美高梅网址注册-澳门mgm4858集团登录网址
做最好的网站
来自 澳门mgm4858集团登录网址 2020-04-04 19:15 的文章
当前位置: 美高梅网址注册 > 澳门mgm4858集团登录网址 > 正文

在内核中就是用HashTable来实现,以上所述是小编

今天主要介绍一下使用递归来按层级查找数据。

在PHP内核中,其中一个很重要的数据结构就是HashTable。我们常用的数组,在内核中就是用HashTable来实现。那么,PHP的HashTable是怎么实现的呢?最近在看HashTable的数据结构,但是算法书籍里面没有具体的实现算法,刚好最近也在阅读PHP的源码,于是参考PHP的HashTable的实现,自己实现了一个简易版的HashTable,总结了一些心得,下面给大家分享一下。

原理挺简单的,主要是通过父级id一级一级的循环查找子级,使用PHP循环代码也很容易实现,不过如果层级越多,PHP重复代码也越多,这时可以使用递归来实现这功能。

笔者github上有一个简易版的HashTable的实现:HashTable实现

1、首先查出要使用的数据组成一个数组(避免递归里查询数据库,之后根据这个数组组成自己需要的数据就可以了)比如得到如下数据:

另外,我在github有对PHP源码更详细的注解。感兴趣的可以围观一下,给个star。PHP5.4源码注解。可以通过commit记录查看已添加的注解。

$data = [ ['id' => '1', 'pid' => '0', 'dsp' => '1'], ['id' => '2', 'pid' => '0', 'dsp' => '2'], ['id' => '3', 'pid' => '0', 'dsp' => '3'], ['id' => '4', 'pid' => '1', 'dsp' => '1-4'], ['id' => '5', 'pid' => '4', 'dsp' => '1-4-5'], ['id' => '6', 'pid' => '5', 'dsp' => '1-4-5-6'], ['id' => '7', 'pid' => '3', 'dsp' => '3-7'], ['id' => '8', 'pid' => '2', 'dsp' => '2-8'], ['id' => '9', 'pid' => '1', 'dsp' => '1-9'], ['id' => '10', 'pid' => '4', 'dsp' => '1-4-10'],];

HashTable的介绍

哈希表是实现字典操作的一种有效数据结构。

2、接下来使用递归重组数据,使数据按层级显示。

定义

简单地说,HashTable(哈希表)就是一种键值对的数据结构。支持插入,查找,删除等操作。在一些合理的假设下,在哈希表中的所有操作的时间复杂度是O(1)(对相关证明感兴趣的可以自行查阅)。

/** * 根据父级id查找子级数据 * @param $data 要查询的数据 * @param int $pid 父级id */public function recursion{ static $child = []; // 定义存储子级数据数组 foreach ($data as $key => $value) { if ($value['pid'] == $pid) { $child[] = $value; // 满足条件的数据添加进child数组 unset; // 使用过后可以销毁 $this->recursion; // 递归调用,查找当前数据的子级 } } return $child;}

[ { "id": "1", "pid": "0", "dsp": "1" }, { "id": "4", "pid": "1", "dsp": "1-4" }, { "id": "5", "pid": "4", "dsp": "1-4-5" }, { "id": "6", "pid": "5", "dsp": "1-4-5-6" }, { "id": "10", "pid": "4", "dsp": "1-4-10" }, { "id": "9", "pid": "1", "dsp": "1-9" }, { "id": "2", "pid": "0", "dsp": "2" }, { "id": "8", "pid": "2", "dsp": "2-8" }, { "id": "3", "pid": "0", "dsp": "3" }, { "id": "7", "pid": "3", "dsp": "3-7" }]

实现哈希表的关键

在哈希表中,不是使用关键字做下标,而是通过哈希函数计算出key的哈希值作为下标,然后查找/删除时再计算出key的哈希值,从而快速定位元素保存的位置。

在一个哈希表中,不同的关键字可能会计算得到相同的哈希值,这叫做“哈希冲突”,就是处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多,开放寻址法,拉链法等等。

因此,实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的方法。

总结

Hash函数

判断一个哈希算法的好坏有以下四个定义:

  • 一致性,等价的键必然产生相等的哈希值;
  • 高效性,计算简便;
  • 均匀性,均匀地对所有的键进行哈希。

哈希函数建立了关键值与哈希值的对应关系,即:h = hash_func(key)。对应关系见下图:
美高梅网址注册 1

设计一个完美的哈希函数就交由专家去做吧,我们只管用已有的较成熟的哈希函数就好了。PHP内核使用的哈希函数是time33函数,又叫DJBX33A,其实现如下:

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
         register ulong hash = 5381;

        /* variant with the hash unrolled eight times */
        for (; nKeyLength >= 8; nKeyLength -= 8) {
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
            hash = ((hash << 5) + hash) + *arKey++;
    }

    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;
        case 0: break;
        EMPTY_SWITCH_DEFAULT_CASE()
    }
    return hash;
}

