PHP 數(shù)組的內(nèi)部實(shí)現(xiàn)

哈希表

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

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

什么是哈希表

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

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

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

HashTable和Bucket

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;
} HashTable;

  1. nNumOfElements
    標(biāo)識(shí)現(xiàn)在存儲(chǔ)在數(shù)組里面的值的數(shù)量。這也是函數(shù)count的返回值
  2. nTableSize
    表示哈希表的容量。它通常是下一個(gè)大于等于nNumOfElements的2的冪值。比如，如果數(shù)組存儲(chǔ)了32元素，那么哈希表也是32大小的容量。但如果再多一個(gè)元素添加進(jìn)來，也就是說，數(shù)組現(xiàn)在有33個(gè)元素，那么哈希表的容量就被調(diào)整為64。 這是為了保持哈希表在空間和時(shí)間上始終有效。很明顯，如果哈希表太小，那么將會(huì)有很多的沖突，而且性能也會(huì)降低。另一方面，如果哈希表太大，那么浪費(fèi)內(nèi)存。2的冪值是一個(gè)很好的折中方案。
  3. nTableMask
    是哈希表的容量減一。這個(gè)mask用來根據(jù)當(dāng)前的表大小調(diào)整生成的哈希值。例如，”foo”真正的哈希值（使用DJBX33A哈希函數(shù)）是193491849。如果我們現(xiàn)在有64容量的哈希表，我們明顯不能使用它作為數(shù)組的下標(biāo)。取而代之的是通過應(yīng)用哈希表的mask，然后只取哈希表的低位。
    hash | 193491849 | 0b1011100010000111001110001001
    & mask | & 63 | & 0b0000000000000000000000111111
    = index | = 9 | = 0b0000000000000000000000001001
  4. nNextFreeElement
    是下一個(gè)可以使用的數(shù)字鍵值，當(dāng)你使用$array[] = xyz是被使用到。
  5. pInternalPointer
    存儲(chǔ)數(shù)組當(dāng)前的位置。這個(gè)值在foreach遍歷時(shí)可使用reset()，current()，key()，next()，prev()和end()函數(shù)訪問。
  6. pListHead和pListTail
    標(biāo)識(shí)了數(shù)組的第一個(gè)和最后一個(gè)元素的位置。記住：PHP的數(shù)組是有序集合。比如，[‘foo’ => ‘bar’, ‘bar’ => ‘foo’]和[‘bar’ => ‘foo’, ‘foo’ => ‘bar’]這兩個(gè)數(shù)組包含了相同的元素，但卻有不同的順序。
  7. arBuckets
    是我們經(jīng)常談?wù)摰摹肮１恚╥nternal C array）”。它用Bucket **來定義，因此它可以被看作數(shù)組的bucket指針（我們會(huì)馬上談?wù)揃ucket是什么）。
  8. pDestructor
    是值的析構(gòu)器。如果一個(gè)值從HT中移除，那么這個(gè)函數(shù)會(huì)被調(diào)用。常見的析構(gòu)函數(shù)是zval_ptr_dtor。zval_ptr_dtor會(huì)減少zval的引用數(shù)量，而且，如果它遇到o，它會(huì)銷毀和釋放它。

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;

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

  2. arKey
    用來保存字符串鍵值。

  3. nKeyLength
    是對(duì)應(yīng)的長度。如果是數(shù)字鍵值，那么這兩個(gè)變量都不會(huì)被使用。

  4. pData
    及

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

  6. pListNext
    和

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

  8. pNext
    和

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

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

哈希表是怎么被使用的？

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

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

使用第二部分提到的技巧你可以很容易地找到函數(shù)在
ext/standard/array.c文件里面定義了?，F(xiàn)在，讓我們來快速查看這個(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ù)說明第一個(gè)參數(shù)類型是數(shù)組（即變量keys），第二個(gè)參數(shù)是任意的zval（即變量val）。

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

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ù)組一樣大小來初始化數(shù)組到return_value變量里。

這里的size只是一種優(yōu)化方案。函數(shù)也可以只調(diào)用
array_init(return_value)，這樣隨著越來越多的元素添加到數(shù)組里，PHP就會(huì)多次重置數(shù)組的大小。通過指定特定的大小，PHP會(huì)在一開始就分配正確的內(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) {
zend_hash_move_forward_ex(Z_ARRVAL_P(keys), &pos);
}

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

reset(keys); while (null !==entry = current(keys)) { next(keys);
}

跟下面的一樣：

foreach (keys asentry) {
// some code
}

唯一不同的是，C的遍歷并沒有使用內(nèi)部的數(shù)組指針，而使用它自己的pos變量來存儲(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);

這看起來太直接了：首先值的引用增加了（添加值到哈希表意味著增加另一個(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類型轉(zhuǎn)換不會(huì)改變?cè)瓉淼臄?shù)組。如果沒有copy操作，強(qiáng)制轉(zhuǎn)換不僅僅修改局部的變量，而且也修改了在鍵值數(shù)組中的值（顯然，這對(duì)用戶來說非常意外）。

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

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

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，而傳遞的是鍵值字符串和它的長度。

來自：https://blog.csdn.net/u010412301/article/details/53983452
另外一篇參考：
https://segmentfault.com/a/1190000018720188

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容