目錄

1.散列表的基本概念

2.散列表的查找

3.散列函數(shù)的構(gòu)造方法

1.直接定址法

2.除留余數(shù)法

4.散列表解決沖突的方法

1.開放定址法

2.鏈地址法

1.散列表的基本概念

基本思想：記錄的存儲位置與關(guān)鍵字之間存在的對應(yīng)關(guān)系

對應(yīng)關(guān)系——hash函數(shù)

Loc(i) = H(keyi)

Hash：哈希——翻譯為：散列、雜湊（感覺還是哈希聽起來更好聽）

是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效，通過散列函數(shù)，數(shù)據(jù)元素將被更快地定位。

例題1：

若將學(xué)生信息按如下方武存入計算機，如 將2001011810211的所有信息存入V[11]單元： 將2001011810207的所有信息存入V[07]單元： …… 將2001011810231的所有信息存入V[31]單元。

通過取出最后兩位定義一個關(guān)鍵存儲。

例題2：

數(shù)據(jù)元素序列(21,23,39,9,25,11)，若規(guī)定每個元素k的存儲地址H(k)=k,請畫出存儲結(jié)構(gòu)圖。

??

按照每一個元素的值，存儲到相應(yīng)下標的位置上，從而完成對散列表的構(gòu)建。

散列表的若干術(shù)語：

散列方法（雜湊法）：

1. 選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；

2. 查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進行比，確定查找是否成功。

散列函數(shù)（雜湊函數(shù)）：散列方法中使用的轉(zhuǎn)換函數(shù)

散列表（雜湊表）：按上述思想構(gòu)造的表（也就是例題2所建構(gòu)出來的圖表）

散列函數(shù)：H(key)=k

沖突：不同的關(guān)鍵碼映射到同一個散列地址，key1≠key2,但是H(key1)=H(key2)

例題：有6個元素的關(guān)鍵碼分別為：（25,21,39,9,23,11)。

1. 選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)= k mod 7，

2. 地址編號從0-6。

3. 這時候會發(fā)現(xiàn)有好多計算出來的關(guān)鍵詞一致，造成了沖突

2.散列表的查找

?

?根據(jù)散列函數(shù)H(key) = k

查找key=9,則訪問H(9)=9號地址，若內(nèi)容為9則成功；

若查不到，則返回一個特殊值，如空指針或空記錄。

優(yōu)點：查找效率高

缺點：空間效率低！

?

?注意：第一次計算的時候，即使不符合，也不能說明Hash表里面沒有該值。

例題：

已知一組關(guān)鍵字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79)

散列函數(shù)為：H(key)=key mod13，散列表長為m=16，

設(shè)每個記錄的查找概率相等

線性探測再散列：

用線性探測再散列處理沖突，即Hi=(H(key)+di) MOD m

?

?H(19)=6 H(84)=6沖突，H(84)=(6+1)MOD13=7

H(14)=1 沖突，H(84)=(6+2)MOD13=8

H(23)=10 H(27)=1沖突，H(27)=(1+1)MOD13=2

H(1)=1 沖突，H(1)=(1+1)MOD13=2 沖突，H(27)=(1+2)MOD13=3

H(68)=3 沖突，H(27)=(1+3)MOD13=4

H(20)=7 ……

ASL=(1 * 6 + 2 + 3 * 3 + 4 + 9)/12=2.5

用鏈地址法處理沖突：

?

?散列表的查找效率分析

使用平均查找長度ASL來衡量查找算法，ASL取決于

1. 散列函數(shù)

2. 處理沖突的方法

3. 散列表的裝填因子α

α=表中填入的記錄數(shù)/哈希表長度

ASL與裝填因子α有關(guān)！既不是嚴格的O(1)，也不是O(n)

?

?結(jié)論：

1. 散列表技術(shù)具有很好的平均性能，優(yōu)于一些傳統(tǒng)的技術(shù)

2. 鏈地址法優(yōu)于開地址法

3. 除留余數(shù)法作散列函數(shù)優(yōu)于其它類型函數(shù)

3.散列函數(shù)的構(gòu)造方法

?

散列存儲

選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置

Loc(i)=H(keyi)

沖突，不同的關(guān)鍵碼映射到同一個散列地址

key1≠key2，但是H(key1)=H(key2)

在散列查找方法中，沖突是不可能避免的，只能盡可能減少。

使用散列表要解決兩個重要的問題

1）構(gòu)造好的散列函數(shù)

1. 所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度

2. 所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)該在散列地址集中致均勻分布，以減少空間浪費

2）制定一個好的解決沖突的方案

查找時，如果從散列函數(shù)計算出的地址中查不到關(guān)鍵碼，則應(yīng)該依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。

構(gòu)造散列函數(shù)考慮的因素：

1. 執(zhí)行速度（即計算散列函數(shù)所需要的時間）

2. 關(guān)鍵字的長度

3. 散列表的大小

4. 關(guān)鍵字的分布情況

5. 查找頻率

