PHP底层数据存储结构-哈希表

上一节已经介绍了php数据的存储结构，下面我们看看PHP中的哈希表是怎么实现的。

PHP的哈希实现array(10 => 'Hello'); $a[] = 'TIPI'; var_dump($a);   // ouput array(2) { [10]=> string(5) "Hello" [11]=> string(5) "TIPI" }

PHP中可以不指定索引值向数组中添加元素，这时将默认使用数字作为索引， 和C语言中的枚举类似， 而这个元素的索引到底是多少就由nNextFreeElement字段决定了。 如果数组中存在了数字key，则会默认使用最新使用的key + 1，例如上例中已经存在了10作为key的元素， 这样新插入的默认索引就为11了。

数据容器：槽位变长结构体，主要的目的是增加灵活性。 以下为哈希表插入新元素时申请空间的代码

p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
    return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);

如代码，申请的空间大小加上了字符串key的长度，然后把key拷贝到新申请的空间里。 在后面比如需要进行hash查找的时候就需要对比key这样就可以通过对比p->arKey和查找的key是否一样来进行数据的 查找。申请空间的大小-1是因为结构体内本身的那个字节还是可以使用的。

在PHP5.4中将这个字段定义成const char* arKey类型了。

Zend引擎哈希表结构和关系 Zend引擎哈希表结构和关系

上图来源于网络。

  • Bucket结构体维护了两个双向链表，pNext和pLast指针分别指向本槽位所在的链表的关系。
  • 而pListNext和pListLast指针指向的则是整个哈希表所有的数据之间的链接关系。 HashTable结构体中的pListHead和pListTail则维护整个哈希表的头元素指针和最后一个元素的指针。

PHP中数组的操作函数非常多，例如：array_shift()和array_pop()函数，分别从数组的头部和尾部弹出元素。 哈希表中保存了头部和尾部指针，这样在执行这些操作时就能在常数时间内找到目标。 PHP中还有一些使用的相对不那么多的数组操作函数：next()，prev()等的循环中， 哈希表的另外一个指针就能发挥作用了：pInternalPointer，这个用于保存当前哈希表内部的指针。 这在循环时就非常有用。

如图中左下角的假设，假设依次插入了Bucket1，Bucket2，Bucket3三个元素：

  1. 插入Bucket1时，哈希表为空，经过哈希后定位到索引为1的槽位。此时的1槽位只有一个元素Bucket1。 其中Bucket1的pData或者pDataPtr指向的是Bucket1所存储的数据。此时由于没有链接关系。pNext， pLast，pListNext，pListLast指针均为空。同时在HashTable结构体中也保存了整个哈希表的第一个元素指针， 和最后一个元素指针，此时HashTable的pListHead和pListTail指针均指向Bucket1。
  2. 插入Bucket2时，由于Bucket2的key和Bucket1的key出现冲突，此时将Bucket2放在双链表的前面。 由于Bucket2后插入并置于链表的前端，此时Bucket2.pNext指向Bucket1，由于Bucket2后插入。 Bucket1.pListNext指向Bucket2，这时Bucket2就是哈希表的最后一个元素，这是HashTable.pListTail指向Bucket2。
  3. 插入Bucket3，该key没有哈希到槽位1，这时Bucket2.pListNext指向Bucket3，因为Bucket3后插入。 同时HashTable.pListTail改为指向Bucket3。

简单来说就是哈希表的Bucket结构维护了哈希表中插入元素的先后顺序，哈希表结构维护了整个哈希表的头和尾。 在操作哈希表的过程中始终保持预算之间的关系。

哈希表的操作接口

和上一节类似，将简单介绍PHP哈希表的操作接口实现。提供了如下几类操作接口：

  • 初始化操作，例如zend_hash_init()函数，用于初始化哈希表接口，分配空间等。
  • 查找，插入，删除和更新操作接口，这是比较常规的操作。
  • 迭代和循环，这类的接口用于循环对哈希表进行操作。
  • 复制，排序，倒置和销毁等操作。

本小节选取其中的插入操作进行介绍。 在PHP中不管是对数组的添加操作（zend_hash_add），还是对数组的更新操作（zend_hash_update）， 其最终都是调用_zend_hash_add_or_update函数完成，这在面向对象编程中相当于两个公有方法和一个公共的私有方法的结构， 以实现一定程度上的代码复用。

 
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
     //...省略变量初始化和nKeyLength <=0 的异常处理
 
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h & ht->nTableMask;
 
    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
            if (!memcmp(p->arKey, arKey, nKeyLength)) { //  更新操作
                if (flag & HASH_ADD) {
                    return FAILURE;
                }
                HANDLE_BLOCK_INTERRUPTIONS();
 
                //..省略debug输出
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                    *pDest = p->pData;
                }
                HANDLE_UNBLOCK_INTERRUPTIONS();
                return SUCCESS;
            }
        }
        p = p->pNext;
    }
 
    p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
    if (!p) {
        return FAILURE;
    }
    memcpy(p->arKey, arKey, nKeyLength);
    p->nKeyLength = nKeyLength;
    INIT_DATA(ht, p, pData, nDataSize);
    p->h = h;
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); //Bucket双向链表操作
    if (pDest) {
        *pDest = p->pData;
    }
 
    HANDLE_BLOCK_INTERRUPTIONS();
    CONNECT_TO_GLOBAL_DLLIST(p, ht);    // 将新的Bucket元素添加到数组的链接表的最后面
    ht->arBuckets[nIndex] = p;
    HANDLE_UNBLOCK_INTERRUPTIONS();
 
    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /*  如果此时数组的容量满了，则对其进行扩容。*/
    return SUCCESS;
}

整个写入或更新的操作流程如下：

  1. 生成hash值，通过与nTableMask执行与操作，获取在arBuckets数组中的Bucket。
  2. 如果Bucket中已经存在元素，则遍历整个Bucket，查找是否存在相同的key值元素，如果有并且是update调用，则执行update数据操作。
  3. 创建新的Bucket元素，初始化数据，并将新元素添加到当前hash值对应的Bucket链表的最前面（CONNECT_TO_BUCKET_DLLIST）。
  4. 将新的Bucket元素添加到数组的链接表的最后面（CONNECT_TO_GLOBAL_DLLIST）。
  5. 将元素个数加1，如果此时数组的容量满了，则对其进行扩容。这里的判断是依据nNumOfElements和nTableSize的大小。 如果nNumOfElements > nTableSize则会调用zend_hash_do_resize以2X的方式扩容（nTableSize << 1）。
php进阶

相关

标签