個人博客地址 http://dandanlove.com/

在平時工作和源碼學(xué)習(xí)的過程中經(jīng)常遇到哈希相關(guān)的問題，每次都會上網(wǎng)找資料回憶哈希相關(guān)的知識點。趁這機會記錄下來，防止以后又忘記了_！！

哈希表

根據(jù)關(guān)鍵字（Key value）至二級訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

哈希沖突

對不通的關(guān)鍵字可能得到同意散列地址，即k1 != k2,而f(k1) = f(k2)，這種現(xiàn)象稱為碰撞，也叫哈希沖突。

為什么需要哈希

使用數(shù)組或者鏈表存儲元素，一旦存儲的內(nèi)容數(shù)量特別多，需要占用很大的空間，而且在查找某一個元素是否存在的過程中，數(shù)據(jù)和鏈表都需要循環(huán)便利，而通過哈希計算，可以大大減少比較次數(shù)。

哈希使用

幾種常見的哈希函數(shù)（散列函數(shù)）的構(gòu)造方法

• 直接定址法：取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)值為散列地址。例如：H(key) = key,H(key) = a*key + b,其中a，b為常數(shù)。

  
  
  直接定址法

• 除留余數(shù)發(fā)：取關(guān)鍵字被某個不大于散列長度m的數(shù)p求余，得到的作為散列地址。例如：H(key)=key%p,p < m。

  
  
  除留余數(shù)發(fā)

• 數(shù)字分析法：當(dāng)關(guān)鍵字的位數(shù)大于地址的位數(shù)，對關(guān)鍵字的各位分布進行分析，選出分布均勻的任意幾位作為散列地址。僅僅用于適用所欲關(guān)鍵字都已知的情況下，根據(jù)實際應(yīng)用確定要選取的部分，盡量避免發(fā)生沖突。

  
  
  數(shù)字分析法

• 平方取中法：先計算出關(guān)機子的平方值，然后取平方值中間幾位作為散列地址。隨機分布的關(guān)鍵字，得到散列地址也是隨機分布的。

  
  
  平方取中法

• 折疊法（疊加法）：將關(guān)鍵字分為位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）作為散列地址。用于關(guān)鍵字位數(shù)比較多，并且關(guān)鍵字中每一位上數(shù)字分布大致均勻。

  
  
  折疊法
• 隨機數(shù)法：選擇一個隨機函數(shù)，把關(guān)鍵字的隨機函數(shù)值作為它的哈希值。通常關(guān)鍵字的長度不等時采用這種方法。

構(gòu)造哈希函數(shù)的方法很多，實際工作中需要根據(jù)不同的情況選擇合適的方法，總的原則是盡可能的減少產(chǎn)生的沖突。

通常考慮的因素有關(guān)鍵字的長度和分布情況、哈希值的范圍等。

如：當(dāng)關(guān)鍵字是整數(shù)類型時就可以用哦除留余數(shù)法；如果關(guān)鍵字是小數(shù)類型，選擇隨機書法會比較好。

哈希函數(shù)

鏈接法（拉鏈法）

拉鏈法解決沖突的做法是：將所有關(guān)鍵字為hash相同的結(jié)點鏈接在同一個單鏈表中。

若選定的散列表長度為嗎，則可將散列表定義為一個由m個頭指針組成的指針數(shù)組T[0...m-1].

凡是散列地址為i的結(jié)點，均插入到以T[i]為頭指針的單鏈表中。

T中各個分量的初值值均為空指針

在拉鏈法中，裝填因子a可以大于1，但一般均取a<=1。

拉鏈法構(gòu)造散列表

開放定址發(fā)（再散列法）

基本思想：當(dāng)關(guān)鍵字key的哈希地址p=H(key)出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1任然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，...，直到找出一個不沖突的哈希地址pi，將相應(yīng)元素存入其中。

這種方法有一個通用的再散列函數(shù)形式：Hi = (H(key) + di) % m, i = 1,2,,4,...,n。其中H（key)為哈希函數(shù)，m為表長，di稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。

用開放定址法解決沖突的做法是：

當(dāng)沖突發(fā)生時，使用某種探測技術(shù)在散列表中形成一個探測序列。沿此序列逐個單元地查找，知道找到給定的關(guān)鍵字，或者碰到一個開放地址（即該地址單元為空）為止（若要插入，在探測到開放的地址，則可將待插入的新結(jié)點存入該地址單元）。查找時探測到開放地址則表明無待查的關(guān)鍵字，即查找失敗。

簡單的說：當(dāng)發(fā)生沖突時，使用某種探測（亦稱探測）技術(shù)在散列表中尋找下一個空的散列地址，只要散列表足夠大，空的散列表地址總能找到。

按照形成探查序列的方法不同，可將開放地址發(fā)區(qū)分為線性探查法、二次探查法、雙重散列法等。

• 線性探查法：hi=（h（key） + 1） % m， 0 <= i <= m-1。

  基本思想是：探查時從地址d開始，首先探查T[d],然后依次探查T[d+1],...,直到T[m-1],此后又循環(huán)到T[0],T[1],...,直到有空余地址或者到T[d-1]位為止。

  這種方法的特點是：沖突發(fā)生時，順查看表中下一單元，知道找出一個空單元或者查遍全表。

• 二次探測再散列法：hi=（h(key) + i*i）% m, 0 <= i <= m-1。

  基本思想是：探查時從地址d開始，首先探查T[d],然后依次探查T[d+1^2],T[d+2^2],T[d+3^2],...等，直到探查到有空余地址或者到T[d-1]為止。

  缺點是無法探測到整個散列空間。

• 雙重散列法：hi=(h(key) + i*h1(key))%m, 0 <= i <= m-1。

  基本思想是：探查時從地址d開始，首先探查T[d],然后依次探查T[d+h1(d)],T[d+2*h1(d)],...,等。該方法使用了兩個散列函數(shù)h(key)和h1(key)，故也稱為雙散列函數(shù)探查法。

  定義h1(key)的方法比較多，但無論采用什么方法定義，都必須使h1（key)和值和m互素，才能使發(fā)生沖突的同義詞地址均勻分布在整個表中，負(fù)責(zé)可能造成同義詞地址的循環(huán)計算。

  該方法是開放定址法中最好的方法之一。

建立公共溢出區(qū)

這種方法的基本思想是：將hash表分為基本表和溢出表兩部分，凡是基本表發(fā)生沖突的元素，一律填入溢出表。

再哈希法

這種方法是同時構(gòu)造多個不同的哈希函數(shù)：

Hi=RH1(key) i=1,2,3,,,,k

當(dāng)哈希地址Hi=RH1(key)發(fā)生沖突時，再計算Hi=RH2(key),,,,直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚焦，但增加了計算時間。

參考文章: 重溫數(shù)據(jù)結(jié)構(gòu)：哈希 哈希函數(shù) 哈希表

文章到這里就全部講述完啦，若有其他需要交流的可以留言哦_！！

想閱讀作者的更多文章，可以查看我 個人博客 和公共號：

振興書城