php中HashTable的实现

     PHP内核中的哈希表是十分重要的数据结构，PHP的大部分的语言特性都是基于哈希表实现的， 例如：变量的作用域、函数表、类的属性、方法等，Zend引擎内部的很多数据都是保存在哈希表中的(在前面的章节中也介绍了hashTable的应用)。

     Zend HashTable的实现结合了双向链表和向量（数组）两种数据结构的优点，为PHP提供了非常高效的数据存储和查询机制。

一、HashTable的数据结构

     PHP实现HashTable主要是通过两个数据结构Bucket(桶)和HashTable。
     从PHP脚本端来看，HashTable相当于Array对象，而Bucket相当于Array对象里的某个元素。对于多维数组实际就是HashTable的某个Bucket里存储着另一个HashTable。

①HashTable结构：

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

 ②Bucket结构：

typedef struct bucket {
     ulong h; //数组索引
     uint nKeyLength; //字符串索引的长度
     void *pData; //实际数据的存储地址
     void *pDataPtr; //引入的数据存储地址
     struct bucket *pListNext;
     struct bucket *pListLast;
     struct bucket *pNext; //双向链表的下一个元素的地址
     struct bucket *pLast;//双向链表的下一个元素地址
     char arKey[1]; /* Must be last element */
} Bucket;

二、HashTable的初始化

     php为HashTable的初始化提供了一个接口zend_hash_init，这个接口主要是把HashTable结构体的成员变量初始化，并且初始化桶数组，实现如下：

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction,
                    dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;
    //...
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    // ...
    ht->nTableMask = ht->nTableSize - 1;
 
    /* Uses ecalloc() so that Bucket* == NULL */
    if (persistent) {
        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
        if (!tmp) {
            return FAILURE;
        }
        ht->arBuckets = tmp;
    } else {
        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
        if (tmp) {
            ht->arBuckets = tmp;
        }
    }
 
    return SUCCESS;
}

    参数nSize是要申请的桶数组的大小，但这并不是php实际申请的大小，因为php内部会计算出一个不小于nSize并且使2的n次方的数作为实现申请的大小。

    参数persistent判断是否使用php内存管理，如果为FALSE就使用操作系统的内存管理，否则就是使用php内存管理。一般把这个参数设置为TRUE，因为使用操作系统内存管理需要自己释放内存，就容易造成内存泄露，所以最好交给php去管理内存。

三、HashTable的操作接口

     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）。

四、哈希表索引处理方式

     在内核中只允许数字索引，对于字符串索引，内核采用了time33算法将字符串转换为整型。

1、数字索引处理

//省略了部分代码，提出主要的逻辑
ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{    
     ulong h;
     uint nIndex;
     Bucket *p;
     //省略了部分代码，提出主要的逻辑
     nIndex = h & ht->nTableMask;
     p = ht->arBuckets[nIndex];
     p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
     if (!p) {
          return FAILURE;
     }
     p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
     p->h = h;
     INIT_DATA(ht, p, pData, nDataSize);
     if (pDest) {
          *pDest = p->pData;
     }

     ht->arBuckets[nIndex] = p;

     ht->nNumOfElements++;

     return SUCCESS;
}

 2、字符串索引的处理

    与数字索引相比，只是多了一步将字符串转换为整型。用到的算法是time33。下面贴出了算法的实现，就是对字符串的每个字符转换为ASCII码乘上33并且相加得到的结果。

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;
     }
     return hash;
}

zend_hash.c
//下面省略了部分代码，提出主要的逻辑
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)
{     
     ulong h;
     uint nIndex;
     Bucket *p;
     
     h = zend_inline_hash_func(arKey, nKeyLength); //字符串转整型
     nIndex = h & ht->nTableMask;
     p = ht->arBuckets[nIndex];
     p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
     if (!p) {
          return FAILURE;
     }
     p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
     p->h = h;
     INIT_DATA(ht, p, pData, nDataSize);
     if (pDest) {
          *pDest = p->pData;
     }

     ht->arBuckets[nIndex] = p;

     ht->nNumOfElements++;

     return SUCCESS;
}

五、内核中如何实现均与分布和解决HASH碰撞问题

1、均匀分布

    均匀分布是指，将需要存储的各个元素均匀的分布到HashTable中。而负责计算具体分布到表中哪个位置的函数就是散列函数做的事情，所以散列函数的实现直接关系到均匀分布的效率。
    上面也提到了PHP内核中用了简单的方式实现：h & ht->nTableMask;

2、HASH碰撞

     Hash碰撞是指，经过Hash算法后得到的值会出现key1 != key2, 但Hash(key1)却等于Hash(key2)的情况，这就是碰撞问题。
     在PHP内核来看，就是会出现key1 != key2, 但key1 & ht->nTableMask却等于 key2 & ht->nTableMask的情况。PHP内核使用双向链表的方式来存储冲突的数据。即Bucket本身也是一个双向链表，当发生冲突时，会将数据按顺序向后排列。
     如果不发生冲突，Bucket即是长度为1的的双向链表。

ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
{
     ulong h;
     uint nIndex;
     Bucket *p;

     IS_CONSISTENT(ht);

     h = zend_inline_hash_func(arKey, nKeyLength);
     nIndex = h & ht->nTableMask;

     p = ht->arBuckets[nIndex];
     //找到元素时，并非立即返回，而是要再对比h与nKeyLength，防止hash碰撞。此段代码就是遍历链表,直到链表尾部。
     while (p != NULL) {
          if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
               if (!memcmp(p->arKey, arKey, nKeyLength)) {
                    *pData = p->pData;
                    return SUCCESS;
               }
          }
          p = p->pNext;
     }
     return FAILURE;
}

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