php源碼學(xué)習(xí)日志 hash表

 php 的源碼實現(xiàn)中，很多數(shù)據(jù)是用一張hash表維護(hù)的，比如對象的方法，數(shù)組等

    基本概念

        哈希表是一種通過哈希函數(shù)，將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)，它維護(hù)鍵和值之間一一對應(yīng)關(guān)系。

鍵(key)：用于操作數(shù)據(jù)的標(biāo)示，例如PHP數(shù)組中的索引，或者字符串鍵等等。

槽(slot/bucket)：哈希表中用于保存數(shù)據(jù)的一個單元，也就是數(shù)據(jù)真正存放的容器。

哈希函數(shù)(hash function)：將key映射(map)到數(shù)據(jù)應(yīng)該存放的slot所在位置的函數(shù)。

哈希沖突(hash collision)：哈希函數(shù)將兩個不同的key映射到同一個索引的情況。

 但是hash算法再好，在無線的數(shù)據(jù)下，總會出現(xiàn)不同key對應(yīng)相同值的情況，應(yīng)為hash后的值是等長的，而這個時候，就是hash沖突了，解決沖突目前有兩個方法，鏈表發(fā)和尋址法

沖突解決 鏈接法

       鏈接法通過使用一個鏈表來保存slot值的方式來解決沖突，也就是當(dāng)不同的key映射到一個槽中的時候使用鏈表來保存這些值。所以使用鏈接法是在最壞的情況下，也就是所有的key都映射到同一個槽中了，這樣哈希表就退化成了一個鏈表，這樣的話操作鏈表的時間復(fù)雜度則成了O(n)，這樣哈希表的性能優(yōu)勢就沒有了，所以選擇一個合適的哈希函數(shù)是最為關(guān)鍵的。

弱點

     由于目前大部分的編程語言的哈希表實現(xiàn)都是開源的，大部分語言的哈希算法都是公開的算法，雖然目前的哈希算法都能良好的將key進(jìn)行比較均勻的分布，而這個假使的前提是key是隨機(jī)的，正是由于算法的確定性，這就導(dǎo)致了別有用心的***能利用已知算法的可確定性來構(gòu)造一些特殊的key，讓這些key都映射到同一個槽位導(dǎo)致哈希表退化成單鏈表，導(dǎo)致程序的性能急劇下降，從而造成一些應(yīng)用的吞吐能力急劇下降，尤其是對于高并發(fā)的應(yīng)用影響很大，通過大量類似的請求可以讓服務(wù)器遭受DoS(服務(wù)拒絕***)，這個問題一直就存在著，只是最近才被各個語言重視起來。

哈希沖突***利用的哈希表最根本的弱點是：開源算法和哈希實現(xiàn)的確定性以及可預(yù)測性，這樣***者才可以利用特殊構(gòu)造的key來進(jìn)行***。要解決這個問題的方法則是讓***者無法輕易構(gòu)造能夠進(jìn)行***的key序列。

開放尋址法

        通常還有另外一種解決沖突的方法：開放尋址法。使用開放尋址法是槽本身直接存放數(shù)據(jù)，在插入數(shù)據(jù)時如果key所映射到的索引已經(jīng)有數(shù)據(jù)了，這說明發(fā)生了沖突，這是會尋找下一個槽，如果該槽也被占用了則繼續(xù)尋找下一個槽，直到尋找到?jīng)]有被占用的槽，在查找時也使用同樣的策律來進(jìn)行。

由于開放尋址法處理沖突的時候占用的是其他槽位的空間,這可能會導(dǎo)致后續(xù)的key在插入的時候更加容易出現(xiàn)哈希沖突，所以采用開放尋址法的哈希表的裝載因子不能太高，否則容易出現(xiàn)性能下降。

裝載因子是哈希表保存的元素數(shù)量和哈希表容量的比，通常采用鏈接法解決沖突的哈希表的裝載 因子最好不要大于1，而采用開放尋址法的哈希表最好不要大于0.5。