成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

codeKK / 3016人閱讀

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

HashTable對PHP來說是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。很多PHP的內(nèi)部實(shí)現(xiàn)（變量的作用域，函數(shù)表，類的屬性、方法，數(shù)組）就是通過HashTable來實(shí)現(xiàn)的。最近了解了一下PHP底層HashTable的實(shí)現(xiàn)。
PHP底層HashTable的實(shí)現(xiàn)有兩個(gè)非常重要的結(jié)構(gòu)分別是:HashTable和Bucket。
先說一下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ù)組，用來存儲數(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é)先簡單了解一下hash結(jié)構(gòu)。
簡單說一下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;
}

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

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

typedef struct bucket{
    ulong h;       //對key索引以后的值，數(shù)字key不做kash
    uint nKeyLength; //key的長度
    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ò)上的很火的圖來說明(圖原地址沒找到，沒有做來源說明):

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

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


  
1、插入Bucket1時(shí)，哈希表為空，經(jīng)過哈希后定位到索引為1的槽位。此時(shí)的1槽位只有一個(gè)元素Bucket1。 其中Bucket1的pData或者pDataPtr指向的是Bucket1所存儲的數(shù)據(jù)。此時(shí)由于沒有鏈接關(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沒有哈希到槽位1，這時(shí)Bucket2.pListNext指向Bucket3，因?yàn)锽ucket3后插入。 同時(shí)HashTable.pListTail改為指向Bucket3。

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/31884.html

相關(guān)文章

  • php底層原理之類和對象

    摘要：所以想要理解更深入的同學(xué)最好查看下我之前的關(guān)于介紹變量函數(shù)的文章類的數(shù)據(jù)結(jié)構(gòu)不管是普通類還是抽象類或是接口，都存放到統(tǒng)一的結(jié)構(gòu)體中，并且在生成中間代碼時(shí)，會將此類添加到全局類列表中。 對于PHPer來說，OOP是不可或缺的開發(fā)思維，但是你對php類和對象的底層實(shí)現(xiàn)又了解多少呢？本著知其然且知其所以然的思想，讓我們一起來尋找答案~ 類的底層實(shí)現(xiàn)可看作是之前我們講過的變量、函數(shù)等的知識集合...

    isaced 評論0 收藏0

  • PHP_底層分析

    摘要：將會產(chǎn)生強(qiáng)制分裂結(jié)構(gòu)體結(jié)構(gòu)體引用數(shù)組時(shí)的一些奇怪現(xiàn)象引用數(shù)組時(shí)的怪現(xiàn)象數(shù)組不會比較細(xì)致的檢查，多維數(shù)組存在。因此，判斷的時(shí)候，只會判斷外面一層的結(jié)構(gòu)體。中底層都離不開表。底層所有的變量都是放在中。 PHP編譯特點(diǎn) 編譯型語言 對于C語言，C++，編譯成機(jī)器碼(二進(jìn)制)來運(yùn)行。Java語言，把.java 編譯成.class， 稱為bytecode(字節(jié)碼)，由jvm來運(yùn)行 解釋型語言 解...

    tomlingtm 評論0 收藏0

  • 【天贏金創(chuàng)】PHP7與Swoole

    摘要：但在密集計(jì)算方面比等靜態(tài)編譯語言差幾十倍甚至上百倍。一使用棧內(nèi)存在引擎和擴(kuò)展中，經(jīng)常要?jiǎng)?chuàng)建一個(gè)的變量，底層就是一個(gè)指針。代碼中創(chuàng)建的變量也進(jìn)行了優(yōu)化，直接在棧內(nèi)存上預(yù)分配。應(yīng)用層與底層在錯(cuò)誤拋出的方式全部統(tǒng)一為異常。 原文：http://rango.swoole.com/archives/440最近PHP官方終于發(fā)布了傳說中的PHP7，雖然只是alpha版。PHP7號稱是新一代的PHP...

    MingjunYang 評論0 收藏0

  • php底層原理之?dāng)?shù)組實(shí)現(xiàn)

    摘要：數(shù)組是最常用的數(shù)據(jù)類型，同時(shí)容易上手也得益于其強(qiáng)大的數(shù)組，但是數(shù)組在中是如何實(shí)現(xiàn)的呢首先，我們還是先了解下相關(guān)的數(shù)據(jù)結(jié)構(gòu)，為下面的內(nèi)容打好基礎(chǔ)哈希表哈希表，顧名思義，即將不同的關(guān)鍵字映射到不同單元的一種數(shù)據(jù)結(jié)構(gòu)。 數(shù)組是PHPer最常用的數(shù)據(jù)類型，同時(shí)php容易上手也得益于其強(qiáng)大的數(shù)組，但是數(shù)組在php中是如何實(shí)現(xiàn)的呢？ 首先，我們還是先了解下相關(guān)的數(shù)據(jù)結(jié)構(gòu)，為下面的內(nèi)容打好基礎(chǔ) 哈希...

    HackerShell 評論0 收藏0

  • php中的哈希碰撞以及防御

    php中的哈希表 php中的變量是以符號表的方式進(jìn)行存儲的，實(shí)際上也是個(gè)HashTable，哈希表是通過特定的哈希算法將索引轉(zhuǎn)換成特定的index然后映射到對應(yīng)的槽中，然后采用拉鏈法，在一個(gè)槽中使用鏈表將數(shù)據(jù)進(jìn)行存儲，鏈表的時(shí)間復(fù)雜度為O(n)。 php中的hashtable的結(jié)構(gòu)定義在Zend/zend_hash.h文件中： //保存數(shù)據(jù)的單鏈表結(jié)構(gòu) typedef struct bucket ...

    周國輝 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<