謝宇翔
摘要:本文對經(jīng)典算法中的哈希算法(又稱散列),介紹了其常用的七種構(gòu)造方法和四種沖突解決方法及其原理,并通過舉例,詳細(xì)說明了各種方法的具體實(shí)現(xiàn)和適用場景。
關(guān)鍵詞:哈希,關(guān)鍵字,沖突,時(shí)間復(fù)雜度,空間復(fù)雜度,大數(shù)據(jù)
正文:
在如今的大數(shù)據(jù)時(shí)代,需要各種高效,海量的數(shù)據(jù)處理技術(shù),哈希(HASH)算法以自身的優(yōu)點(diǎn),被廣泛應(yīng)用在查找,存儲,加密,校驗(yàn),區(qū)塊鏈等眾多場景,大大提升了數(shù)據(jù)存儲分析的效率,是不可或缺的數(shù)據(jù)處理技術(shù)。
以下就對哈希的構(gòu)造和沖突解決原理進(jìn)行詳細(xì)的理論和舉例說明。
一、哈希的構(gòu)造方法[1][2]
1.直接定址法:
哈希地址:f(key)=a*key+b (a,b為常數(shù))
簡單均勻,不產(chǎn)生沖突,需事先知道key的分布情況,適合查找表較小且連續(xù)的情況。
舉例:比方說某校從1905年起招生,則統(tǒng)計(jì)每屆招生人數(shù)時(shí),可以用年份-1905作為地址:
此時(shí) f(key)=key-1905
2.數(shù)字分析法
假設(shè)關(guān)鍵字以固定位組成,且可能出現(xiàn)的關(guān)鍵字是事先知道的,則可取關(guān)鍵字的若干數(shù)位組成哈希地址。
3.平方取中法
一個(gè)數(shù)平方的中間幾位與這個(gè)數(shù)的每一位都有關(guān),因而平方取中法產(chǎn)生沖突的機(jī)會相對較小。所取的位數(shù)由表長決定。適合于不知道關(guān)鍵字分布,而位數(shù)又不是很大的情況。
4.折疊法
把一個(gè)關(guān)鍵字分成位數(shù)相同的幾段(最后一段位數(shù)可以不同),然后將各段的疊加和(舍去進(jìn)位)作為哈希地址。
事先不需要知道關(guān)鍵字的分布,而且關(guān)鍵字中每一位上數(shù)字分布大致均勻,適合關(guān)鍵字位數(shù)較多的情況。
5.除留余數(shù)法
取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得的余數(shù)為哈希地址。即 f(key) = key mod p,p<=m。不僅可以對關(guān)鍵字直接取模,也可在折疊法、平方取中法等運(yùn)算之后取模。對p的選擇很重要,一般取質(zhì)數(shù)或m。這是比較重要和常用的方法,被廣泛使用。
6.偽隨機(jī)數(shù)法
f(key) = random(key)
這里 random 是隨機(jī)函數(shù),當(dāng) key 的長度不等時(shí),采用這種方法比較合適。
7.基數(shù)轉(zhuǎn)換法
將一個(gè)數(shù)看作其它進(jìn)制,然后按照新進(jìn)制取其中若干位作為哈希值。一般取大于原基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù),并且兩個(gè)基數(shù)是互質(zhì)的。
比方說key是十進(jìn)制的,那可以新的進(jìn)制為十三進(jìn)制,取其第3,6,9位,即f(key)=key13的第3,6,9位。
二、哈希的沖突解決
下面以創(chuàng)建哈希表為例,說明解決沖突的方法。
常用的解決沖突方法有以下四種:開放尋址法、再哈希法、鏈地址法(拉鏈法)和建立一個(gè)公共溢出區(qū)。[1][2]
1.開放尋址法:當(dāng)關(guān)鍵字key的哈希地址q=f(key)發(fā)生沖突,以q為基數(shù)再生成一個(gè)哈希地址q1,若q1仍然沖突,再以q為基數(shù)生成另一個(gè)哈希地址q2,…,直到找到不沖突的哈希地址。這種方法有一個(gè)通用的再散列函數(shù)形式:
fi=(f(key)+di)%m i=1,2,…,n
其中f(key)為哈希函數(shù),m 為表長,di稱為增量序列。di的取值方式,主要有以下三種:
a) 線性探測再散列 di=1,2,3,…,m-1
b) 二次探測再散列 di=k,-k,k-1,-(k-1),…,1,-1 ? ?( k<=m/2)
c) 偽隨機(jī)探測再散列 di=偽隨機(jī)數(shù)序列。
2.再哈希法:
這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù):
fi(key) i=1,2,…,k
當(dāng)哈希地址f1(key)發(fā)生沖突時(shí),再計(jì)算f2(key)……,直到?jīng)_突不再產(chǎn)生。
比方說fi(key) 定義為對key取5+6i的模,也就是11,17,23,29….
3.鏈地址法(拉鏈法)
這種方法的基本思想是將所有哈希地址為f(key)=i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表,并將單鏈表的頭指針存在哈希表的第i個(gè)單元中,因而查找、插入和刪除主要在同義詞鏈中進(jìn)行。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況。
舉例,用以上f(key)=key%13為例,首先建立一個(gè)擁有索引為13的數(shù)組,數(shù)組中每個(gè)元素為一個(gè)鏈表的頭指針,然后在需要存放數(shù)據(jù)的時(shí)候,根據(jù)f(key)找到數(shù)組中對應(yīng)元素對應(yīng)的鏈表(頭指針),然后在此鏈表最后插入數(shù)據(jù)。
4.建立公共溢出區(qū):
這種方法的基本思想是:將哈希表分為基本表和溢出表兩部分,凡是和基本表發(fā)生沖突的元素,一律填入溢出表。
三、綜合實(shí)例:
問題描述[3]
A和 B各有排列好的n塊積木,每塊積木上寫有一個(gè)小寫英文字母。
允許A從自己的積木串s中丟掉任意塊(也允許不丟);允許B從自己的積木串t中丟掉左邊連續(xù)的一段積木和右邊連續(xù)的一段積木(也允許只丟一邊或兩邊都不丟)。不允許丟棄自己所有積木。然后A和B分別將自己剩下的積木按原來的順序重新排成一排。
計(jì)算一下,有多少種不同的情況下他們最后剩下的兩排積木是相同的(剩下的這兩排積木塊數(shù)相同且每一個(gè)位置上的字母都對應(yīng)相同)?
解答:因?yàn)閷的要求比較寬松,所以首先枚舉t的子串,通過逐一匹配s的位,以此來獲取t中可能匹配的所有子串,時(shí)間復(fù)雜度為O(n^2)。然后在累計(jì)答案處進(jìn)行字符串的相等判斷和去除重復(fù),這里的比較用哈希表來大大提高效率:首先計(jì)算t每個(gè)可能字串的哈希值,把每個(gè)字符轉(zhuǎn)換成ascii與‘a(chǎn)’的差值,即a=1,b=2,…,并把每個(gè)位以base(很大的質(zhì)數(shù))作為進(jìn)制獲得表示t從i到j(luò)的哈希key數(shù)組HashKey[i][j],然后比方說采用除留余數(shù)法,以另一個(gè)大質(zhì)數(shù)作為模數(shù)獲得哈希地址來進(jìn)行比較。若是簡單的進(jìn)行枚舉比較,那時(shí)間復(fù)雜度將大幅度增加;和其它方法相比較,使用hash應(yīng)該是時(shí)間復(fù)雜度最優(yōu)的方法。
參考文獻(xiàn):
[1]哈希算法原理詳解 https://www.jianshu.com/p/f9239c9377c5
[2]哈希算法以及沖突解決 https://www.itdaan.com/blog/2016/12/06/c885400f4092.html
[3]洛谷 https://www.luogu.com.cn/problem/P7469