注:函数使用了一个8次循环+switch来实现,是对for循环的优化,减少循环的运行次数,然后在switch里面执行剩下的没有遍历到的元素。

以上所述是小编给大家介绍的PHP使用递归按层级查找数据的方法,希望对大家有所帮助!

拉链法

将所有具有相同哈希值的元素都保存在一条链表中的方法叫拉链法。查找的时候通过先计算key对应的哈希值,然后根据哈希值找到对应的链表,最后沿着链表顺序查找相应的值。
具体保存后的结构图如下:
美高梅网址注册 2

PHP的HashTable结构

简单地介绍了哈希表的数据结构之后,继续看看PHP中是如何实现哈希表的。

PHP内核hashtable的定义:

typedef struct _hashtable {
          uint nTableSize;
          uint nTableMask;
          uint nNumOfElements;
          ulong nNextFreeElement;
          Bucket *pInternalPointer;
          Bucket *pListHead;
          Bucket *pListTail; 
          Bucket **arBuckets;
          dtor_func_t pDestructor;
          zend_bool persistent;
          unsigned char nApplyCount;
          zend_bool bApplyProtection;
          #if ZEND_DEBUG
               int inconsistent;
          #endif
} HashTable;
  • nTableSize,HashTable的大小,以2的倍数增长
  • nTableMask,用在与哈希值做与运算获得该哈希值的索引取值,arBuckets初始化后永远是nTableSize-1
  • nNumOfElements,HashTable当前拥有的元素个数,count函数直接返回这个值
  • nNextFreeElement,表示数字键值数组中下一个数字索引的位置
  • pInternalPointer,内部指针,指向当前成员,用于遍历元素
  • pListHead,指向HashTable的第一个元素,也是数组的第一个元素
  • pListTail,指向HashTable的最后一个元素,也是数组的最后一个元素。与上面的指针结合,在遍历数组时非常方便,比如reset和endAPI
  • arBuckets,包含bucket组成的双向链表的数组,索引用key的哈希值和nTableMask做与运算生成
  • pDestructor,删除哈希表中的元素使用的析构函数
  • persistent,标识内存分配函数,如果是TRUE,则使用操作系统本身的内存分配函数,否则使用PHP的内存分配函数
  • nApplyCount,保存当前bucket被递归访问的次数,防止多次递归
  • bApplyProtection,标识哈希表是否要使用递归保护,默认是1,要使用

举一个哈希与mask结合的例子:

例如,”foo”真正的哈希值(使用DJBX33A哈希函数)是193491849。如果我们现在有64容量的哈希表,我们明显不能使用它作为数组的下标。取而代之的是通过应用哈希表的mask,然后只取哈希表的低位。

hash           |        193491849  |     0b1011100010000111001110001001
& mask         | &             63  | &   0b0000000000000000000000111111
----------------------------------------------------------------------
= index        | = 9               | =   0b0000000000000000000000001001

因此,在哈希表中,foo是保存在arBuckets中下标为9的bucket向量中。

bucket结构体的定义

typedef struct bucket {
     ulong h;
     uint nKeyLength;
     void *pData;
     void *pDataPtr;
     struct bucket *pListNext;
     struct bucket *pListLast;
     struct bucket *pNext;
     struct bucket *pLast;
     const char *arKey;
} Bucket;
  • h,哈希值(或数字键值的key
  • nKeyLength,key的长度
  • pData,指向数据的指针
  • 美高梅网址注册,pDataPtr,指针数据
  • pListNext,指向HashTable中的arBuckets链表中的下一个元素
  • pListLast,指向HashTable中的arBuckets链表中的上一个元素
  • pNext,指向具有相同hash值的bucket链表中的下一个元素
  • pLast,指向具有相同hash值的bucket链表中的上一个元素
  • arKey,key的名称

PHP中的HashTable是采用了向量加双向链表的实现方式,向量在arBuckets变量保存,向量包含多个bucket的指针,每个指针指向由多个bucket组成的双向链表,新元素的加入使用前插法,即新元素总是在bucket的第一个位置。由上面可以看到,PHP的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。

一个PHP中的HashTable的示例图如下所示:
美高梅网址注册 3

(图片源自网络,侵权即删)

本文由美高梅网址注册发布于澳门mgm4858集团登录网址,转载请注明出处:在内核中就是用HashTable来实现,以上所述是小编

关键词: