举一个哈希与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的示例图如下所示：

PHP's new hashtable implementation

HashTable相干API

• zend_hash_init
• zend_hash_add_or_update
• zend_hash_find
• zend_hash_del_key_or_index

zend_hash_init

函数履行步调

• 设置哈希表大年夜小
• 设置构造体其他成员变量的初始值 (包含释放内存用的析构函数pDescructor)

具体代码注解点击：zend_hash_init源码

注：

1、pHashFunction在此处并没有效到，php的哈希函数应用的是内部的zend_inline_hash_func

2、zend_hash_init履行之后并没有真正地为arBuckets分派内存和计算出nTableMask的大年夜小，真正分派内存和计算nTableMask是在插入元素时进行CHECK_INIT检查初始化时进行。

zend_hash_add_or_update

函数履行步调

• 检查键的长度
• 检查初始化
• 计算哈希值和下标
• 遍历哈希值地点的bucket，如不雅找到雷同的key且值须要更新，则更新数据，不然持续指向bucket的下一?元素，直到指向bucket的最后一个地位
• 为新参加的元素分派bucket，设置新的bucket的属性值，然后添加到哈希表中
• 如不雅哈希表空间满了，则从新调剂哈希表的大年夜小

函数履行流程图

CONNECT_TO_BUCKET_DLLIST是将新元素添加到具有雷同hash值的bucket链表。

CONNECT_TO_GLOBAL_DLLIST是将新元素添加到HashTable的双向链表。

具体代码和注解请点击：zend_hash_add_or_update代码注解。

zend_hash_find

函数履行步调

• 计算哈希值和下标
• 遍历哈希值地点的bucket，如不雅找到key地点的bucket，则返回值，不然，指向下一?bucket，直到指向bucket链表中的最后一个地位

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

具体代码和注解请点击：zend_hash_find代码注解。

zend_hash_del_key_or_index

函数履行步调

• 计算key的哈希值和下标
• 遍历哈希值地点的bucket，如不雅找到key地点的bucket，则进行第三步，不然，指向下一?bucket，直到指向bucket链表中的最后一个地位
• 如不雅要删除的是第一个元素，直接将arBucket[nIndex]指向第二个元素；其余的操作是将当前指针的last的next履行当前的next
   2/3   首页 上一页 1 2 3 下一页 尾页
  
  

  　　推荐阅读

  　　初识Rust语言的所有权概念

  今朝仅看了第二版的官方文档，记录一下初步印象，应当还有更深刻一致的解释，程度有限，仅供参考。实验情况：ubuntu17.10，rust1.18，vscode1.14 + 扩大rust（rls）。BTW，情况搭建顺利得>>>详细阅读

  
  

  本文标题：[PHP内核探索]PHP中的哈希表

  地址：http://www.17bianji.com/lsqh/36437.html

   1/2    1