摘要：為了防止你錯(cuò)過(guò)了之前的文章，以下是鏈接第一部分給開(kāi)發(fā)者的源碼源碼結(jié)構(gòu)第二部分理解內(nèi)部函數(shù)的定義第三部分的變量實(shí)現(xiàn)所有的東西都是哈希表基本上，里面的所有東西都是哈希表。哈希后的結(jié)果可以被作為正常的數(shù)組的鍵值又名為內(nèi)存塊。表示哈希表的容量。

文章來(lái)自：http://www.hoohack.me/2016/02/15/understanding-phps-internal-array-implementation-ch
原文：https://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html

歡迎來(lái)到"給PHP開(kāi)發(fā)者的PHP源碼"系列的第四部分，這一部分我們會(huì)談?wù)揚(yáng)HP數(shù)組在內(nèi)部是如何表示和在代碼庫(kù)里使用的。

為了防止你錯(cuò)過(guò)了之前的文章，以下是鏈接：

第一部分：給PHP開(kāi)發(fā)者的PHP源碼-源碼結(jié)構(gòu)

第二部分：理解PHP內(nèi)部函數(shù)的定義

第三部分：PHP的變量實(shí)現(xiàn)

基本上，PHP里面的所有東西都是哈希表。不僅僅是在下面的PHP數(shù)組實(shí)現(xiàn)中，它們還用來(lái)存儲(chǔ)對(duì)象屬性，方法，函數(shù)，變量還有幾乎所有東西。

因?yàn)楣１韺?duì)PHP來(lái)說(shuō)太基礎(chǔ)了，因此非常值得深入研究它是如何工作的。

記住，在C里面，數(shù)組是內(nèi)存塊，你可以通過(guò)下標(biāo)訪問(wèn)這些內(nèi)存塊。因此，在C里面的數(shù)組只能使用整數(shù)且有序的鍵值（那就是說(shuō)，你不能在鍵值0之后使用1332423442的鍵值）。C里面沒(méi)有關(guān)聯(lián)數(shù)組這種東西。

哈希表是這樣的東西：它們使用哈希函數(shù)轉(zhuǎn)換字符串鍵值為正常的整型鍵值。哈希后的結(jié)果可以被作為正常的C數(shù)組的鍵值（又名為內(nèi)存塊）。現(xiàn)在的問(wèn)題是，哈希函數(shù)會(huì)有沖突，那就是說(shuō)，多個(gè)字符串鍵值可能會(huì)生成一樣的哈希值。例如，在PHP，超過(guò)64個(gè)元素的數(shù)組里，字符串"foo"和"oof"擁有一樣的哈希值。

這個(gè)問(wèn)題可以通過(guò)存儲(chǔ)可能沖突的值到鏈表中，而不是直接將值存儲(chǔ)到生成的下標(biāo)里。

那么，現(xiàn)在哈希表的基本概念已經(jīng)清晰了，讓我們看看在PHP內(nèi)部中實(shí)現(xiàn)的哈希表結(jié)構(gòu)：

typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
     #if ZEND_DEBUG
        int inconsistent;
     #endif
} HashTable;

nNumOfElements標(biāo)識(shí)現(xiàn)在存儲(chǔ)在數(shù)組里面的值的數(shù)量。這也是函數(shù)count($array)返回的值。

nTableSize表示哈希表的容量。它通常是下一個(gè)大于等于nNumOfElements的2的冪值。比如，如果數(shù)組存儲(chǔ)了32元素，那么哈希表也是32大小的容量。但如果再多一個(gè)元素添加進(jìn)來(lái)，也就是說(shuō)，數(shù)組現(xiàn)在有33個(gè)元素，那么哈希表的容量就被調(diào)整為64。

這是為了保持哈希表在空間和時(shí)間上始終有效。很明顯，如果哈希表太小，那么將會(huì)有很多的沖突，而且性能也會(huì)降低。另一方面，如果哈希表太大，那么浪費(fèi)內(nèi)存。2的冪值是一個(gè)很好的折中方案。

nTableMask是哈希表的容量減一。這個(gè)mask用來(lái)根據(jù)當(dāng)前的表大小調(diào)整生成的哈希值。例如，"foo"真正的哈希值（使用DJBX33A哈希函數(shù)）是193491849。如果我們現(xiàn)在有64容量的哈希表，我們明顯不能使用它作為數(shù)組的下標(biāo)。取而代之的是通過(guò)應(yīng)用哈希表的mask，然后只取哈希表的低位。

