在Zend Engine中的HashTable的實(shí)現(xiàn)代碼主要包括zend_hash.h,和zend_hash.c這兩個(gè)文件中戳吝。Zend HashTable包括兩個(gè)主要的數(shù)據(jù)結(jié)構(gòu)，其一是Bucket（桶）結(jié)構(gòu)车酣，另一個(gè)是HashTable結(jié)構(gòu)。Bucket結(jié)構(gòu)是用于保存數(shù)據(jù)的容器醒陆，而 HashTable結(jié)構(gòu)則提供了對(duì)所有這些Bucket(或桶列)進(jìn)行管理的機(jī)制

1 數(shù)據(jù)結(jié)構(gòu)

typedef struct bucket {
    ulong h;                               /* Used for numeric indexing */
    uint nKeyLength;                       /* key 長度 */
    void *pData;                           /* 指向Bucket中保存的數(shù)據(jù)的指針 */
    void *pDataPtr;                        /* 指針數(shù)據(jù) */
    struct bucket *pListNext;              /* 指向HashTable桶列中下一個(gè)元素 */
    struct bucket *pListLast;              /* 指向HashTable桶列中前一個(gè)元素 */
    struct bucket *pNext;                  /* 指向具有同一個(gè)hash值的桶列的后一個(gè)元素 */
    struct bucket *pLast;                  /* 指向具有同一個(gè)hash值的桶列的前一個(gè)元素 */
    char arKey[1];                         /* 必須是最后一個(gè)成員躏吊，key名稱*/
} Bucket;

在Zend HashTable中，每個(gè)數(shù)據(jù)元素(Bucket)有一個(gè)鍵名(key)誊锭，它在整個(gè)HashTable中是唯一的，不能重復(fù)弥锄。根據(jù)鍵名可以唯一確定 HashTable中的數(shù)據(jù)元素丧靡。

鍵名有兩種表示方式:

• 使用字符串arKey作為鍵名，該字符串的長度為nKeyLength. 注意到在上面的 數(shù)據(jù)結(jié)構(gòu)中arKey雖然只是一個(gè)長度為1的字符數(shù)組籽暇，但它并不意味著key只能是一個(gè)字符窘行。實(shí)際上Bucket是一個(gè)可變長的結(jié)構(gòu)體，由于arKey是 Bucket的最后一個(gè)成員變量图仓，通過arKey與nKeyLength結(jié)合可確定一個(gè)長度為nKeyLength的key罐盔。這是C語言編程中的一個(gè)比較 常用的技巧。
• 索引方式救崔，這時(shí)nKeyLength總是0惶看，長整型字段h就表示該數(shù)據(jù)元素的鍵名。簡單的來說六孵，即如果nKeyLength=0纬黎，則鍵名為h；否則鍵名為arKey, 鍵名的長度為nKeyLength劫窒。

當(dāng)nKeyLength > 0時(shí)本今，并不表示這時(shí)的h值就沒有意義。事實(shí)上，此時(shí)它保存的是arKey對(duì)應(yīng)的hash值冠息。不管hash函數(shù)怎么設(shè)計(jì)挪凑，沖突都是不可避免的，也就是說不同 的arKey可能有相同的hash值逛艰。具有相同hash值的Bucket保存在HashTable的arBuckets數(shù)組(參考下面的解釋)的同一個(gè)索 引對(duì)應(yīng)的桶列中躏碳。這個(gè)桶列是一個(gè)雙向鏈表，其前向元素散怖，后向元素分別用pLast,pNext來表示菇绵。新插入的Bucket放在該桶列的最前面。

在Bucket中镇眷，實(shí)際的數(shù)據(jù)是保存在pData指針指向的內(nèi)存塊中咬最，通常這個(gè)內(nèi)存塊是系統(tǒng)另外分配的。但有一種情況例外欠动，就是當(dāng)Bucket保存 的數(shù)據(jù)是一個(gè)指針時(shí)丹诀，HashTable將不會(huì)另外請求系統(tǒng)分配空間來保存這個(gè)指針，而是直接將該指針保存到pDataPtr中翁垂，然后再將pData指向 本結(jié)構(gòu)成員的地址。這樣可以提高效率硝桩，減少內(nèi)存碎片沿猜。由此我們可以看到PHP HashTable設(shè)計(jì)的精妙之處。如果Bucket中的數(shù)據(jù)不是一個(gè)指針碗脊，pDataPtr為NULL啼肩。

