一、前沿

1.1、直接尋址表

當(dāng)關(guān)鍵字的全域U比較小時(shí)，直接尋址是一種簡(jiǎn)單而有效的技術(shù)。假設(shè)某應(yīng)用要用到一個(gè)動(dòng)態(tài)集合，其中每個(gè)元素都有一個(gè)取自全域U={0，1，…，m-1)的關(guān)鍵字，此處m是一個(gè)不很大的數(shù)。另假設(shè)沒(méi)有兩個(gè)元素具有相同的關(guān)鍵字。

為表示動(dòng)態(tài)集合，我們用一個(gè)數(shù)組(或稱直接尋址表)T[0…m一1]，其中每個(gè)位置（或稱槽）應(yīng)全域U中的一個(gè)關(guān)鍵字。下圖說(shuō)明這個(gè)方法；槽 k 指向集合中一個(gè)關(guān)鍵字為 k 的元素。如果該集合中沒(méi)有關(guān)鍵字為 k 的元素，則T[k]=NIL。

用一個(gè)直接尋址表T實(shí)現(xiàn)動(dòng)態(tài)集合。全域U={0，1，…，9}中的每個(gè)關(guān)鍵字都對(duì)應(yīng)于表中的一個(gè)下標(biāo)值。由實(shí)際關(guān)鍵字構(gòu)成的集合K={2，3，5，8}決定表中哪些槽包含指向元素的指針。其他帶深陰影的槽包含NIL

直接尋址技術(shù)缺點(diǎn):

• 當(dāng)域U很大時(shí)，需要消耗大量?jī)?nèi)存，很不實(shí)際
• 如果域U很大而實(shí)際出現(xiàn)的key很少，則大量空間被浪費(fèi)
• 無(wú)法處理關(guān)鍵字不是數(shù)字的情況

---

1.2、哈希

直接尋址表：key為k的元素放到k位置上

改進(jìn)直接尋址表：哈希(Hashing)

• 構(gòu)建大小為m的尋址表T
• key為k的元素放到h(k)位置上
• h(k)是一個(gè)函數(shù)，其將域U映射到表T[0,1,…,m-1]

---

二、哈希表

2.1、概念

哈希表（Hash Table，又稱為散列表），是—種線性表的存儲(chǔ)結(jié)構(gòu)。哈希表由一個(gè)直接尋址表和一個(gè)哈希函數(shù)組成。哈希函數(shù)h(k)將元素關(guān)鍵字k作為自變量，返回元素的存儲(chǔ)下標(biāo)。

哈希表一個(gè)通過(guò)哈希函數(shù)來(lái)計(jì)算數(shù)據(jù)存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)，通常支持如下操作:

• insert(key,value)：插入鍵值對(duì)(key,value)
• get(key)：如果存在鍵為key的鍵值對(duì)則返回其value，否則返回空值
• delete(key)：刪除鍵為key的鍵值對(duì)

例：假設(shè)有一個(gè)長(zhǎng)度為7的哈希表，哈希函數(shù)h(k)=k%7。元素集合{14,22,3,5}的存儲(chǔ)方式如下圖：

---

2.2、哈希沖突

由于哈希表的大小是有限的，而要存儲(chǔ)的值的總數(shù)量是無(wú)限的，因此對(duì)于任何哈希函數(shù)，都會(huì)出現(xiàn)兩個(gè)不同元素映射到同一個(gè)位置上的情況，這種情況叫做哈希沖突。

2.2.1、解決哈希沖突——開(kāi)放尋址法

開(kāi)放尋址法：如果哈希函數(shù)返回的位置已經(jīng)有值，則可以向后探查新的位置來(lái)存儲(chǔ)這個(gè)值

• 線性探查：如果位置i被占用，則探查i+1, i+2,…
• 二次探查：如果位置i被占用，則探查i+1^2, i-1^2, i+2^2, i-2^2,…
• 二度哈希：有n個(gè)哈希函數(shù)，當(dāng)使用第1個(gè)哈希函數(shù)h1發(fā)生沖突時(shí)，則嘗試使用h2,h3,…

---

2.2.2、解決哈希沖實(shí)——拉鏈法

拉鏈法:哈希表每個(gè)位置都連接—個(gè)鏈表，當(dāng)沖突發(fā)生時(shí)，沖突的元素將被加到該位置鏈表的最后。

---

2.3、常見(jiàn)哈希函數(shù)

除法哈希法

乘法哈希法

全域哈希法

---

三、哈希表實(shí)現(xiàn)(拉鏈法)

