PHP HashTable结构

[diffnest]

1. 创建并且初始化一个HashTable

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;

    SET_INCONSISTENT(HT_OK);

    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    ·······
}

• *ht是指针，指向一个HashTable，我们既可以&一个已存在的HashTable变量， 也可以通过emalloc()、pemalloc()等函数来直接申请一块内存， 不过最常用的方法还是用ALLOC_HASHTABLE(ht)宏来让内核自动的替我们完成这项工作。 ALLOC_HASHTABLE(ht)所做的工作相当于ht = emalloc(sizeof(HashTable));
• nSize代表着这个HashTable可以拥有的元素的最大数量(HashTable能够包含任意数量的元素， 这个值只是为了提前申请好内存，提高性能，省的不停的进行rehash操作)。;
• pHashFunction是早期的Zend Engine中的一个参数，为了兼容没有去掉它， 但它已经没有用处了，所以我们直接赋成NULL就可以了。在原来， 它其实是一个钩子，用来让用户自己hook一个散列函数，替换php默认的DJBX33A算法实现。
• pDestructor也代表着一个回调函数，当我们删除或者修改HashTable中其中一个元素时候便会调用， 它的函数原型必须是这样的：void method_name(void pElement);这里的pElement是一个指针，指向HashTable中那么将要被删除或者修改的那个数据，而数据的类型往往也是个指针。
• persistent是最后一个参数，它的含义非常简单。 如果它为true，那么这个HashTable将永远存在于内存中，而不会在RSHUTDOWN阶段自动被注销掉。 此时第一个参数ht所指向的地址必须是通过pemalloc()函数申请的。

2. C中hashtable结构体解释（zend/Zend_hash.h）

typedef struct _hashtable {
    uint nTableSize; //hash Bucket的大小，最小为8，以2x增长
    uint nTableMask; //nTableSize-1，掩码，用于根据hash值计算存储位置。
    uint nNumOfElements;//hash Bucket中当前存在的元素个数，count()函数会直接返回此值 ，是PHP数组中实际存储元素的个数，我们使用count,sizeof计算的就是获取的这个值
    ulong nNextFreeElement;//下一个数字索引的位置（当我们申请一个空下标元素的时候就需要用到此项，比如$ret[] = 'apple'。）
    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;

3.C中bucket结构体解释（zend/Zend_hash.h）

typedef struct bucket {
    /* Used for numeric indexing */
    ulong h; //对char *key进行hash后的值，数字索引的话就是索引值  uint nKeyLength;//hash关键字的长度，如果数组索引为数字，此值为0
    void *pData; //指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr; //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;//整个hash表的下一元素
    struct bucket *pListLast;//整个哈希表该元素的上一个元素
    struct bucket *pNext;//存放在同一个hash Bucket内的下一个元素
    struct bucket *pLast;//同一个哈希bucket的上一个元素
    const char *arKey;
    /*存储字符索引，此项必须放在最未尾，因为此处只字义了1个字节，存储的实际上是指向char *key的值，
    这就意味着可以省去再赋值一次的消耗，而且，有时此值并不需要，所以同时还节省了空间。
    */
} Bucket;

解释：

1.h是一个哈希值，未经过掩码矫正的哈希DBJ算出来的原始值。或是数字索引的数字(通过nKeyLength=0来表示是数字索引)。而对于字符串索引来说, 索引值保存在arKey中, 索引的长度保存在nKeyLength中.

2.arKey，用来记录作为哈希计算的字符串，nKeyLength是哈希字符串的长度，对于整形键值是用不到这两项的。

3.pData以及pDataPtr是实际存储数据的指针，在PHP里面他们通常是指向一个zval结构。在Bucket中，实际的数据是保存在pData指针指向的内存块中，通常这个内存块是系统另外分配的。但有一种情况例外，就是当Bucket保存 的数据是一个指针时，HashTable将不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pDataPtr中，然后再将pData指向 本结构成员的地址。这样可以提高效率，减少内存碎片。由此我们可以看到PHP HashTable设计的精妙之处。如果Bucket中的数据不是一个指针，pDataPtr为NULL。

4.pListNext, pListLast 指定了整个数组的顺序，PHP中的遍历就是通过哈希结构体中的pListHead bucket依次遍历pListNext直到数组结束。

5.pNext和pLast 这两个指针是用来解决哈希冲突的，这个在下面哈希冲突中详细介绍，在PHP的哈希表冲突的处理采用的是拉链法也就是在每个可能冲突的键值位置拉出一个链表来存储对应的键值数据。

6.arKey 最后一个元素, 这个是flexible array技巧, 可以节省内存,和方便初始化的一种做法, 具体的参看http://blog.csdn.net/zhangboyj/article/details/6232168 （c99 柔性数组成员），博文中特意指出不能用arKey[1]的写法，这个我现在还不太懂。

4. BUCKET结构图（一图解千惑）

下面是引用了tipi里面的插入说明:

如图中左下角的假设，假设依次插入了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结构维护了哈希表中插入元素的先后顺序，哈希表结构维护了整个哈希表的头和尾。 在操作哈希表的过程中始终保持预算之间的关系。