HashTable中所有的Bucket通過pListNext, pListLast構(gòu)成了一個(gè)雙向鏈表。最新插入的Bucket放在這個(gè)雙向鏈表的最后衙伶。

注意在一般情況下祈坠，Bucket并不能提供它所存儲(chǔ)的數(shù)據(jù)大小的信息。所以在PHP的實(shí)現(xiàn)中矢劲，Bucket中保存的數(shù)據(jù)必須具有管理自身大小的能力赦拘。

typedef struct _hashtable {
    uint nTableSize;                  // hash Bucket的大小，最小為8芬沉，以2x增長
    uint nTableMask;                  // nTableSize-1 躺同， 索引取值的優(yōu)化
    uint nNumOfElements;              // hash Bucket中當(dāng)前存在的元素個(gè)數(shù)，count()函數(shù)會(huì)直接返回此值 
    ulong nNextFreeElement;           // 下一個(gè)數(shù)字索引的位置
    Bucket *pInternalPointer;         // 當(dāng)前遍歷的指針（foreach比for快的原因之一）
    Bucket *pListHead;                // 存儲(chǔ)數(shù)組頭元素指針
    Bucket *pListTail;                // 存儲(chǔ)數(shù)組尾元素指針
    Bucket **arBuckets;               // 存儲(chǔ)hash數(shù)組
    dtor_func_t pDestructor;          // 在刪除元素時(shí)執(zhí)行的回調(diào)函數(shù)丸逸，用于資源的釋放
    zend_bool persistent;             // 指出了Bucket內(nèi)存分配的方式蹋艺。如果persisient為TRUE，則使用操作系統(tǒng)本身的內(nèi)存分配函數(shù)為Bucket分配內(nèi)存黄刚，否則使用PHP的內(nèi)存分配函數(shù)捎谨。
    unsigned char nApplyCount;        // 標(biāo)記當(dāng)前hash Bucket被遞歸訪問的次數(shù)（防止多次遞歸）
    zend_bool bApplyProtection;       // 標(biāo)記當(dāng)前hash桶允許不允許多次訪問，不允許時(shí)，最多只能遞歸3次
#if ZEND_DEBUG
    int inconsistent;                 // 判斷hash是否一致
#endif
} HashTable;

在HashTable結(jié)構(gòu)中涛救，nTableSize指定了HashTable的大小畏邢，同時(shí)它限定了HashTable中能保存Bucket的最大數(shù)量，此 數(shù)越大州叠，系統(tǒng)為HashTable分配的內(nèi)存就越多棵红。為了提高計(jì)算效率，系統(tǒng)自動(dòng)會(huì)將nTableSize調(diào)整到最小一個(gè)不小于nTableSize的2 的整數(shù)次方咧栗。也就是說逆甜，如果在初始化HashTable時(shí)指定一個(gè)nTableSize不是2的整數(shù)次方，系統(tǒng)將會(huì)自動(dòng)調(diào)整nTableSize的值致板。即

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

例如交煞，如果在初始化HashTable的時(shí)候指定nTableSize = 11，HashTable初始化程序會(huì)自動(dòng)將nTableSize增大到16斟或。

arBuckets是HashTable的關(guān)鍵素征，HashTable初始化程序會(huì)自動(dòng)申請一塊內(nèi)存，并將其地址賦值給arBuckets萝挤，該內(nèi)存大 小正好能容納nTableSize個(gè)指針御毅。我們可以將arBuckets看作一個(gè)大小為nTableSize的數(shù)組，每個(gè)數(shù)組元素都是一個(gè)指針怜珍，用于指向 實(shí)際存放數(shù)據(jù)的Bucket端蛆。當(dāng)然剛開始時(shí)每個(gè)指針均為NULL。

nTableMask的值永遠(yuǎn)是nTableSize – 1酥泛，引入這個(gè)字段的主要目的是為了提高計(jì)算效率今豆，是為了快速計(jì)算Bucket鍵名在arBuckets數(shù)組中的索引。

nNumberOfElements記錄了HashTable當(dāng)前保存的數(shù)據(jù)元素的個(gè)數(shù)柔袁。當(dāng)nNumberOfElement大于nTableSize時(shí)呆躲，HashTable將自動(dòng)擴(kuò)展為原來的兩倍大小。

