hash怎么用(Hash算法怎么用)

概述

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

基本概念

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

哈希函數的構造方法

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

1. 直接尋址法

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

2. 數字分析法

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

3. 平方取中法

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

4. 分段疊加法

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

5. 除留余數法

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

6. 偽隨機數法

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

處理沖突的方法

??通過構造性能良好的哈希函數,可以減少沖突,但一般不可能完全避免沖突,因此解決沖突是哈希法的另一個關鍵問題。創建哈希表和查找哈希表都會遇到沖突,兩種情況下解決沖突的方法應該一致。下面以創建哈希表為例,說明解決沖突的方法。常用的解決沖突方法有以下四種:

1. 開放定址法

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

2. 再哈希法

??這種方法是同時構造多個不同的哈希函數:
??Hi=RH1(key) i=1,2,…,k
??當哈希地址Hi=RH1(key)發生沖突時,再計算Hi=RH2(key)……,直到沖突不再產生。這種方法不易產生聚集,但增加了計算時間。

3. 鏈地址法

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

4. 建立公共溢出區

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

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