hash           |        193491849 |     0b1011100010000111001110001001
& mask         | &             63 | &   0b0000000000000000000000111111
---------------------------------------------------------
= index        | = 9              | =   0b0000000000000000000000001001

nNextFreeElement是下一個(gè)可以使用的數(shù)字鍵值，當(dāng)你使用$array[] = xyz是被使用到。

pInternalPointer 存儲(chǔ)數(shù)組當(dāng)前的位置。這個(gè)值在foreach遍歷時(shí)可使用reset()，current()，key()，next()，prev()和end()函數(shù)訪問(wèn)。

pListHead和pListTail標(biāo)識(shí)了數(shù)組的第一個(gè)和最后一個(gè)元素的位置。記?。篜HP的數(shù)組是有序集合。比如，["foo" => "bar", "bar" => "foo"]和["bar" => "foo", "foo" => "bar"]這兩個(gè)數(shù)組包含了相同的元素，但卻有不同的順序。

arBuckets是我們經(jīng)常談?wù)摰摹肮１恚╥nternal C array）”。它用Bucket **來(lái)定義，因此它可以被看作數(shù)組的bucket指針（我們會(huì)馬上談?wù)揃ucket是什么）。

pDestructor是值的析構(gòu)器。如果一個(gè)值從HT中移除，那么這個(gè)函數(shù)會(huì)被調(diào)用。常見(jiàn)的析構(gòu)函數(shù)是zval_ptr_dtor。zval_ptr_dtor會(huì)減少zval的引用數(shù)量，而且，如果它遇到o，它會(huì)銷(xiāo)毀和釋放它。

最后的四個(gè)變量對(duì)我們來(lái)說(shuō)不是那么重要。所以簡(jiǎn)單地說(shuō)persistent標(biāo)識(shí)哈希表可以在多個(gè)請(qǐng)求里存活，nApplyCount和bApplyProtection防止多次遞歸，inconsistent用來(lái)捕獲在調(diào)試模式里哈希表的非法使用。

讓我們繼續(xù)第二個(gè)重要的結(jié)構(gòu)：Bucket：

typedef struct bucket {
    ulong h;
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey;
} Bucket;

h是一個(gè)哈希值（沒(méi)有應(yīng)用mask值映射之前的值）。

arKey用來(lái)保存字符串鍵值。nKeyLength是對(duì)應(yīng)的長(zhǎng)度。如果是數(shù)字鍵值，那么這兩個(gè)變量都不會(huì)被使用。

pData及pDataPtr被用來(lái)存儲(chǔ)真正的值。對(duì)PHP數(shù)組來(lái)說(shuō)，它的值是一個(gè)zval結(jié)構(gòu)體（但它也在其他地方使用到）。不要糾結(jié)為什么有兩個(gè)屬性。它們兩者的區(qū)別是誰(shuí)負(fù)責(zé)釋放值。

pListNext和pListLast標(biāo)識(shí)數(shù)組元素的下一個(gè)元素和上一個(gè)元素。如果PHP想順序遍歷數(shù)組它會(huì)從pListHead這個(gè)bucket開(kāi)始（在HashTable結(jié)構(gòu)里面），然后使用pListNext bucket作為遍歷指針。在逆序也是一樣，從pListTail指針開(kāi)始，然后使用pListLast指針作為變量指針。（你可以在用戶代碼里調(diào)用end()然后調(diào)用prev()函數(shù)達(dá)到這個(gè)效果。）

pNext和pLast生成我上面提到的“可能沖突的值鏈表”。arBucket數(shù)組存儲(chǔ)第一個(gè)可能值的bucket。如果該bucket沒(méi)有正確的鍵值，PHP會(huì)查找pNext指向的bucket。它會(huì)一直指向后面的bucket直到找到正確的bucket。pLast在逆序中也是一樣的原理。

你可以看到，PHP的哈希表實(shí)現(xiàn)相當(dāng)復(fù)雜。這是它使用超靈活的數(shù)組類(lèi)型要付出的代價(jià)。

Zend Engine定義了大量的API函數(shù)供哈希表使用。低級(jí)的哈希表函數(shù)預(yù)覽可以在zend_hash.h文件里面找到。另外Zend Engine在zend_API.h文件定義了稍微高級(jí)一些的API。