nNextFreeElement記錄HashTable中下一個(gè)可用于插入數(shù)據(jù)元素的arBuckets的索引捶索。

pListHead, pListTail則分別表示Bucket雙向鏈表的第一個(gè)和最后一個(gè)元素插掂，這些數(shù)據(jù)元素通常是根據(jù)插入的順序排列的。也可以通過各種排序函數(shù)對(duì)其進(jìn)行重 新排列腥例。pInternalPointer則用于在遍歷HashTable時(shí)記錄當(dāng)前遍歷的位置燥筷，它是一個(gè)指針，指向當(dāng)前遍歷到的Bucket院崇，初始值是 pListHead肆氓。

pDestructor是一個(gè)函數(shù)指針，在HashTable的增加底瓣、修改谢揪、刪除Bucket時(shí)自動(dòng)調(diào)用蕉陋，用于處理相關(guān)數(shù)據(jù)的清理工作。

persistent標(biāo)志位指出了Bucket內(nèi)存分配的方式拨扶。如果persisient為TRUE凳鬓，則使用操作系統(tǒng)本身的內(nèi)存分配函數(shù)為Bucket分配內(nèi)存，否則使用PHP的內(nèi)存分配函數(shù)患民。具體請參考PHP的內(nèi)存管理缩举。

nApplyCount與bApplyProtection結(jié)合提供了一個(gè)防止在遍歷HashTable時(shí)進(jìn)入遞歸循環(huán)時(shí)的一種機(jī)制。

inconsistent成員用于調(diào)試目的匹颤，只在PHP編譯成調(diào)試版本時(shí)有效仅孩。表示HashTable的狀態(tài)，狀態(tài)有四種：

|狀態(tài)值|含義|
|--|
|HT_IS_DESTROYING |正在刪除所有的內(nèi)容印蓖，包括arBuckets本身 |
|HT_IS_DESTROYED |已刪除辽慕，包括arBuckets本身|
|HT_CLEANING |正在清除所有的arBuckets指向的內(nèi)容，但不包括arBuckets本身|
|HT_OK |正常狀態(tài)赦肃，各種數(shù)據(jù)完全一致|

typedef struct _zend_hash_key {
    char *arKey;             /* hash元素key名稱 */
    uint nKeyLength;         /* hash 元素key長度 */
    ulong h;                 /* key計(jì)算出的hash值或直接指定的數(shù)值下標(biāo) */
} zend_hash_key;

現(xiàn)在來看zend_hash_key結(jié)構(gòu)就比較容易理解了溅蛉。它通過arKey, nKeyLength, h三個(gè)字段唯一確定了HashTable中的一個(gè)元素。

根據(jù)上面對(duì)HashTable相關(guān)數(shù)據(jù)結(jié)構(gòu)的解釋他宛，我們可以畫出HashTable的內(nèi)存結(jié)構(gòu)圖：

zend_hashtable.png

具體實(shí)現(xiàn)

hash的初始化

