查找-hash 算法

1 思想:哈希表是根據設定的

哈希函數H(key)處理衝突方法將一組關鍵字映射到一個有限的地址區間上,並將關鍵字對應的值存儲在該地址空間,可以通過關鍵字快速獲取對應的值,這種表稱為哈希表或散列,所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比,哈希表無疑是查找速度比較快的一種。

2 查找複雜度: O(1)

3 哈希函數

  1. 直接尋址法:取關鍵字或關鍵字的某個線性函數值為散列地址。即H(key)=key或H(key) = a?key + b,其中a和b為常數(這種散列函數叫做自身函數)
  2. 數字分析法:因此數字分析法就是找出數字的規律,儘可能利用這些數據來構造衝突幾率較低的散列地址。比如一組員工的出生年月日,這時我們發現出生年月日的前幾位數字大體相同,這樣的話,出現衝突的幾率就會很大,但是我們發現年月日的後幾位表示月份和具體日期的數字差別很大,如果用後面的數字來構成散列地址,則衝突的幾率會明顯降低。
  3. 平方取中法:取關鍵字平方後的中間幾位作為散列地址
  4. 摺疊法:將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(去除進位)作為散列地址。
  5. 除留餘數法:取關鍵字被某個不大於散列表表長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


分享到:


相關文章: