哈希表
基本上，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)里砚著。
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;
- nNumOfElements
標(biāo)識(shí)現(xiàn)在存儲(chǔ)在數(shù)組里面的值的數(shù)量次伶。這也是函數(shù)count的返回值 - 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è)元素的位置炬丸。記滋鼻蕖：PHP的數(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ì)銷毀和釋放它汁蝶。
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ù)組類型要付出的代價(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文件里面定義了。現(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ù)類型是數(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里面存在的三步重要的部分：
Z_ARRVAL_P宏從zval里面提取值到哈希表。
zend_hash_num_elements提取哈希表元素的個(gè)數(shù)（nNumOfElements屬性）罢杉。
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) {
zend_hash_move_forward_ex(Z_ARRVAL_P(keys), &pos);
}
這可以很容易地翻譯成PHP代碼：
reset($keys);
while (null !== $entry = current($keys)) {
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類型轉(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í)銷毀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)槲覀儧](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)度。