HashTable提供了一個(gè)zend_hash_init宏來完成HashTable的初始化操作船侧。實(shí)際上它是通過下面的內(nèi)部函數(shù)來實(shí)現(xiàn)的:

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)  { 
            /* 自動(dòng)調(diào)整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; 

    /* 根據(jù)persistent使用不同方式分配arBuckets內(nèi)存厅各，并將其所有指針初始化為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函數(shù)。但現(xiàn)PHP已強(qiáng)制使用DJBX33A算法讯检，因此實(shí)際上pHashFunction這個(gè)參數(shù)并不會(huì)用到，保留在這里只是為了與以前的代碼兼容卫旱。

增加人灼、插入和修改元素

向HashTable中添加一個(gè)新的元素最關(guān)鍵的就是要確定將這個(gè)元素插入到arBuckets數(shù)組中的哪個(gè)位置。根據(jù)上面對(duì)Bucket結(jié)構(gòu)鍵名 的解釋顾翼，我們可以知道有兩種方式向HashTable添加一個(gè)新的元素投放。

• 使用字符串作為鍵名來插入Bucket；
• 使用索引作為鍵名來插入Bucket, 具體又可以分為兩種情況：指定索引或不指定索引适贸，指定索引指的是強(qiáng)制將Bucket插入到指定的索引位置中灸芳；不指定索引 則將Bucket插入到nNextFreeElement對(duì)應(yīng)的索引位置中。

這幾種插入數(shù)據(jù)的方法實(shí)現(xiàn)比較類似拜姿，不同的只是定位Bucket的方法烙样。

修改HashTable中的數(shù)據(jù)的方法與增加數(shù)據(jù)的方法也很類似。

我們先看第一種使用字符串作為鍵名增加或修改Bucket的方法：

/**
* @desc 往ht里面添加/修改key-value蕊肥，只服務(wù)于關(guān)聯(lián)數(shù)組谒获，索引數(shù)組另有服務(wù)函數(shù)
* @param ht         : 哈希表
* @param arKey      : key 
* @param nKeyLength : key的長度
* @param pData      : value
* @param nDataSize  : value的長度
* @param pDest      : value為指針時(shí)的值
* @param flag       : 標(biāo)識(shí)新增還是修改  
*/
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表空間已經(jīng)分配過了
    CHECK_INIT(ht);

    // 計(jì)算當(dāng)前key的hash值
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        // hash表中有該節(jié)點(diǎn)
        // 這地方分了兩種情形（為什么分兩種情況呢批狱？裸准？？赔硫？）
        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的時(shí)候先將原先的指針內(nèi)存釋放
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                // UPDATE_DATA不負(fù)責(zé)釋放內(nèi)存
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                    *pDest = p->pData;
                }
                HANDLE_UNBLOCK_INTERRUPTIONS();
                return SUCCESS;
        }
        p = p->pNext;
    }
    
    // 執(zhí)行到這里炒俱，操作只能是增加一個(gè)節(jié)點(diǎn)了
    // 如果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是一個(gè)指針
        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 是跨過整個(gè)Bucket結(jié)構(gòu)體空間
        // 結(jié)構(gòu)體重的arKey存放的是他之后一個(gè)字節(jié)的地址
        // 而多分配的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;

    // 鏈入本桶內(nèi)的雙向鏈表中
    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();

    // 沒插入完成一個(gè) 判斷是否需要擴(kuò)容
    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
    return SUCCESS;
}

因?yàn)檫@個(gè)函數(shù)是使用字符串作為鍵名來插入數(shù)據(jù)的，因此它首先檢查nKeyLength的值是否大于0爪膊，如果不是的話就直接退出权悟。然后計(jì)算arKey對(duì)應(yīng)的 hash值h，將其與nTableMask按位與后得到一個(gè)無符號(hào)整數(shù)nIndex惊完。這個(gè)nIndex就是將要插入的Bucket在arBuckets數(shù) 組中的索引位置僵芹。

現(xiàn)在已經(jīng)有了arBuckets數(shù)組的一個(gè)索引，我們知道它包括的數(shù)據(jù)是一個(gè)指向Bucket的雙向鏈表的指針小槐。如果這個(gè)雙向鏈表不為空的話我們首先檢查 這個(gè)雙向鏈表中是否已經(jīng)包含了用字符串arKey指定的鍵名的Bucket拇派，這樣的Bucket如果存在，并且我們要做的操作是插入新Bucket(通過 flag標(biāo)識(shí))凿跳，這時(shí)就應(yīng)該報(bào)錯(cuò) – 因?yàn)樵?code>HashTable中鍵名不可以重復(fù)件豌。如果存在，并且是修改操作控嗜，則使用在HashTable中指定了析構(gòu)函數(shù)pDestructor對(duì)原來的 pData指向的數(shù)據(jù)進(jìn)行析構(gòu)操作茧彤；然后將用新的數(shù)據(jù)替換原來的數(shù)據(jù)即可成功返回修改操作。
如果在HashTable中沒有找到鍵名指定的數(shù)據(jù)疆栏，就將該數(shù)據(jù)封裝到Bucket中曾掂，然后插入HashTable。這里要注意的是如下的兩個(gè)宏：

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

前者是將該Bucket插入到指定索引的Bucket雙向鏈表中壁顶，后者是插入到整個(gè)HashTable的Bucket雙向鏈表中珠洗。兩者的插入方式也不同，前者是將該Bucket插入到雙向鏈表的最前面若专，后者是插入到雙向鏈表的最末端许蓖。

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

/**
* @desc 數(shù)字索引類型的key-value值添加
* @param ht        : 添加的hash表結(jié)構(gòu)
* @param  h        : key 新增時(shí) h 設(shè)置為0 更新時(shí)會(huì)透傳上層的h
* @param pData     : value
* @param nDataSize ：value的長度
* @param pDest     : 用于指向下一個(gè)元素
* @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為當(dāng)前保留的最大下標(biāo)
    // 如果是HASH_NEXT_INSERT, 兩種情況 
    // 1膊爪、更新已有值，此時(shí)(h < nNextFreeElement)嚎莉，定位到對(duì)應(yīng)的元素米酬，修改即可
    // 2、插入一個(gè)key-value對(duì)趋箩，此時(shí) (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設(shè)置為添加（添加到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();
            // 當(dāng)插入一個(gè)key-value對(duì)且key>nNextFreeElement時(shí)琼懊，及時(shí)修正nNextFreeElement值
            // 以保證下一個(gè)元素的下標(biāo)是當(dāng)前下標(biāo)+1
            // 這個(gè)地方挺有意思的，例如當(dāng)前已用下標(biāo)情況是 0, 1, 2, 3, 9
            // 那么插入一個(gè)下標(biāo)為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標(biāo)志指明當(dāng)前操作是HASH_NEXT_INSERT(不指定索引插入或修改), HASH_ADD(指定索引插入)還是HASH_UPDATE(指定索引修改)哼丈。由于這些操作的實(shí)現(xiàn)代碼基本相同，因此統(tǒng)一合并成了一個(gè)函數(shù)筛严，再用flag加以區(qū)分醉旦。本函數(shù)基本與前一個(gè)相同，不同的是如果確定插入到arBuckets數(shù)組中的索引的方法桨啃。如果操作是HASH_NEXT_INSERT车胡，則直接使用nNextFreeElement作為插入的索引。注意nNextFreeElement的值是如何使用和更新的照瘾。

訪問元素

HashTable用兩種方式來訪問元素:

• 使用字符串arKey的zend_hash_find()匈棘；
• 使用索引的訪問方式zend_hash_index_find();
  由于其實(shí)現(xiàn)的代碼很簡單，分析工作就留給讀者自已完成析命。

刪除元素

HashTable刪除數(shù)據(jù)均使用zend_hash_del_key_or_index()函數(shù)來完成主卫，其代碼也較為簡單，這里也不再詳細(xì)分析鹃愤。需要的是注意如何根據(jù)arKey或h來計(jì)算出相應(yīng)的下標(biāo)簇搅，以及兩個(gè)雙向鏈表的指針的處理。

遍歷元素

/* 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);
}

因?yàn)?code>HashTable中所有Bucket都可以通過pListHead指向的雙向鏈表來訪問软吐，因此遍歷HashTable的實(shí)現(xiàn)也比較簡單瘩将。這里值得一 提的是對(duì)當(dāng)前遍歷到的Bucket的處理使用了一個(gè)apply_func_t類型的回調(diào)函數(shù)。根據(jù)實(shí)際需要凹耙，該回調(diào)函數(shù)返回下面值之一：

• ZEND_HASH_APPLY_KEEP
• ZEND_HASH_APPLY_STOP
• ZEND_HASH_APPLY_REMOVE

它們分別表示繼續(xù)遍歷姿现，停止遍歷或刪除相應(yīng)元素后繼續(xù)遍歷。

還有一個(gè)要注意的問題就是遍歷時(shí)的防止遞歸的問題肖抱，也就是防止對(duì)同一個(gè)HashTable同時(shí)進(jìn)行多次遍歷备典。這是用下面兩個(gè)宏來實(shí)現(xiàn)的：

HASH_PROTECT_RECURSION(ht)
HASH_UNPROTECT_RECURSION(ht)

其主要原理是如果遍歷保護(hù)標(biāo)志bApplyProtection為真，則每次進(jìn)入遍歷函數(shù)時(shí)將nApplyCount值加1虐沥，退出遍歷函數(shù)時(shí)將nApplyCount值減1熊经。開始遍歷之前如果發(fā)現(xiàn)nApplyCount > 3就直接報(bào)告錯(cuò)誤信息并退出遍歷泽艘。

上面的apply_func_t不帶參數(shù)欲险。HashTable還提供帶一個(gè)參數(shù)或可變參數(shù)的回調(diào)方式，對(duì)應(yīng)的遍歷函數(shù)分別為:

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的數(shù)據(jù)結(jié)構(gòu)喜每，理解這些代碼并不困難务唐。