在Zend Engine中的HashTable的实现代码主要包括zend_hash.h,和zend_hash.c这两个文件中。Zend HashTable包括两个主要的数据结构，其一是Bucket（桶）结构，另一个是HashTable结构。Bucket结构是用于保存数据的容器，而 HashTable结构则提供了对所有这些Bucket(或桶列)进行管理的机制

1 数据结构

typedef struct bucket {
    ulong h;                               /* Used for numeric indexing */
    uint nKeyLength;                       /* key 长度 */
    void *pData;                           /* 指向Bucket中保存的数据的指针 */
    void *pDataPtr;                        /* 指针数据 */
    struct bucket *pListNext;              /* 指向HashTable桶列中下一个元素 */
    struct bucket *pListLast;              /* 指向HashTable桶列中前一个元素 */
    struct bucket *pNext;                  /* 指向具有同一个hash值的桶列的后一个元素 */
    struct bucket *pLast;                  /* 指向具有同一个hash值的桶列的前一个元素 */
    char arKey[1];                         /* 必须是最后一个成员，key名称*/
} Bucket;

在Zend HashTable中，每个数据元素(Bucket)有一个键名(key)，它在整个HashTable中是唯一的，不能重复。根据键名可以唯一确定 HashTable中的数据元素。

键名有两种表示方式:

• 使用字符串arKey作为键名，该字符串的长度为nKeyLength. 注意到在上面的 数据结构中arKey虽然只是一个长度为1的字符数组，但它并不意味着key只能是一个字符。实际上Bucket是一个可变长的结构体，由于arKey是 Bucket的最后一个成员变量，通过arKey与nKeyLength结合可确定一个长度为nKeyLength的key。这是C语言编程中的一个比较 常用的技巧。
• 索引方式，这时nKeyLength总是0，长整型字段h就表示该数据元素的键名。简单的来说，即如果nKeyLength=0，则键名为h；否则键名为arKey, 键名的长度为nKeyLength。

当nKeyLength > 0时，并不表示这时的h值就没有意义。事实上，此时它保存的是arKey对应的hash值。不管hash函数怎么设计，冲突都是不可避免的，也就是说不同 的arKey可能有相同的hash值。具有相同hash值的Bucket保存在HashTable的arBuckets数组(参考下面的解释)的同一个索 引对应的桶列中。这个桶列是一个双向链表，其前向元素，后向元素分别用pLast,pNext来表示。新插入的Bucket放在该桶列的最前面。

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

HashTable中所有的Bucket通过pListNext, pListLast构成了一个双向链表。最新插入的Bucket放在这个双向链表的最后。

注意在一般情况下，Bucket并不能提供它所存储的数据大小的信息。所以在PHP的实现中，Bucket中保存的数据必须具有管理自身大小的能力。

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;                 // 判断hash是否一致
#endif
} HashTable;

在HashTable结构中，nTableSize指定了HashTable的大小，同时它限定了HashTable中能保存Bucket的最大数量，此 数越大，系统为HashTable分配的内存就越多。为了提高计算效率，系统自动会将nTableSize调整到最小一个不小于nTableSize的2 的整数次方。也就是说，如果在初始化HashTable时指定一个nTableSize不是2的整数次方，系统将会自动调整nTableSize的值。即

nTableSize = 2ceil(log(nTableSize, 2)) or
nTableSize = pow(ceil(log(nTableSize,2)))

例如，如果在初始化HashTable的时候指定nTableSize = 11，HashTable初始化程序会自动将nTableSize增大到16。

arBuckets是HashTable的关键，HashTable初始化程序会自动申请一块内存，并将其地址赋值给arBuckets，该内存大 小正好能容纳nTableSize个指针。我们可以将arBuckets看作一个大小为nTableSize的数组，每个数组元素都是一个指针，用于指向 实际存放数据的Bucket。当然刚开始时每个指针均为NULL。

nTableMask的值永远是nTableSize – 1，引入这个字段的主要目的是为了提高计算效率，是为了快速计算Bucket键名在arBuckets数组中的索引。

nNumberOfElements记录了HashTable当前保存的数据元素的个数。当nNumberOfElement大于nTableSize时，HashTable将自动扩展为原来的两倍大小。

nNextFreeElement记录HashTable中下一个可用于插入数据元素的arBuckets的索引。

pListHead, pListTail则分别表示Bucket双向链表的第一个和最后一个元素，这些数据元素通常是根据插入的顺序排列的。也可以通过各种排序函数对其进行重 新排列。pInternalPointer则用于在遍历HashTable时记录当前遍历的位置，它是一个指针，指向当前遍历到的Bucket，初始值是 pListHead。

pDestructor是一个函数指针，在HashTable的增加、修改、删除Bucket时自动调用，用于处理相关数据的清理工作。

persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。具体请参考PHP的内存管理。

nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制。

inconsistent成员用于调试目的，只在PHP编译成调试版本时有效。表示HashTable的状态，状态有四种：

|状态值|含义|
|--|
|HT_IS_DESTROYING |正在删除所有的内容，包括arBuckets本身 |
|HT_IS_DESTROYED |已删除，包括arBuckets本身|
|HT_CLEANING |正在清除所有的arBuckets指向的内容，但不包括arBuckets本身|
|HT_OK |正常状态，各种数据完全一致|

typedef struct _zend_hash_key {
    char *arKey;             /* hash元素key名称 */
    uint nKeyLength;         /* hash 元素key长度 */
    ulong h;                 /* key计算出的hash值或直接指定的数值下标 */
} zend_hash_key;

现在来看zend_hash_key结构就比较容易理解了。它通过arKey, nKeyLength, h三个字段唯一确定了HashTable中的一个元素。

根据上面对HashTable相关数据结构的解释，我们可以画出HashTable的内存结构图：

zend_hashtable.png

具体实现

hash的初始化

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;
    Bucket **tmp; 
    SET_INCONSISTENT(HT_OK); 
    if (nSize >= 0×80000000)  {
        /* prevent overflow */
        ht->nTableSize = 0×80000000;
    } else {
        while ((1U << i) < nSize)  { 
            /* 自动调整nTableSize至2的n次方 */ 
            i++; 
        } 
        ht->nTableSize = 1 << i; /* i的最小值为3，因此HashTable大小最小为8 */
    } 
    ht->nTableMask = ht->nTableSize - 1;
    ht->pDestructor = pDestructor;
    ht->arBuckets = NULL;
    ht->pListHead = NULL;
    ht->pListTail = NULL;
    ht->nNumOfElements = 0;
    ht->nNextFreeElement = 0;
    ht->pInternalPointer = NULL;
    ht->persistent = persistent;
    ht->nApplyCount = 0;
    ht->bApplyProtection = 1; 

    /* 根据persistent使用不同方式分配arBuckets内存，并将其所有指针初始化为NULL*/
    /* 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;
}

在以前的版本中，可以使用pHashFunction来指定hash函数。但现PHP已强制使用DJBX33A算法，因此实际上pHashFunction这个参数并不会用到，保留在这里只是为了与以前的代码兼容。

增加、插入和修改元素

向HashTable中添加一个新的元素最关键的就是要确定将这个元素插入到arBuckets数组中的哪个位置。根据上面对Bucket结构键名 的解释，我们可以知道有两种方式向HashTable添加一个新的元素。

• 使用字符串作为键名来插入Bucket；
• 使用索引作为键名来插入Bucket, 具体又可以分为两种情况：指定索引或不指定索引，指定索引指的是强制将Bucket插入到指定的索引位置中；不指定索引 则将Bucket插入到nNextFreeElement对应的索引位置中。

这几种插入数据的方法实现比较类似，不同的只是定位Bucket的方法。

修改HashTable中的数据的方法与增加数据的方法也很类似。

我们先看第一种使用字符串作为键名增加或修改Bucket的方法：

/**
* @desc 往ht里面添加/修改key-value，只服务于关联数组，索引数组另有服务函数
* @param ht         : 哈希表
* @param arKey      : key 
* @param nKeyLength : key的长度
* @param pData      : value
* @param nDataSize  : value的长度
* @param pDest      : value为指针时的值
* @param flag       : 标识新增还是修改  
*/
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;
#ifdef ZEND_SIGNALS
    TSRMLS_FETCH();