所以根據(jù)元素集合的特性構(gòu)造，我們就必須考慮到散列查找實際上就是以空間換時間，但我們?nèi)匀幌Ｍ⒘械牡刂房臻g盡量小而且無論是用什么方法進行存儲，目的都是盡可能均勻地存放元素，以避免沖突。

通常，我們會采取以下六種常見方法：

1. 直接定址法

2. 數(shù)字分析法

3. 平方取中法

4. 折疊法

5. 除留余數(shù)法

6. 隨機數(shù)法

接下來，主要來介紹上述的6種方法

1.直接定址法

Hash(key)=a·key+b（a、b為常數(shù)）

優(yōu)點：以關(guān)鍵碼key的某個線性函數(shù)值為散列地址，不會產(chǎn)生沖突。

例：{100, 300, 500, 700, 800, 900} 散列函數(shù)Hash(key) = key/100 (a=1/100, b = 0)

?

2.除留余數(shù)法

Hash(key) = key mod p（p是一個整數(shù)）

關(guān)鍵在于選取合適的p

技巧在于設(shè)表長為m，取p≤m且為質(zhì)數(shù)

例：{15, 23, 27, 38, 53, 61, 70}，

散列函數(shù)Hash(key)=key mod 7

?

4.散列表解決沖突的方法

1. 開放定址法（開地址法）

2. 鏈地址法（拉鏈法）

3. 再散列表法（雙散鏈函數(shù)法）

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

1.開放定址法

基本思想：有沖突時就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將數(shù)據(jù)元素存入。

例如：除留余數(shù)法 Hi = (Hash(key) + di) mod m di為增量序列

常用方法：

1. 線性探測法 di為1,2，……m-1線性序列

2. 二次探測法 di為1^2, -1^2，…… q^2二次序列

3. 偽隨機探測法 di為偽隨機數(shù)序列

線性探測法：

Hi = (Hash(key) + di) mod m (1≤ i ≤ m)

其中的m為散列表長度，di為增量序列1,2，……m-1，且di = i

一旦沖突，就找到下一個地址，直到找到空地址存入。

例：關(guān)鍵碼集為{47, 7, 29, 11, 16, 92, 22, 8, 3}，散列表的表長為m=11；散列函數(shù)為Hash(key) = key mod 11；擬用線性探測是否有沖突。建散列表加下：

??

如圖，因為當29mod11得到7，與我們的原有的7相沖突，此時，通過線性探測法，我們應(yīng)該判斷7的下一個位置，是否為空，若為空則線性往下進行存儲。

??

依次往復(fù)地進行計算、存儲，有如下圖形式：

??

當我們要對其中數(shù)據(jù)進行查找的時候，實際上也是要重復(fù)上述的操作的，也就是取模，如果發(fā)現(xiàn)數(shù)據(jù)不符，則繼續(xù)往后面線性查找。

二次探測法：

例：關(guān)鍵碼集為{47, 7, 29, 11, 16, 92, 22, 8, 3}，散列表的表長為m=11；散列函數(shù)為Hash(key) = key mod 11；擬用二次探測法是否有沖突。

Hi = (Hash(key) + di) mod m (1≤ i ≤ m)

其中的m為散列表長度，di為增量序列1,2，……m-1，且di = i

其中：m為散列表長度，m要求是某個4k+3的質(zhì)數(shù)；

di為增量序列1^2 ， -1^2， 2^2， -2^2，……， q^2

??

例如存儲3的時候發(fā)現(xiàn)原來的位置已經(jīng)被占用了，即Hash(3)=3，散列地址沖突，由 H1=(Hash(3)+12)mod11=4，仍然沖突，則繼續(xù)H2=(Hash(3)-12)mod 11 = 2，找到空的散列地址，存入。

偽隨機探測法：

H1 = (Hash(key)+di) mod m (1≤ i ≤ m)

其中：m為散列表長度，di為偽隨機數(shù)

2.鏈地址法

基本思想：相同散列地址的記錄鏈成一單鏈表

m個散列地址就設(shè)m個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)。

例如：一組關(guān)鍵字為{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函數(shù)為Hash(key)=key mod 13

?

鏈地址法建立散列表步驟

Step1:取數(shù)據(jù)元素的關(guān)鍵字key,計算其散列函數(shù)值（地址）。若該地址對應(yīng)的鏈表為空，則將該元素插入此鏈表；否則執(zhí)行Step2解決沖突。

Step2:根據(jù)選擇的沖突處理方法，計算關(guān)鍵字key的下一個存儲地址。若該地址對應(yīng)的鏈表為不為空，則利用鏈表的前插法或后插法將該元素插入此鏈表。

鏈地址法的優(yōu)點：

1. 非同義詞不會產(chǎn)生沖突，無“集聚”現(xiàn)象

2. 鏈表上結(jié)點空間動態(tài)申請，更適合子表不確定的情況

?文章來源地址http://www.zghlxwxcb.cn/news/detail-494203.html

到了這里，關(guān)于一篇就能學(xué)懂的散列表，讓哈希表數(shù)據(jù)結(jié)構(gòu)大放光彩的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！