1 思想：哈希表是根據設定的
哈希函數H(key)和處理衝突方法將一組關鍵字映射到一個有限的地址區間上，並將關鍵字對應的值存儲在該地址空間，可以通過關鍵字快速獲取對應的值，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比，哈希表無疑是查找速度比較快的一種。2 查找複雜度: O(1)
3 哈希函數：
- 直接尋址法：取關鍵字或關鍵字的某個線性函數值為散列地址。即H(key)=key或H(key) = a?key + b，其中a和b為常數（這種散列函數叫做自身函數）
- 數字分析法：因此數字分析法就是找出數字的規律，儘可能利用這些數據來構造衝突幾率較低的散列地址。比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現衝突的幾率就會很大，但是我們發現年月日的後幾位表示月份和具體日期的數字差別很大，如果用後面的數字來構成散列地址，則衝突的幾率會明顯降低。
- 平方取中法：取關鍵字平方後的中間幾位作為散列地址
- 摺疊法：將關鍵字分割成位數相同的幾部分，最後一部分位數可以不同，然後取這幾部分的疊加和（去除進位）作為散列地址。
- 除留餘數法：取關鍵字被某個不大於散列表表長m的數p除後所得的餘數為散列地址。即 H(key) = key MOD p, p<=m。不僅可以對關鍵字直接取模，也可在摺疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞。
4 hash衝突及解決 hash衝突在所難免，解決衝突是一個複雜問題。衝突主要取決於： （1）與散列函數有關，一個好的散列函數的值應儘可能平均分佈。 （2）與解決衝突的哈希衝突函數有關。 （3）與負載因子的大小。太大不一定就好，而且浪費空間嚴重，負載因子和散列函數是聯動的。 解決衝突的辦法： （1）開放定址法：線性探查法、平方探查法、偽隨機序列法、雙哈希函數法。 （2)
拉鍊法：把所有同義詞，即hash值相同的記錄，用單鏈表連接起來。5 應用： 1.字符串哈希 2.加密哈希 3.幾何哈希 4.布隆過濾器
6 不足：獲取有序序列複雜度高
參考： http://www.tuicool.com/articles/RnErui
分享到:
閱讀更多 醉人Ryu 的文章