#endif

    IS_CONSISTENT(ht);

    // 异常情况，key长度为0 
    if (nKeyLength <= 0) {
#if ZEND_DEBUG
        ZEND_PUTS("zend_hash_update: Can't put in empty key\n");
#endif
        return FAILURE;
    }

    // 添加之前，确保hash表空间已经分配过了
    CHECK_INIT(ht);

    // 计算当前key的hash值
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        // hash表中有该节点
        // 这地方分了两种情形（为什么分两种情况呢？？？？）
        if (p->arKey == arKey ||
            ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
                if (flag & HASH_ADD) {
                    return FAILURE;
                }
                HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
                if (p->pData == pData) {
                    ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
                    HANDLE_UNBLOCK_INTERRUPTIONS();
                    return FAILURE;
                }
#endif
                // 更新value的时候先将原先的指针内存释放
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                // UPDATE_DATA不负责释放内存
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                    *pDest = p->pData;
                }
                HANDLE_UNBLOCK_INTERRUPTIONS();
                return SUCCESS;
        }
        p = p->pNext;
    }
    
    // 执行到这里，操作只能是增加一个节点了
    // 如果arKey是字符串(???)
    // Zend/zend_string.h +37
    // #define IS_INTERNED(s) \
    //    (((s) >= CG(interned_strings_start)) && ((s) < CG(interned_strings_end)))
    if (IS_INTERNED(arKey)) {
        // 这里没有分配多余的空间
        // 也就是value是一个指针
        p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
        if (!p) {
            return FAILURE;
        }
        p->arKey = arKey;
    } else {
        p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
        if (!p) {
            return FAILURE;
        }
        // 注意这里的 p + 1 是跨过整个Bucket结构体空间
        // 结构体重的arKey存放的是他之后一个字节的地址
        // 而多分配的nKeyLength 存放的是value值
        p->arKey = (const char*)(p + 1);
        memcpy((char*)p->arKey, arKey, nKeyLength);
    }
    p->nKeyLength = nKeyLength;
    INIT_DATA(ht, p, pData, nDataSize);
    p->h = h;

    // 链入本桶内的双向链表中
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
    if (pDest) {
        *pDest = p->pData;
    }

    HANDLE_BLOCK_INTERRUPTIONS();

    // 链入全局双向链表中
    CONNECT_TO_GLOBAL_DLLIST(p, ht);
    ht->arBuckets[nIndex] = p;
    HANDLE_UNBLOCK_INTERRUPTIONS();

    // 没插入完成一个 判断是否需要扩容
    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
    return SUCCESS;
}

因为这个函数是使用字符串作为键名来插入数据的，因此它首先检查nKeyLength的值是否大于0，如果不是的话就直接退出。然后计算arKey对应的 hash值h，将其与nTableMask按位与后得到一个无符号整数nIndex。这个nIndex就是将要插入的Bucket在arBuckets数 组中的索引位置。

现在已经有了arBuckets数组的一个索引，我们知道它包括的数据是一个指向Bucket的双向链表的指针。如果这个双向链表不为空的话我们首先检查 这个双向链表中是否已经包含了用字符串arKey指定的键名的Bucket，这样的Bucket如果存在，并且我们要做的操作是插入新Bucket(通过 flag标识)，这时就应该报错 – 因为在HashTable中键名不可以重复。如果存在，并且是修改操作，则使用在HashTable中指定了析构函数pDestructor对原来的 pData指向的数据进行析构操作；然后将用新的数据替换原来的数据即可成功返回修改操作。
如果在HashTable中没有找到键名指定的数据，就将该数据封装到Bucket中，然后插入HashTable。这里要注意的是如下的两个宏：

CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex])
CONNECT_TO_GLOBAL_DLLIST(p, ht)

前者是将该Bucket插入到指定索引的Bucket双向链表中，后者是插入到整个HashTable的Bucket双向链表中。两者的插入方式也不同，前者是将该Bucket插入到双向链表的最前面，后者是插入到双向链表的最末端。

下面是第二种插入或修改Bucket的方法，即使用索引的方法：

/**
* @desc 数字索引类型的key-value值添加
* @param ht        : 添加的hash表结构
* @param  h        : key 新增时 h 设置为0 更新时会透传上层的h
* @param pData     : value
* @param nDataSize ：value的长度
* @param pDest     : 用于指向下一个元素
* @param flag      : HASH_NEXT_INSERT or HASH_ADD    
*/
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)
{
    uint nIndex;
    Bucket *p;
#ifdef ZEND_SIGNALS
    TSRMLS_FETCH();
#endif

    IS_CONSISTENT(ht);
    CHECK_INIT(ht);

    // 如果是HASH_ADD，h为当前保留的最大下标
    // 如果是HASH_NEXT_INSERT, 两种情况 
    // 1、更新已有值，此时(h < nNextFreeElement)，定位到对应的元素，修改即可
    // 2、插入一个key-value对，此时 (h >= nNextFreeElement), 那么参考L515行注释
    if (flag & HASH_NEXT_INSERT) {
        h = ht->nNextFreeElement;
    }
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if ((p->nKeyLength == 0) && (p->h == h)) {
            // 找到了要添加的value了，并且flag设置为添加（添加到XX之后或者直接添加）
            if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
                return FAILURE;
            }
            HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
            if (p->pData == pData) {
                ZEND_PUTS("Fatal error in zend_hash_index_update: p->pData == pData\n");
                HANDLE_UNBLOCK_INTERRUPTIONS();
                return FAILURE;
            }
#endif
            if (ht->pDestructor) {
                ht->pDestructor(p->pData);
            }
            UPDATE_DATA(ht, p, pData, nDataSize);
            HANDLE_UNBLOCK_INTERRUPTIONS();
            // 当插入一个key-value对且key>nNextFreeElement时，及时修正nNextFreeElement值
            // 以保证下一个元素的下标是当前下标+1
            // 这个地方挺有意思的，例如当前已用下标情况是 0, 1, 2, 3, 9
            // 那么插入一个下标为8的元素，不更新nNextFreeElement 
            if ((long)h >= (long)ht->nNextFreeElement) {
                ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
            }
            if (pDest) {
                *pDest = p->pData;
            }
            return SUCCESS;
        }
        p = p->pNext;
    }
    p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent);
    if (!p) {
        return FAILURE;
    }
    p->arKey = NULL;
    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;
    }

    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);

    HANDLE_BLOCK_INTERRUPTIONS();
    ht->arBuckets[nIndex] = p;
    CONNECT_TO_GLOBAL_DLLIST(p, ht);
    HANDLE_UNBLOCK_INTERRUPTIONS();

    if ((long)h >= (long)ht->nNextFreeElement) {
        ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
    }
    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);
    return SUCCESS;
}

