PHP 中的數(shù)組實(shí)際上是一個(gè)有序映射。映射是一種把 values 關(guān)聯(lián)到 keys 的類(lèi)型。--PHP手冊(cè)
數(shù)組是PHP中非常強(qiáng)大、靈活的一種數(shù)據(jù)類(lèi)型翁潘，它的底層實(shí)現(xiàn)為HashTable（哈希表)，除了我們熟悉的PHP用戶空間的Array類(lèi)型之外歼争，內(nèi)核中也隨處用到哈希表拜马，比如函數(shù)渗勘、類(lèi)、常量俩莽、include文件的索引表旺坠、全局符號(hào)表等都用的HashTable存儲(chǔ)。
1扮超、 數(shù)組結(jié)構(gòu)
PHP中HashTable的數(shù)據(jù)結(jié)構(gòu)如下：
//Bucket：散列表中存儲(chǔ)的元素
typedef struct _Bucket {
zval val; //存儲(chǔ)的具體value取刃，這里嵌入了一個(gè)zval，而不是一個(gè)指針
zend_ulong h; //key根據(jù)times 33計(jì)算得到的哈希值出刷，或者是數(shù)值索引編號(hào)
zend_string *key; //存儲(chǔ)元素的key
} Bucket;
//HashTable結(jié)構(gòu)
typedef struct _zend_array HashTable;
struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar reserve)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; //哈希值計(jì)算掩碼璧疗，等于nTableSize的負(fù)值(nTableMask = -nTableSize)
Bucket *arData; //存儲(chǔ)元素?cái)?shù)組，指向第一個(gè)Bucket
uint32_t nNumUsed; //已用Bucket數(shù)
uint32_t nNumOfElements; //哈希表有效元素?cái)?shù)
uint32_t nTableSize; //哈希表總大小馁龟，為2的n次方
uint32_t nInternalPointer;
zend_long nNextFreeElement; //下一個(gè)可用的數(shù)值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 則nNextFreeElement = 2;
dtor_func_t pDestructor;
};
注意：nNumUsed：已用bucket數(shù) nNumOfElements：哈希表有效元素?cái)?shù)
兩者有不同的含義崩侠，當(dāng)將一個(gè)元素從哈希表刪除時(shí)并不會(huì)將對(duì)應(yīng)的Bucket移除，而是將Bucket存儲(chǔ)的zval修改為IS_UNDEF坷檩，只有擴(kuò)容時(shí)發(fā)現(xiàn)nNumOfElements與nNumUsed相差達(dá)到一定數(shù)量時(shí)才會(huì)將已刪除的元素全部移除却音，重新構(gòu)建哈希表，所以 nNumUsed >= nNumOfElements矢炼。
HashTable中另外一個(gè)非常重要的值arData系瓢，這個(gè)值指向存儲(chǔ)元素?cái)?shù)組的第一個(gè)Bucket，插入元素時(shí)按順序依次插入數(shù)組句灌，比如第一個(gè)元素在arData[0]夷陋、第二個(gè)在arData[1] ... arData[nNumUsed]。PHP數(shù)組的有序性正是通過(guò)arData保證的胰锌。
所以肌稻，HashTable主要依賴arData實(shí)現(xiàn)元素的存儲(chǔ)、索引匕荸。插入一個(gè)元素時(shí)先將元素按先后順序插入Bucket數(shù)組，位置是idx枷邪，再根據(jù)key的哈希值映射到散列表中的某個(gè)位置nIndex榛搔，將idx存入這個(gè)位置；查找時(shí)先在哈希表中映射到nIndex东揣，得到value在Bucket數(shù)組的位置idx践惑，再?gòu)腂ucket數(shù)組中取出元素。
2嘶卧、 哈希碰撞
哈希碰撞是指不同的key可能計(jì)算得到相同的哈希值(數(shù)值索引的哈希值直接就是數(shù)值本身)尔觉，但是這些值又需要插入同一個(gè)哈希表。
出現(xiàn)哈希碰撞之后芥吟，又如何解決呢侦铜？一般有如下幾種方法：
鏈表法：為每個(gè) Hash 值建立一個(gè)單鏈表专甩，當(dāng)發(fā)生沖突時(shí)，將記錄插入到鏈表中钉稍。
開(kāi)放尋址法：有一個(gè)公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1),基本思想：當(dāng)發(fā)生地址沖突時(shí)涤躲，按照某種方法繼續(xù)探測(cè)哈希表中的其他存儲(chǔ)單元，直到找到空位置為止贡未。
再哈希法：當(dāng)發(fā)生沖突時(shí)种樱，使用第二個(gè)、第三個(gè)哈希函數(shù)計(jì)算地址俊卤，直到無(wú)沖突時(shí)嫩挤。
3、 擴(kuò)容
哈希表可存儲(chǔ)的value數(shù)是固定的消恍，當(dāng)空間不夠用時(shí)就要進(jìn)行擴(kuò)容了岂昭。
PHP哈希表的大小為2^n，插入時(shí)如果容量不夠則首先檢查已刪除元素所占比例哺哼，如果達(dá)到閾值時(shí)佩抹，則將已刪除元素移除，重建索引取董；如果未到閾值則進(jìn)行擴(kuò)容操作棍苹，擴(kuò)大為當(dāng)前大小的2倍，將當(dāng)前Bucket數(shù)組復(fù)制到新的空間茵汰，然后重建索引枢里。
4、重建散列表
當(dāng)刪除元素達(dá)到一定數(shù)量或擴(kuò)容后就需要重建哈希表蹂午，因?yàn)関alue在Bucket位置移動(dòng)了或哈希數(shù)組nTableSize變化了導(dǎo)致key與value的映射關(guān)系改變栏豺。
重建過(guò)程實(shí)際就是遍歷Bucket數(shù)組中的value，然后重新計(jì)算映射值更新到哈希表豆胸。
此外奥洼，還有一個(gè)重要的處理：移除已刪除的value，開(kāi)始的時(shí)候我們說(shuō)過(guò)晚胡，刪除value時(shí)只是將value的type設(shè)置為IS_UNDEF灵奖，并沒(méi)有實(shí)際從Bucket數(shù)組中刪除，如果這些value一直存在那么將浪費(fèi)很多空間估盘，所以這里會(huì)把它們移除瓷患，操作的方式也比較簡(jiǎn)單：將后面未刪除的value依次前移。
