PHP 數(shù)組的底層主要是通過 HashTable 實(shí)現(xiàn)塘辅，HashTable 通過映射函數(shù)或者散列函數(shù)將 String Key 轉(zhuǎn)換成一個(gè)普通的數(shù)字下標(biāo)盖溺，然后再將 Value 值存儲(chǔ)到下標(biāo)對(duì)應(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ǔ)到對(duì)應(yīng)的下標(biāo)元素中奖蔓，當(dāng)我們通過 Key 訪問數(shù)組元素時(shí)赞草，只需要再通過相同的算法計(jì)算出對(duì)應(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ù)定位到對(duì)應(yīng)的 Bucket 鏈表時(shí)，需要遍歷鏈表姑尺，逐個(gè)對(duì)比 key 值竟终，直至找出對(duì)應(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ì)申請(qǐng)一個(gè)大小是原來兩倍的新數(shù)組敦姻，并將舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中瘾境，因?yàn)閿?shù)組長(zhǎng)度發(fā)生了變化，所以 key->value 的映射關(guān)系需要重新計(jì)算镰惦，這個(gè)就是重建索引