flag标志指明当前操作是HASH_NEXT_INSERT(不指定索引插入或修改), HASH_ADD(指定索引插入)还是HASH_UPDATE(指定索引修改)。由于这些操作的实现代码基本相同，因此统一合并成了一个函数，再用flag加以区分。本函数基本与前一个相同，不同的是如果确定插入到arBuckets数组中的索引的方法。如果操作是HASH_NEXT_INSERT，则直接使用nNextFreeElement作为插入的索引。注意nNextFreeElement的值是如何使用和更新的。

访问元素

HashTable用两种方式来访问元素:

• 使用字符串arKey的zend_hash_find()；
• 使用索引的访问方式zend_hash_index_find();
  由于其实现的代码很简单，分析工作就留给读者自已完成。

删除元素

HashTable删除数据均使用zend_hash_del_key_or_index()函数来完成，其代码也较为简单，这里也不再详细分析。需要的是注意如何根据arKey或h来计算出相应的下标，以及两个双向链表的指针的处理。

遍历元素

/* This is used to recurse elements and selectively delete certain entries 
 * from a hashtable. apply_func() receives the data and decides if the entry 
 * should be deleted or recursion should be stopped. The following three 
 * return codes are possible:
 * ZEND_HASH_APPLY_KEEP   - continue
 * ZEND_HASH_APPLY_STOP   - stop iteration
 * ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
 */

ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
{
    Bucket *p;

    IS_CONSISTENT(ht);

    HASH_PROTECT_RECURSION(ht);
    p = ht->pListHead;
    while (p != NULL) {
        int result = apply_func(p->pData TSRMLS_CC);
        
        if (result & ZEND_HASH_APPLY_REMOVE) {
            p = zend_hash_apply_deleter(ht, p);
        } else {
            p = p->pListNext;
        }
        if (result & ZEND_HASH_APPLY_STOP) {
            break;
        }
    }
    HASH_UNPROTECT_RECURSION(ht);
}

因为HashTable中所有Bucket都可以通过pListHead指向的双向链表来访问，因此遍历HashTable的实现也比较简单。这里值得一 提的是对当前遍历到的Bucket的处理使用了一个apply_func_t类型的回调函数。根据实际需要，该回调函数返回下面值之一：

• ZEND_HASH_APPLY_KEEP
• ZEND_HASH_APPLY_STOP
• ZEND_HASH_APPLY_REMOVE

它们分别表示继续遍历，停止遍历或删除相应元素后继续遍历。

还有一个要注意的问题就是遍历时的防止递归的问题，也就是防止对同一个HashTable同时进行多次遍历。这是用下面两个宏来实现的：

HASH_PROTECT_RECURSION(ht)
HASH_UNPROTECT_RECURSION(ht)

其主要原理是如果遍历保护标志bApplyProtection为真，则每次进入遍历函数时将nApplyCount值加1，退出遍历函数时将nApplyCount值减1。开始遍历之前如果发现nApplyCount > 3就直接报告错误信息并退出遍历。

上面的apply_func_t不带参数。HashTable还提供带一个参数或可变参数的回调方式，对应的遍历函数分别为:

typedef int (*apply_func_arg_t)(void *pDest,void *argument TSRMLS_DC);
void zend_hash_apply_with_argument(HashTable *ht,apply_func_arg_t apply_func, void *data TSRMLS_DC); 
typedef int (*apply_func_args_t)(void *pDest,int num_args, va_list args, zend_hash_key *hash_key);
void zend_hash_apply_with_arguments(HashTable *ht,apply_func_args_t apply_func, int numargs, …);

除了上面提供的几种提供外，还有许多其它操作HashTable的API。如排序、HashTable的拷贝与合并等等。只要充分理解了上述HashTable的数据结构，理解这些代码并不困难。