PHP 數(shù)組的底層主要是通過 HashTable 實(shí)現(xiàn)，HashTable 通過映射函數(shù)或者散列函數(shù)將 String Key 轉(zhuǎn)換成一個(gè)普通的數(shù)字下標(biāo)，然后再將 Value 值存儲(chǔ)到下標(biāo)對應(yīng)的數(shù)組元素中

HashTable 主要包含兩部分：1.存儲(chǔ)元素的數(shù)組 2.散列函數(shù)或者映射函數(shù)

隨機(jī)訪問
如果我們指定一個(gè) Key=>Value 的映射關(guān)系，Key 是一個(gè) String 類型的，則先通過 Time 33 算法將 String 轉(zhuǎn)換成一個(gè) Int 整型，然后再通過 PHP 里面特定的散列算法映射成 Bucket 數(shù)組中的一個(gè)下標(biāo)，將 Value 值存儲(chǔ)到對應(yīng)的下標(biāo)元素中，當(dāng)我們通過 Key 訪問數(shù)組元素時(shí)，只需要再通過相同的算法計(jì)算出對應(yīng)的 Key,就能實(shí)現(xiàn)隨機(jī)訪問數(shù)組元素

順序訪問
存儲(chǔ)在 HashTable 中的數(shù)組是無序的，但是 PHP 中的數(shù)組是有序的，為了實(shí)現(xiàn) HashTable 的有序性，PHP 引入了一個(gè)中間映射表，該表是一個(gè)大小和 Bucket 數(shù)組相同的數(shù)組，數(shù)組中存放的是整形數(shù)據(jù)，主要用于存放元素實(shí)際存儲(chǔ)的 Value 的下標(biāo)值，當(dāng)引入中間映射表之后，Bucket 中的數(shù)據(jù)是有序的，而中間映射表中的數(shù)據(jù)是無序的，當(dāng)我們順序訪問的時(shí)候只需要遍歷 Bucket 中的數(shù)據(jù)即可

Hash 沖突
PHP 解決 Hash 沖突采用的是鏈地址法，將出現(xiàn)沖突的 Bucket 串成鏈表，這樣通過中間映射表映射出來的就不再是一個(gè)元素而是一個(gè)鏈表，通過散列函數(shù)定位到對應(yīng)的 Bucket 鏈表時(shí)，需要遍歷鏈表，逐個(gè)對比 key 值，直至找出對應(yīng)的目標(biāo)值

PHP 實(shí)現(xiàn)擴(kuò)容
1.當(dāng)刪除的元素所占比例超出閾值的時(shí)候，則需要移除已經(jīng)被邏輯刪除的 Bucket,將后面的 Bucket 補(bǔ)位到前面，因?yàn)?Bucket 的下標(biāo)發(fā)生了變動(dòng)，所以需要更新每元素在中間映射表中實(shí)際存儲(chǔ)的下標(biāo)值
2.當(dāng)沒有超出閾值的時(shí)候，PHP 會(huì)申請一個(gè)大小是原來兩倍的新數(shù)組，并將舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中，因?yàn)閿?shù)組長度發(fā)生了變化，所以 key->value 的映射關(guān)系需要重新計(jì)算，這個(gè)就是重建索引