Skip to content

PHP 内核中的 HashTable 分析

HashTable 是 PHP 的灵魂,因为在 Zend 引擎中大量地使用了 HashTable,如变量表、常量表、函数表等,这些都是使用 HashTable 保存的,另外 PHP 的数组也是使用 HashTable 实现的。

PHP 内核 HashTable 的数据结构

PHP 中的 HashTable 实现代码保存在 Zend/zend_hash.hZend/zend_hash.c 这两个文件中,首先看 HashTable 的数据结构定义:

// Zend/zend_hash.h
#include <stdio.h>

typedef struct bucket {
    ulong h;                    // 保存经过 hash 函数处理之后的 hash 值
    uint nKeyLength;            // 保存索引(key)的长度
    void *pData;                // 指向要保存的内存块地址
    void *pDataPtr;             // 保存指针数据
    struct bucket *pListNext;   // 指向双向链表的下一个元素
    struct bucket *pListLast;   // 指向双向链表的上一个元素
    struct bucket *pNext;       // 指向具有同一个 hash 值的下一个元素
    struct bucket *pLast;       // 指向具有同一个 hash 值的上一个元素
    char arKey[1];              // 保存索引(key),而且必须为最后一个成员

} Bucket;

typedef struct _hashtable {
    uint nTableSize;            // 记录 Bucket 数组的大小
    uint nTableMask;            
    uint nNumOfElements;        // 记录 HashTable 中保存元素的个数
    ulong nNextFreeElement;     // 下一个可用 Bucket 位置
    Bucket *pInternalPointer;   // 遍历 HashTable 元素
    Bucket *pListHead;          // 双向链表表头
    Bucket *pListTail;          // 双向链表表尾
    Bucket **arBuckets;         // Bucket 数组
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
} HashTable;

在上面的数据结构定义中看到,Bucket 和 HashTable 这两个结构体构成一个完整的 HashTable

Bucket 结构体分析

PHP 的 HashTable 同时维护一个双向链表,用于有序遍历 HashTable 里的元素

在这些成员变量中,pData 和 pDataPtr 比较容易混淆。pData 指向的是想要保存的内存块地址,一般是通过 malloc 之类的系统调用分配出来。但是有时候只想保存一个指针,如果这样也去调用 malloc 分配内存的话就会造成很多细小的内存块,从而导致产生内存碎片。这种情况 PHP 内核是不能容忍的,所以出现了 pDataPtr 指针。pDataPtr 的作用就是当想要保存的数据是一个指针类型的数据时,就直接保存到 pDataPtr 成员变量中,而不用调用 malloc 分配内存,从而防止内存碎片的产生,然后 pData 直接指向 pDataPtr。当要保存的数据不是指针时,pDataPtr 被设置成 NULL。

HashTable 结构体分析

一个 Bucket 只能保存一个数据,而 HashTable 的目的就是通过索引(key)把每个元素分散到一个唯一的位置(当没有冲突时),这是怎么做到的呢?答案是 通过 hash 算法把索引处理成一个 int 的数,然后定位到一个 Bucket 数组的其中一个元素中,如图所示。

HashTable 原理

字符串索引经过 hash 函数处理后,返回一个值为 1 的 int 索引,然后从 Bucket 数组中取得索引为 1 的元素(第二个元素),这就是 HashTable 的原理和实现方法。

PHP 内核通过 HashTable 结构管理 Bucket 数组。arBuckets 中保存的就是上图所示的 Bucket 数组,而 nTableSize 记录 arBuckets 数组的大小。

// PHP 内核是怎样通过一个字符串索引定位到 Bucket 数组(arBuckets)中的一个元素的,代码如下:
h = hash(key);
pos = h % nTableSize;
bucket = arBuckets[pos]

int hash(char *key) {
    int h = 0;
    char *p = key;
    while (*p) {
        h += *p;
        p++;
    }
    return h;
}

// 上面的 hash 算法只展示了 hash 函数是怎么把一个字符串处理成一个整数,实际上 PHP 内核的 hash 算法会更复杂。

值得注意的是 nNumOfElements 与 nTableSize 的区别。

Bucket 存储数据示意图

pListHead 和 pListTail 分别是双向链表的表头和表尾指针。传统的 HashTable 是不会同时维护双向链表的。下图展示了这个双向链表。

HashTable 中的双向链表

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*