php源碼學習日志 hash表

 php 的源碼實現中，很多數據是用一張hash表維護的，比如對象的方法，數組等

    基本概念

        哈希表是一種通過哈希函數，將特定的鍵映射到特定值的一種數據結構，它維護鍵和值之間一一對應關系。

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

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

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

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

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

沖突解決 鏈接法

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

弱點

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

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

開放尋址法

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

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

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