我們沒(méi)有足夠的時(shí)間去講所有的函數(shù)，但是我們至少可以查看一些實(shí)例函數(shù)，看看它是如何工作的。我們將使用array_fill_keys作為實(shí)例函數(shù)。

使用第二部分提到的技巧你可以很容易地找到函數(shù)在ext/standard/array.c文件里面定義了?，F(xiàn)在，讓我們來(lái)快速查看這個(gè)函數(shù)。

跟大部分函數(shù)一樣，函數(shù)的頂部有一堆變量的定義，然后調(diào)用zend_parse_parameters函數(shù)：

zval *keys, *val, **entry;
HashPosition pos;

if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "az", &keys, &val) == FAILURE) {
    return;
}

很明顯，az參數(shù)說(shuō)明第一個(gè)參數(shù)類(lèi)型是數(shù)組（即變量keys），第二個(gè)參數(shù)是任意的zval（即變量val）。

解析完參數(shù)后，返回?cái)?shù)組就被初始化了：

/* Initialize return array */
array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(keys)));

這一行包含了array API里面存在的三步重要的部分：

1、Z_ARRVAL_P宏從zval里面提取值到哈希表。

2、zend_hash_num_elements提取哈希表元素的個(gè)數(shù)（nNumOfElements屬性）。

3、array_init_size使用size變量初始化數(shù)組。

因此，這一行使用與鍵值數(shù)組一樣大小來(lái)初始化數(shù)組到return_value變量里。

這里的size只是一種優(yōu)化方案。函數(shù)也可以只調(diào)用array_init(return_value)，這樣隨著越來(lái)越多的元素添加到數(shù)組里，PHP就會(huì)多次重置數(shù)組的大小。通過(guò)指定特定的大小，PHP會(huì)在一開(kāi)始就分配正確的內(nèi)存空間。

數(shù)組被初始化并返回后，函數(shù)用跟下面大致相同的代碼結(jié)構(gòu)，使用while循環(huán)變量keys數(shù)組：

zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(keys), &pos);
while (zend_hash_get_current_data_ex(Z_ARRVAL_P(keys), (void **)&entry, &pos) == SUCCESS) {
    // some code

    zend_hash_move_forward_ex(Z_ARRVAL_P(keys), &pos);
}

這可以很容易地翻譯成PHP代碼：

reset($keys);
while (null !== $entry = current($keys)) {
    // some code

    next($keys);
}

跟下面的一樣：

foreach ($keys as $entry) {
    // some code
}

唯一不同的是，C的遍歷并沒(méi)有使用內(nèi)部的數(shù)組指針，而使用它自己的pos變量來(lái)存儲(chǔ)當(dāng)前的位置。

在循環(huán)里面的代碼分為兩個(gè)分支：一個(gè)是給數(shù)字鍵值，另一個(gè)是其他鍵值。數(shù)字鍵值的分支只有下面的兩行代碼：

zval_add_ref(&val);
zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_PP(entry), &val, sizeof(zval *), NULL);

這看起來(lái)太直接了：首先值的引用增加了（添加值到哈希表意味著增加另一個(gè)指向它的引用），然后值被插入到哈希表中。zend_hash_index_update宏的參數(shù)分別是，需要更新的哈希表Z_ARRVAL_P(return_value)，整型下標(biāo)Z_LVAL_PP(entry)，值&val，值的大小sizeof(zval *)以及目標(biāo)指針(這個(gè)我們不關(guān)注，因此是NULL）。

非數(shù)字下標(biāo)的分支就稍微復(fù)雜一點(diǎn)：

zval key, *key_ptr = *entry;

if (Z_TYPE_PP(entry) != IS_STRING) {
    key = **entry;
    zval_copy_ctor(&key);
    convert_to_string(&key);
    key_ptr = &key;
}

zval_add_ref(&val);
zend_symtable_update(Z_ARRVAL_P(return_value), Z_STRVAL_P(key_ptr), Z_STRLEN_P(key_ptr) + 1, &val, sizeof(zval *),             NULL);

if (key_ptr != *entry) {
    zval_dtor(&key);
}

首先，使用convert_to_string將鍵值轉(zhuǎn)換為字符串（除非它已經(jīng)是字符串了）。在這之前，entry被復(fù)制到新的key變量。key = **entry這一行實(shí)現(xiàn)。另外，zval_copy_ctor函數(shù)會(huì)被調(diào)用，不然復(fù)雜的結(jié)構(gòu)（比如字符串或數(shù)組）不會(huì)被正確地復(fù)制。

上面的復(fù)制操作非常有必要，因?yàn)橐ＷC類(lèi)型轉(zhuǎn)換不會(huì)改變?cè)瓉?lái)的數(shù)組。如果沒(méi)有copy操作，強(qiáng)制轉(zhuǎn)換不僅僅修改局部的變量，而且也修改了在鍵值數(shù)組中的值（顯然，這對(duì)用戶來(lái)說(shuō)非常意外）。

