哈希表：即散列存儲(chǔ)結(jié)構(gòu)。
散列法存儲(chǔ)的基本思想：建立記錄關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系催式，或者說(shuō)悬而，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址呜舒。
這樣，不經(jīng)過(guò)比較笨奠，一次存取就能得到所查元素的查找方法
優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無(wú)關(guān)袭蝗！

哈希方法(雜湊法)
選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置并按此存放般婆；查找時(shí)也由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址到腥，將k與地址中內(nèi)容進(jìn)行比較，確定查找是否成功蔚袍。

哈希函數(shù)(雜湊函數(shù))
哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù)).在記錄的關(guān)鍵碼與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系

例：

有數(shù)據(jù)元素序列(14乡范，23，39啤咽，9晋辆，25，11)宇整，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）＝k 瓶佳， H(k)稱為散列函數(shù),畫出存儲(chǔ)結(jié)構(gòu)圖。

image.png

根據(jù)散列函數(shù)H（k）＝k 没陡，可知元素14應(yīng)當(dāng)存入地址為14的單元涩哟，元素23應(yīng)當(dāng)存入地址為23的單元索赏，……盼玄，

如何進(jìn)行散列查找？

根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式潜腻，迅即可查到結(jié)果埃儿！
例如，查找key=9,則訪問(wèn)H(9)=9號(hào)地址融涣，若內(nèi)容為9則成功童番；
若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值威鹿，例如空指針或空記錄剃斧。
很顯然這種搜索方式空間效率過(guò)低。

哈希函數(shù)可寫成：addr(ai)=H(ki)

選取某個(gè)函數(shù)忽你，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置并按此存放幼东；查找時(shí)也由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址中內(nèi)容進(jìn)行比較，確定查找是否成功根蟹。哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù)).在記錄的關(guān)鍵碼與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系脓杉。

可能導(dǎo)致的沖突

通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后简逮，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上球散，這種現(xiàn)象稱為沖突。

例.

有6個(gè)元素的關(guān)鍵碼分別為：（14散庶，23蕉堰，39，9悲龟，25嘁灯，11）。
選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7

image.png

根據(jù)哈希函數(shù)算出來(lái)發(fā)現(xiàn)同一個(gè)地址放了多個(gè)關(guān)鍵碼躲舌，也就是沖突了丑婿。
在哈希查找方法中，沖突是不可能避免的没卸，只能盡可能減少羹奉。
所以，哈希方法必須解決以下兩個(gè)問(wèn)題：

1）構(gòu)造好的哈希函數(shù)
（a）所選函數(shù)盡可能簡(jiǎn)單约计，以便提高轉(zhuǎn)換速度诀拭；
（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址內(nèi)集中并大致均勻分布煤蚌，以減少空間浪費(fèi)耕挨。

2）制定一個(gè)好的解決沖突的方案
查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼尉桩，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則筒占，有規(guī)律地查詢其它相關(guān)單元。

從上面兩個(gè)例子可以得出如下結(jié)論：
哈希函數(shù)只是一種映象蜘犁，所以哈希函數(shù)的設(shè)定很靈活翰苫，只要使任何關(guān)鍵碼的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可
沖突：key1≠key2，但H(key1)=H(key2)
同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵碼
哈希函數(shù)沖突不可避免这橙，只能盡量減少奏窑。所以，哈希方法解決兩個(gè)問(wèn)題：
構(gòu)造好的哈希函數(shù)屈扎；

制定解決沖突基本要求：
要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址埃唯，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小鹰晨。
要求二：無(wú)論用什么方法存儲(chǔ)墨叛，目的都是盡量均勻地存放元素滑沧，以避免沖突。

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

• 直接定址法
• 除留余數(shù)法
• 乘余取整法
• 數(shù)字分析法
• 平方取中法
• 折疊法
• 隨機(jī)數(shù)法

1巍实、直接定址法

Hash(key) = a·key + b (a滓技、b為常數(shù))
優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.
缺點(diǎn)：要占用連續(xù)地址空間棚潦，空間效率低令漂。

例.關(guān)鍵碼集合為{100，300丸边，500叠必，700，800妹窖，900}纬朝，
選取哈希函數(shù)為Hash(key)=key/100，
則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：

image.png

2骄呼、除留余數(shù)法

Hash(key)=key mod p (p是一個(gè)整數(shù))
特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址共苛。
關(guān)鍵：如何選取合適的p？p選的不好蜓萄，容易產(chǎn)生同義詞
技巧：若設(shè)計(jì)的哈希表長(zhǎng)為m隅茎，則一般取p≤m且為質(zhì)數(shù)
（也可以是合數(shù)，但不能包含小于20的質(zhì)因子）嫉沽。

3辟犀、乘余取整法

