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在插入的時候更加容易出現哈希沖突，是以采用開放尋址法的哈希表的裝載因子不能太高，否則容易出現性能下降。