顯然，循環(huán)結(jié)束之后，復(fù)制操作需要再次被移除，zval_dtor(&key)做的就是這個(gè)工作。zval_ptr_dtor和zval_dtor的不同是zval_ptr_dtor只會(huì)在refcount變量為0時(shí)銷(xiāo)毀zval變量，而zval_dtor會(huì)馬上銷(xiāo)毀它，而不是依賴(lài)refcount的值。這就為什么你看到zval_pte_dtor使用"normal"變量而zval_dtor使用臨時(shí)變量，這些臨時(shí)變量不會(huì)在其他地方使用。而且，zval_ptr_dtor會(huì)在銷(xiāo)毀之后釋放zval的內(nèi)容而zval_dtor不會(huì)。因?yàn)槲覀儧](méi)有malloc()任何東西，因此我們也不需要free()，因此在這方面，zval_dtor做了正確的選擇。

現(xiàn)在來(lái)看看剩下的兩行（重要的兩行^^）：

zval_add_ref(&val);
zend_symtable_update(Z_ARRVAL_P(return_value), Z_STRVAL_P(key_ptr), Z_STRLEN_P(key_ptr) + 1, &val, sizeof(zval *), NULL);

這跟數(shù)字鍵值分支完成后的操作非常相似。不同的是，現(xiàn)在調(diào)用的是zend_symtable_update而不是zend_hash_index_update，而傳遞的是鍵值字符串和它的長(zhǎng)度。

"正常的"插入字符串鍵值到哈希表的函數(shù)是zend_hash_update，但這里卻使用了zend_symtable_update。它們有什么不同呢？

符號(hào)表簡(jiǎn)單地說(shuō)就是哈希表的特殊的類(lèi)型，這種類(lèi)型使用在數(shù)組里。它跟原始的哈希表不同的是他如何處理數(shù)字型的鍵值：在符號(hào)表里，"123"和123被看作是相同的。因此，如果你在$array["123"]存儲(chǔ)一個(gè)值，你可以在后面使用$array[123]獲取它。

底層可以使用兩種方式實(shí)現(xiàn)：要么使用"123"來(lái)保存123和"123"，要么使用123來(lái)保存這兩種鍵值。顯然PHP選擇了后者（因?yàn)檎捅茸址?lèi)型更快和占用更少的空間）。

如果你不小心使用"123"而不是強(qiáng)制轉(zhuǎn)換為123后插入數(shù)據(jù)，你會(huì)發(fā)現(xiàn)符號(hào)表一些有趣的事情。一個(gè)利用數(shù)組到對(duì)象的強(qiáng)制轉(zhuǎn)換如下：

$obj = new stdClass;
$obj->{123} = "foo";
$arr = (array) $obj;
var_dump($arr[123]); // Undefined offset: 123
var_dump($arr["123"]); // Undefined offset: 123

對(duì)象屬性總是使用字符串鍵值來(lái)保存，盡管它們是數(shù)字。因此$obj->{123} = "foo"這行代碼實(shí)際上保存"foo"變量到"123"下標(biāo)里。當(dāng)使用數(shù)組強(qiáng)制轉(zhuǎn)換的時(shí)候，這個(gè)值不會(huì)給改變。但當(dāng)$arr[123]和$arr["123"]都想訪問(wèn)123下標(biāo)的值（不是已有的"123"下標(biāo)）時(shí)，都拋出了錯(cuò)誤。因此，恭喜，你創(chuàng)建了一個(gè)隱藏的數(shù)組元素。

下一部分會(huì)再次在ircmaxell的博客發(fā)表。下一篇會(huì)介紹對(duì)象和類(lèi)在內(nèi)部是如何工作的。