?

?

Hash表是一種數據結構 提供快速的存取和查找，他是基于數組的，數組創建后大小是固定的難以拓展 ，當然可以復制數據到更大的數組，但是非常消耗性能，如果數據量固定，需要快速查詢時 hash表是一個不錯的選擇

?

數組只能以數字作為下標 而不能以字符串作為下標 所以要考慮將字符串轉換為唯一的數字 這個過程叫做hash化 過程由hash函數完成，使用hash函數插入數據到數組后，數組被稱為hash表

?

Hash函數

1疊加法

假如給 字母編個號碼

空格0 a 1 ,b2 c 2,? 27 z

?

Hash函數采用加法運算

?? 比如 abc = 1+2+3

?? 最大的字母是10位

?? zzzzzzzzzz=26*10=260

?

顯然 所有的字母可能只能組合出? 260個索引為 ，而實際上單詞有 50000

?

而每一個索引的位置 需要存放單詞 50000/260=192個單詞 顯然不行

?

2 冪的連續乘法

?

?? 參考數字的拆分

? ?234=2*100+3*10+4

?

?? 那么abc? 因為字母是27個

?? 1*27*27+2*27+3= 786

?

如果是 zzzzzzzzzz=?? 不知道有多大? 可能會操過變量允許的最大位數

?

怎么解決了 可以對產生的數字進行壓縮

?比如 數組的大小是1000?

那么獲取下標可以用 要存放的字母冪的連乘獲取的結果 % 1000（也就是數組的大小）

就能獲取一個數 <1000 的

?比如（1000+999）%1000 =999??

?

這樣仍然有一個問題

?

就是數組 可能壓縮產生的數字 已經被其他的字母占據了 怎么辦了

?

有兩種解決方法 ：開放地址法 和 鏈地址法

?

2.1開放地址法：

? 開放地址法就是發現如果被占據，就需要利用方法去找尋空白的位置，三種方法：線性探測，二次探測，再hash法

?? 線性探測： 比如產生的索引位置是123，123被占據了? 找124 124被占用找125 一直到找到是空白的地址

?

?? 二次探測：已填充數據的個數/hash表的大小 就是裝填因子，聚集就是hash表某個部分的位置都被填充 而部分位置一個數據的都沒有 出現聚集時 可能到比較遠一點的單元格去尋找空的位置 就叫二次探測

?

? 一次探測 比如 找到的位置是 123? 123+1 ，123+2? 一步一步探測

? 二次探測????? 找到的位置是 123? 123+1?? 123+4 123+9? 已 n的平方來探測

可以這么理解 首先查找臨邊 如果臨邊被占據了 懷疑可能旁邊也被占據了，跳到4的位置

有點憂慮可能有很大的聚集 結果跳到9的位置

?? 但是二次探測也會產生問題 ：二次聚集 比如 n多個數 通過hash函數轉換的數字式一樣的 跳動的步驟也是一樣的 出現二次聚集

?

再哈希法：二次探測出現二次聚集的原因是因為 步長時相同的，現在需要創建一個布長不一樣的探測序列 這個序列可以在用一次hash化一便，布長不能為0 否則每次都在原地打轉

? stepSize=contant*(key%contant)

contant是介質 小于數組容量，key是第一次hash的位置

?

?

2.2鏈地址法：

?這種方法比較容易理解

?Hash表中位置放置的是第一次插入的值，以后如果hash話出來的位置 已經存在數據的話 就已鏈表的形式指向第一個位置 ，如果在來一個指向第二個位置

?

很明顯這樣做會出現重復值 ，當然也允許出現重復值

鏈表就不用再擔心容量問題

?

轉載于:https://www.cnblogs.com/liaomin416100569/archive/2010/10/28/9331589.html

總結

以上是生活随笔為你收集整理的hash算法的介绍 【清晰易懂】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。