php底層HashTable的實(shí)現(xiàn)

codeKK 發(fā)布于2019-07-01 14:12 / 3009人閱讀

摘要：底層的實(shí)現(xiàn)有兩個(gè)非常重要的結(jié)構(gòu)分別是和。簡(jiǎn)單來(lái)說(shuō)就是哈希表的結(jié)構(gòu)維護(hù)了哈希表中插入元素的先后順序，哈希表結(jié)構(gòu)維護(hù)了整個(gè)哈希表的頭和尾。在操作哈希表的過(guò)程中始終保持預(yù)算之間的關(guān)系。

HashTable對(duì)PHP來(lái)說(shuō)是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。很多PHP的內(nèi)部實(shí)現(xiàn)（變量的作用域，函數(shù)表，類的屬性、方法，數(shù)組）就是通過(guò)HashTable來(lái)實(shí)現(xiàn)的。最近了解了一下PHP底層HashTable的實(shí)現(xiàn)。
PHP底層HashTable的實(shí)現(xiàn)有兩個(gè)非常重要的結(jié)構(gòu)分別是:HashTable和Bucket。
先說(shuō)一下HashTable結(jié)構(gòu):
HashTable的底層實(shí)現(xiàn)代碼如下:

typedef struct _hashtable{
    uint nTableSize;         // hash Bucket的大小，最小為8
    uint nTableMask;         //nTableSize - 1, 索引取值的優(yōu)化
    uint nNumofElements      // bucket 里面存的總數(shù) 
    ulong nNextFreeElement   //下一個(gè)數(shù)字索引的位置
    Bucket *pInternalPointer  //當(dāng)前遍歷的指針(foreach比較快的原因)
    Bucket *pListHead         //整個(gè)hashtable的頭指針
    Bucket *pListTail         //整個(gè)hashTable的尾指針
    Bucket **argBuckets       // Buceket 數(shù)組，用來(lái)存儲(chǔ)數(shù)據(jù)
    doctor_func_t pDestructor //刪除元素時(shí)的回調(diào)函數(shù)，用于資源的釋放
    zend_bool persistent      //Bucket的內(nèi)存分配方式，true使用系統(tǒng)的分配函數(shù)，false 使用php的內(nèi)存分配函數(shù)
    unsigned char nApplyCount //標(biāo)記當(dāng)前hash bucket 被遞歸的次數(shù)
    zend_bool bApplyProtection 
#if ZEND_DEBUG
    int inconsistent           
#endif 
}HashTable

建議不太了解hash數(shù)據(jù)結(jié)構(gòu)的同學(xué)先簡(jiǎn)單了解一下hash結(jié)構(gòu)。
簡(jiǎn)單說(shuō)一下php中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;
}

最開(kāi)始判斷需要初始化的hashtable大小是不是超過(guò)了系統(tǒng)能使用的最大大小。下面是對(duì)tablesize大小的一個(gè)處理。將用戶自定義的大小改成需要的大小。例如:如果用戶定義的hashtable大小是6，那初始化時(shí)，就會(huì)將6變成8，如果用戶定義的大小為11，那初始化后的Hashtable的大小為16.
下面就是一個(gè)簡(jiǎn)單的判斷，來(lái)決定是按照C語(yǔ)言本身的分配內(nèi)存函數(shù)來(lái)分配內(nèi)存，還是根據(jù)php封裝好的內(nèi)存分配函數(shù)來(lái)分配內(nèi)存。

再談一下 bucket的結(jié)構(gòu)

typedef struct bucket{
    ulong h;       //對(duì)key索引以后的值，數(shù)字key不做kash
    uint nKeyLength; //key的長(zhǎng)度
    void *pData;     
    void *pDataPtr;   //指針數(shù)據(jù)，指向真實(shí)數(shù)據(jù)
    struct bucket * pListNext; //整個(gè)hash表的下個(gè)元素
    struct bucket *pListLast;   //整個(gè)hash表的上個(gè)元素
    struct bucket *pNext;       //本bucket里面，下一個(gè)元素
    struct bucket *pLast;       //本bucket里面的上一個(gè)元素
    char arKey[1];
}Bucket

這里用一張網(wǎng)絡(luò)上的很火的圖來(lái)說(shuō)明(圖原地址沒(méi)找到，沒(méi)有做來(lái)源說(shuō)明):

下面是引用了tipi里面的插入說(shuō)明:
引用地址:tipi

  如圖中左下角的假設(shè)，假設(shè)依次插入了Bucket1，Bucket2，Bucket3三個(gè)元素：

  1、插入Bucket1時(shí)，哈希表為空，經(jīng)過(guò)哈希后定位到索引為1的槽位。此時(shí)的1槽位只有一個(gè)元素Bucket1。 其中Bucket1的pData或者pDataPtr指向的是Bucket1所存儲(chǔ)的數(shù)據(jù)。此時(shí)由于沒(méi)有鏈接關(guān)系。pNext， pLast，pListNext，pListLast指針均為空。同時(shí)在HashTable結(jié)構(gòu)體中也保存了整個(gè)哈希表的第一個(gè)元素指針， 和最后一個(gè)元素指針，此時(shí)HashTable的pListHead和pListTail指針均指向Bucket1。

  2、插入Bucket2時(shí)，由于Bucket2的key和Bucket1的key出現(xiàn)沖突，此時(shí)將Bucket2放在雙鏈表的前面。 由于Bucket2后插入并置于鏈表的前端，此時(shí)Bucket2.pNext指向Bucket1，由于Bucket2后插入。 Bucket1.pListNext指向Bucket2，這時(shí)Bucket2就是哈希表的最后一個(gè)元素，這是HashTable.pListTail指向Bucket2。3、插入Bucket3，該key沒(méi)有哈希到槽位1，這時(shí)Bucket2.pListNext指向Bucket3，因?yàn)锽ucket3后插入。 同時(shí)HashTable.pListTail改為指向Bucket3。

  簡(jiǎn)單來(lái)說(shuō)就是哈希表的Bucket結(jié)構(gòu)維護(hù)了哈希表中插入元素的先后順序，哈希表結(jié)構(gòu)維護(hù)了整個(gè)哈希表的頭和尾。 在操作哈希表的過(guò)程中始終保持預(yù)算之間的關(guān)系。