Hash算法怎么用

這篇文章主要講解了“Hash算法怎么用”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Hash算法怎么用”吧！

概述

??Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡?，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。 
??Hash主要用于信息安全領(lǐng)域中加密算法，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做Hash值. 也可以說，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。

基本概念

??若結(jié)構(gòu)中存在和關(guān)鍵字K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關(guān)系f為散列函數(shù)(Hash function)，按這個思想建立的表為散列表。 
??對不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象” 作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。 
??若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function)，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少沖突。

哈希函數(shù)的構(gòu)造方法

??構(gòu)造哈希函數(shù)的原則是：①函數(shù)本身便于計算；②計算出來的地址分布均勻，即對任一關(guān)鍵字k，f(k) 對應不同地址的概率相等，目的是盡可能減少沖突。 
??下面介紹構(gòu)造哈希函數(shù)常用的五種方法。

1. 直接尋址法

??取關(guān)鍵字或者關(guān)鍵之的某個線性函數(shù)值為散列地址。即H(key)=key或者H(key)=a*key+b,其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。 

2. 數(shù)字分析法

??如果事先知道關(guān)鍵字集合，并且每個關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。例如，有80個記錄，關(guān)鍵字為8位十進制整數(shù)d1d2d3…d7d8，如哈希表長取100，則哈希表的地址空間為：00~99。假設經(jīng)過分析，各關(guān)鍵字中 d4和d7的取值分布較均勻，則哈希函數(shù)為：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。相反，假設經(jīng)過分析，各關(guān)鍵字中 d1和d8的取值分布極不均勻， d1 都等于5，d8 都等于2，此時，如果哈希函數(shù)為：h(key)=h(d1d2d3…d7d8)=d1d8，則所有關(guān)鍵字的地址碼都是52，顯然不可取。

3． 平方取中法

當無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為：平方后中間幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。

4． 分段疊加法

??這種方法是按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分（最后一部分可以較短），然后將這幾部分相加，舍棄最高進位后的結(jié)果就是該關(guān)鍵字的哈希地址。具體方法有折疊法與移位法。移位法是將分割后的每部分低位對齊相加，折疊法是從一端向另一端沿分割界來回折疊（奇數(shù)段為正序，偶數(shù)段為倒序），然后將各段相加。例如：key=12360324711202065,哈希表長度為1000，則應把關(guān)鍵字分成3位一段，在此舍去最低的兩位65，分別進行移位疊加和折疊疊加，求得哈希地址為105和907。

5． 除留余數(shù)法

??假設哈希表長為m，p為小于等于m的最大素數(shù)，則哈希函數(shù)為h（k）=k % p ，其中%為模p取余運算。

6． 偽隨機數(shù)法

??采用一個偽隨機函數(shù)做哈希函數(shù)，即h(key)=random(key)。

處理沖突的方法

??通過構(gòu)造性能良好的哈希函數(shù)，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關(guān)鍵問題。創(chuàng)建哈希表和查找哈希表都會遇到?jīng)_突，兩種情況下解決沖突的方法應該一致。下面以創(chuàng)建哈希表為例，說明解決沖突的方法。常用的解決沖突方法有以下四種：

1. 開放定址法

??這種方法也稱再散列法，其基本思想是：當關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數(shù)形式： 
??Hi=（H（key）+di）% m i=1，2，…，n 
??其中H（key）為哈希函數(shù)，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種： 
線性探測再散列 
??dii=1，2，3，…，m-1 
??這種方法的特點是：沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。 
二次探測再散列 
di=1^2，-1^2，2^2，-2^2，…，k^2，-k^2 ( k<=m/2 ) 
??這種方法的特點是：沖突發(fā)生時，在表的左右進行跳躍式探測，比較靈活。 
偽隨機探測再散列 
??di=偽隨機數(shù)序列。 
??具體實現(xiàn)時，應建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m），并給定一個隨機數(shù)做起點。 
??例如，已知哈希表長度m=11，哈希函數(shù)為：H（key）= key % 11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關(guān)鍵字為69，則H（69）=3，與47沖突。如果用線性探測再散列處理沖突，下一個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，繼續(xù)找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元。如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 12）% 11 = 2，此時不再沖突，將69填入2號單元。如果用偽隨機探測再散列處理沖突，且偽隨機數(shù)序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元。

2. 再哈希法

??這種方法是同時構(gòu)造多個不同的哈希函數(shù)： 
??Hi=RH1（key） i=1，2，…，k 
??當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。

3. 鏈地址法

??這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。

4. 建立公共溢出區(qū)

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

感謝各位的閱讀，以上就是“Hash算法怎么用”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Hash算法怎么用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！