Hash(key)= ? B( Akey mod 1 ) ?
(A、B均為常數(shù)绸硕，且0<A<1堂竟，B為整數(shù))
特點(diǎn)：以關(guān)鍵碼key乘以A，取其小數(shù)部分玻佩，然后再放大B倍并取整出嘹，作為哈希地址。
例：欲以學(xué)號(hào)最后兩位作為地址夺蛇，則哈希函數(shù)應(yīng)為：
H(k)=100(0.01k % 1 )
其實(shí)也可以用法2實(shí)現(xiàn)： H(k)=k % 100

4疚漆、數(shù)字分析法

特點(diǎn)：選用關(guān)鍵字的某幾位組合成哈希地址酣胀。選用原則應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同刁赦。
例：有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：

image.png

討論：
① 第1闻镶、2位均是“3和4”甚脉，第3位也只有“ 7、8铆农、9”牺氨，因此狡耻，這幾位不能用，余下四位分布較均勻猴凹，可作為哈希地址選用夷狰。

② 若哈希地址取兩位（因元素僅80個(gè)），則可取這四位中的任意兩位組合成哈希地址郊霎，也可以取其中兩位與其它兩位疊加求和后沼头，取低兩位作哈希地址。

5书劝、平方取中法

特點(diǎn)：對(duì)關(guān)鍵碼平方后进倍，按哈希表大小，取中間的若干位作為哈希地址购对。(適于不知道全部關(guān)鍵碼情況)
理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)猾昆。
例：2589的平方值為6702921，可以取中間的029為地址骡苞。

6垂蜗、折疊法

特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和解幽，并按哈希表表長(zhǎng)么抗，取后幾位作為哈希地址。
適用于：關(guān)鍵碼位數(shù)很多,且每一位上各符號(hào)出現(xiàn)概率大致相同的情況亚铁。
法1：移位法 ── 將各部分的最后一位對(duì)齊相加蝇刀。
法2：間界疊加法──從一端向另一端沿分割界來(lái)回折疊后，最后一位對(duì)齊相加徘溢。
例：元素42751896,
用法1： 427＋518＋96=1041
用法2： 427 518 96—> 724+518+69 =1311

7吞琐、隨機(jī)數(shù)法
Hash(key) = random ( key ) (random為偽隨機(jī)函數(shù))
適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便然爆。

小結(jié)：構(gòu)造哈希函數(shù)的原則：
① 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）站粟；
② 關(guān)鍵字的長(zhǎng)度；
③ 哈希表的大性瘛奴烙；
④ 關(guān)鍵字的分布情況；
⑤ 查找頻率剖张。

三切诀、沖突處理方法

• 開(kāi)放定址法（開(kāi)地址法）
• 鏈地址法（拉鏈法）
• 再哈希法（雙哈希函數(shù)法）
• 建立一個(gè)公共溢出區(qū)

1、開(kāi)放定址法（開(kāi)地址法）

設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址搔弄，只要哈希表足夠大幅虑，空的哈希地址總能找到，并將數(shù)據(jù)元素存入顾犹。
1）線性探測(cè)法
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：
Hash(key)為哈希函數(shù)
m為哈希表長(zhǎng)度
di 為增量序列 1倒庵，2褒墨，…m-1，且di=i

關(guān)鍵碼集為 {47擎宝，7郁妈，29，11绍申，16圃庭，92，22失晴，8剧腻，3}，
設(shè)：哈希表表長(zhǎng)為m=11涂屁；
哈希函數(shù)為Hash(key)=key mod 11书在；
擬用線性探測(cè)法處理沖突。建哈希表如下：

image.png

解釋：
① 47拆又、7是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址儒旬；
② Hash(29)=7，哈希地址有沖突帖族，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1) mod 11=8栈源，哈希地址8為空，因此將29存入竖般。
③ 另外甚垦，22、8涣雕、3同樣在哈希地址上有沖突艰亮，也是由H1找到空的哈希地址的。
其中3 還連續(xù)移動(dòng)了（二次聚集）

線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿挣郭，保證能找到一個(gè)空地址單元存放有沖突的元素迄埃；
線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞兑障，……侄非，
因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)流译，大大降低了查找效率逞怨。
解決方案：可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問(wèn)題先蒋。

2） 二次探測(cè)法
仍舉上例骇钦，改用二次探測(cè)法處理沖突，建表如下：
Hi=(Hash(key)±di) mod m
其中：Hash(key)為哈希函數(shù)
m為哈希表長(zhǎng)度竞漾，m要求是某個(gè)4k+3的質(zhì)數(shù)眯搭；
di為增量序列 1^2，-1 ^2业岁，2 ^2鳞仙，-2 ^2，…笔时，q ^2

image.png

注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同棍好，
Hash(3)=3，哈希地址上沖突允耿，由
H1=(Hash(3)+1 ^2) mod 11=4借笙，仍然沖突；
H2=(Hash(3)-1 ^2) mod 11=2较锡，找到空的哈希地址业稼，存入。

3） 若di＝偽隨機(jī)序列蚂蕴，就稱為偽隨機(jī)探測(cè)法