鏈表代碼（單鏈表）：數(shù)據(jù)結(jié)構(gòu)與算法筆記（三）—— 鏈表(單鏈表、循環(huán)鏈表、雙向鏈表)

class HashTable:def __init__(self,size = 20):self.size = sizeself.T = [SingleLinkList() for i in range(self.size)]def h(self,k):'''哈希函數(shù): 計(jì)算數(shù)據(jù)存儲(chǔ)位置'''return k % self.sizedef insert(self,k):'''插入元素'''i = self.h(k)if self.find(k):print('重復(fù)插入!!!')else:self.T[i].append(k)def find(self,k):'''查找元素'''i = self.h(k)return self.T[i].search(k)def travel(self):'''遍歷打印'''for i in range(self.size):print(self.T[i].travel())def remove(self,k):'''刪除元素'''if self.find(k):i = self.h(k)self.T[i].remove(k)if __name__ == '__main__':ht = HashTable()ht.insert(0)ht.insert(1)ht.insert(2)ht.insert(21)ht.travel()ht.remove(2)ht.travel()print(ht.find(2))

---

四、哈希表的應(yīng)用

4.1、集合與字典

字典與集合都是通過(guò)哈希表來(lái)實(shí)現(xiàn)的。

例如：

a = {'name': 'Alex', 'age': 18, 'gender': 'Man'}

使用哈希表存儲(chǔ)字典，通過(guò)哈希函數(shù)將字典的鍵映射為下標(biāo)。
假設(shè)：

h('name')=3, h('age')=1, h('gender')=4

則哈希表存儲(chǔ)為

[None,18,None,'Alex','Man']

如果發(fā)生哈希沖突，則通過(guò)拉鏈法或開(kāi)發(fā)尋址法解決

---

4.2、md5算法

MD5(Message-Digest Algorithm 5)曾經(jīng)是密碼學(xué)中常用的哈希函數(shù)，可以把任意長(zhǎng)度的數(shù)據(jù)映射為128位的哈希值，其曾經(jīng)包含如下特征:

同樣的消息，其MD5值必定相同;

可以快速計(jì)算出任意給定消息的MD5值;

除非暴力的枚舉所有可能的消息，否則不可能從哈希值反推出消息本身;

兩條消息之間即使只有微小的差別，其對(duì)應(yīng)的MD5值也應(yīng)該是完全不同、完全不相關(guān)的;

不能在有意義的時(shí)間內(nèi)人工的構(gòu)造兩個(gè)不同的消息使其具有相同的MD5值。

應(yīng)用舉例： 文件的哈希值

算出文件的哈希值，若兩個(gè)文件的哈希值相同，則可認(rèn)為這兩個(gè)文件是相同的，因此：

用戶可以利用它來(lái)驗(yàn)證下載的文件是否完整。

云存儲(chǔ)服務(wù)商可以利用它來(lái)判斷用戶要上傳的文件是否已經(jīng)存在于服務(wù)器上，從而實(shí)現(xiàn)秒傳的功能，同時(shí)避免存儲(chǔ)過(guò)多相同的文件副本。

---

4.3、SHA2算法

歷史上MD5和SHA-1曾經(jīng)是使用最為廣泛的 cryptographic hash function，但是隨著密碼學(xué)的發(fā)展,這兩個(gè)哈希函數(shù)的安全性相繼受到了各種挑戰(zhàn)。

因此現(xiàn)在安全性較重要的場(chǎng)合推薦使用SHA-2等新的更安全的哈希函數(shù)。

SHA-2包含了一系列的哈希函數(shù): SHA-224，SHA- 256，SHA-384，SHA-512，SHA-512/224，SHA- 512/256，其對(duì)應(yīng)的哈希值長(zhǎng)度分別為224，256，384 or 512位。

SHA-2具有和MD5類似的性質(zhì)(參見(jiàn)MD5算法的特征)。

應(yīng)用舉例：
例如，在比特幣系統(tǒng)中，所有參與者需要共同解決如下問(wèn)題：對(duì)于一個(gè)給定的字符串U，給定的國(guó)標(biāo)哈希值H，需要計(jì)算出一個(gè)字符串V，使得U+V的哈希值與H的差小于一個(gè)給定值D。此時(shí)，只能通過(guò)暴力枚舉V來(lái)進(jìn)行猜測(cè)。首先計(jì)算出結(jié)果的人可獲得一定獎(jiǎng)金。而某人首先計(jì)算成功的概率與其擁有的計(jì)算量成正比，所以其獲得的獎(jiǎng)金的期望值與其擁有的計(jì)算量成正比。

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法笔记（十五）—— 散列(哈希表)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。