2低散、鏈地址法(拉鏈法）

基本思想：將具有相同哈希地址的記錄(所有關(guān)鍵碼為同義詞)鏈成一個(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表骡楼，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來(lái)熔号，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。

設(shè){ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函數(shù)為：
Hash(key)=key mod 11鸟整，
用拉鏈法處理沖突引镊，則建表如圖所示。

image.png

3篮条、再哈希法（雙哈希函數(shù)法）

Hi=RHi(key) i=1, 2, …祠乃，k
RHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時(shí)就計(jì)算另一個(gè)哈希函數(shù)兑燥，直到?jīng)_突不再發(fā)生亮瓷。
優(yōu)點(diǎn)：不易產(chǎn)生聚集；
缺點(diǎn)：增加了計(jì)算時(shí)間降瞳。

4. 建立一個(gè)公共溢出區(qū)

思路：除設(shè)立哈现鲋В基本表外，另設(shè)立一個(gè)溢出向量表挣饥。
所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄除师，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突扔枫，都填入溢出表汛聚。

哈希表的查找及分析

明確：散列函數(shù)沒(méi)有“萬(wàn)能”通式（雜湊法），要根據(jù)元素集合的特性而分別構(gòu)造短荐。
討論：哈希查找的速度是否為真正的O（1）倚舀？
不是叹哭。由于沖突的產(chǎn)生，使得哈希表的查找過(guò)程仍然要進(jìn)行比較痕貌，仍然要以平均查找長(zhǎng)度ASL來(lái)衡量风罩。
一般地，ASL依賴于哈希表的裝填因子α,它標(biāo)志著哈希表的裝滿程度舵稠。

image.png

0≤α≤1
α 越大超升，表中記錄數(shù)越多，說(shuō)明表裝得越滿哺徊，發(fā)生沖突的可能性就越大室琢，查找時(shí)比較次數(shù)就越多。

例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函數(shù)為：H(key)=key MOD 13, 哈希表長(zhǎng)為m=16落追，
設(shè)每個(gè)記錄的查找概率相等
(1) 用線性探測(cè)再散列處理沖突盈滴，即Hi=(H(key)+di) MOD m

image.png

H(19)=6
H(14)=1
H(23)=10
H(1)=1     沖突，H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6   沖突淋硝，H1=(6+1)MOD16=7
                 沖突雹熬，H2=(6+2)MOD16=8
H(27)=1   沖突，H1=(1+1)MOD16=2
                 沖突谣膳，H2=(1+2)MOD16=3
                 沖突竿报，H3=(1+3)MOD16=4
H(55)=3   沖突，H1=(3+1)MOD16=4
                 沖突继谚，H2=(3+2)MOD16=5
H(11)=11
H(10)=10  沖突烈菌，H1=(10+1)MOD16=11
                  沖突，H2=(10+2)MOD16=12
H(79)=1    沖突花履，H1=(1+1)MOD16=2
                  沖突芽世，H2=(1+2)MOD16=3
                  沖突，H3=(1+3)MOD16=4
                  沖突诡壁，H4=(1+4)MOD16=5
                  沖突济瓢，H5=(1+5)MOD16=6
                  沖突，H6=(1+6)MOD16=7
                  沖突妹卿，H7=(1+7)MOD16=8
                  沖突旺矾，H8=(1+8)MOD16=9
ASL=(1*6+2+3*3+4*1+9*1)/12=2.5

(2) 用二次探測(cè)再散列處理沖突，即Hi=(H(key)+di) MOD m

image.png

H(19)=6
H(14)=1
H(23)=10
H(1)=1沖突夺克， H1=(1+12) MOD16=2
H(68)=3
H(20)=7
H(84)=6   沖突箕宙，H1=(6+12)MOD16=7
                 沖突，H2=(6﹣12)MOD16=5
H(27)=1   沖突铺纽，H1=(1+12 )MOD16=2
                 沖突柬帕，H2=(1 -12 )MOD16=0
H(55)=3   沖突，H1=(3+12)MOD16=4
H(11)=11
H(10)=10  沖突，H1=(10+12)MOD16=11
                  沖突陷寝，H2=(10 ﹣12 )MOD16=9
H(79)=1    沖突锅很，H1=(1 +12 )MOD16=2
                  沖突，H2=(1﹣12)MOD16=0
                  沖突盼铁，H3=(1+ 22)MOD16=5
                  沖突粗蔚，H4=(1﹣22)MOD16=13

ASL=(1*6+2*2+3*3+5*1)/12=2

(3) 用鏈地址法處理沖突

image.png

討論：

1） 散列存儲(chǔ)的查找效率到底是多少尝偎？
答：ASL與裝填因子α有關(guān)饶火！既不是嚴(yán)格的O(1)，也不是O(n)
2）“沖突”是不是特別討厭致扯？
答：不一定肤寝！正因?yàn)橛袥_突，使得文件加密后無(wú)法破譯６督（單向散列函數(shù)不可逆鲤看，常用于數(shù)字簽名和間接加密）。
利用了哈希表性質(zhì)：源文件稍稍改動(dòng)耍群，會(huì)導(dǎo)致哈希表變動(dòng)很大义桂。