哈希表

基本概念

• 若關(guān)鍵字為k，則其值存放在f(k)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱這個(gè)對(duì)應(yīng)關(guān)系f為散列函數(shù)，按這個(gè)思想建立的表為散列表。
• 對(duì)不同的關(guān)鍵字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，這種現(xiàn)象稱為沖突（英語(yǔ)：Collision）。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱做同義詞。綜上所述，根據(jù)散列函數(shù)**f(k)**和處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲(chǔ)位置，這種表便稱為散列表，這一映射過(guò)程稱為散列造表或散列，所得的存儲(chǔ)位置稱散列地址。
• 若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就是使關(guān)鍵字經(jīng)過(guò)散列函數(shù)得到一個(gè)“隨機(jī)的地址”，從而減少?zèng)_突。

常用方法

通過(guò)將關(guān)鍵字(key)映射到表中一個(gè)位置， 可以直接訪問(wèn)記錄， 以提高查找的速率，相比較其他的查找結(jié)構(gòu)，哈希表查找的時(shí)間復(fù)雜度更低。其中用于映射的函數(shù)稱為哈希函數(shù)， 哈希函數(shù)有多種，常見的哈希函數(shù)包括CRC32，MD5，SHA等。由于哈希表的特殊性質(zhì)，其在安全加密，數(shù)據(jù)校驗(yàn)，唯一標(biāo)識(shí)，負(fù)載均衡等場(chǎng)景都有著不可替代的作用。4

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

實(shí)際工作中需視不同的情況采用不同的哈希函數(shù)，通常考慮的因素有：

· 計(jì)算哈希函數(shù)所需時(shí)間

· 關(guān)鍵字的長(zhǎng)度

· 哈希表的大小

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

· 記錄的查找頻率

**1.**直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。若其中H（key）中已經(jīng)有值了，就往下一個(gè)找，直到H（key）中沒(méi)有值了，就放進(jìn)去。

**2. 數(shù)字分析法：**分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時(shí)就會(huì)發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會(huì)很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來(lái)構(gòu)成散列地址，則沖突的幾率會(huì)明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來(lái)構(gòu)造沖突幾率較低的散列地址。

3. 平方取中法**：**當(dāng)無(wú)法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。

例：我們把英文字母在字母表中的位置序號(hào)作為該英文字母的內(nèi)部編碼。例如K的內(nèi)部編碼為11，E的內(nèi)部編碼為05，Y的內(nèi)部編碼為25，A的內(nèi)部編碼為01, B的內(nèi)部編碼為02。由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為11052501，同理我們可以得到關(guān)鍵字“KYAB”、“AKEY”、“BKEY”的內(nèi)部編碼。之后對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算后，取出第7到第9位作為該關(guān)鍵字哈希地址，如下表所示

|| ||

**4. 折疊法：**將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對(duì)齊，然后相加；間界疊加是從一端向另一端沿分割界來(lái)回折疊，然后對(duì)齊相加。

**5. 隨機(jī)數(shù)法：**選擇一隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)值作為散列地址，即H(key)=random(key)其中random為隨機(jī)函數(shù),通常用于關(guān)鍵字長(zhǎng)度不等的場(chǎng)合。

**6. 除留余數(shù)法：**取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p≤m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對(duì)p的選擇很重要，一般取素?cái)?shù)或m，若p選的不好，容易產(chǎn)生同義詞。2

處理沖突

1. 開放尋址法：Hi=（H（key）+ di） MOD m,i=1,2，…，k（k≤m-1），其中H（key）為散列函數(shù)，m為散列表長(zhǎng)，di為增量序列，可有下列三種取法：

1.1. di=1,2,3，…，m-1，稱線性探測(cè)再散列；

1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k）^2,（km/2）稱二次探測(cè)再散列；

1.3. di=偽隨機(jī)數(shù)序列，稱偽隨機(jī)探測(cè)再散列。

2. 再散列法：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)散列函數(shù)地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間。

3. 鏈地址法（拉鏈法）

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

查找性能

散列表的查找過(guò)程基本上和造表過(guò)程相同。一些關(guān)鍵碼可通過(guò)散列函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過(guò)程。所以，對(duì)散列表查找效率的量度，依然用平均查找長(zhǎng)度來(lái)衡量。

查找過(guò)程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：

1. 散列函數(shù)是否均勻；

2. 處理沖突的方法；

3. 散列表的裝填因子。

散列表的裝填因子定義為：α= 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度

α是散列表裝滿程度的標(biāo)志因子。由于表長(zhǎng)是定值，α與“填入表中的元素個(gè)數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。

實(shí)際上，散列表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

了解了hash基本定義，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以說(shuō)是目前應(yīng)用最廣泛的Hash算法，而它們都是以 MD4 為基礎(chǔ)設(shè)計(jì)的。那么他們都是什么意思呢?

這里簡(jiǎn)單說(shuō)一下：

⑴ MD4

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的，MD 是 Message Digest 的縮寫。它適用在32位字長(zhǎng)的處理器上用高速軟件實(shí)現(xiàn)--它是基于 32 位操作數(shù)的位操作來(lái)實(shí)現(xiàn)的。

⑵ MD5

MD5（RFC 1321）是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)，與 MD4 相同。MD5比MD4來(lái)得復(fù)雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現(xiàn)更好

⑶ SHA-1 及其他

SHA1是由NIST NSA設(shè)計(jì)為同DSA一起使用的，它對(duì)長(zhǎng)度小于264的輸入，產(chǎn)生長(zhǎng)度為160bit的散列值，因此抗窮舉（brute-force）性更好。SHA-1 設(shè)計(jì)時(shí)基于和MD4相同原理，并且模仿了該算法。

那么這些Hash算法到底有什么用呢?

Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個(gè)方面：

⑴文件校驗(yàn)

我們比較熟悉的校驗(yàn)算法有奇偶校驗(yàn)和CRC校驗(yàn)，這2種校驗(yàn)并沒(méi)有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測(cè)出數(shù)據(jù)傳輸中的信道誤碼，但卻不能防止對(duì)數(shù)據(jù)的惡意破壞。

MD5 Hash算法的"數(shù)字指紋"特性，使它成為目前應(yīng)用最廣泛的一種文件完整性校驗(yàn)和（Checksum）算法，不少Unix系統(tǒng)有提供計(jì)算md5 checksum的命令。

⑵數(shù)字簽名

Hash 算法也是現(xiàn)代密碼體系中的一個(gè)重要組成部分。由于非對(duì)稱算法的運(yùn)算速度較慢，所以在數(shù)字簽名協(xié)議中，單向散列函數(shù)扮演了一個(gè)重要的角色。對(duì) Hash 值，又稱"數(shù)字摘要"進(jìn)行數(shù)字簽名，在統(tǒng)計(jì)上可以認(rèn)為與對(duì)文件本身進(jìn)行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點(diǎn)。

⑶ 鑒權(quán)協(xié)議

如下的鑒權(quán)協(xié)議又被稱作挑戰(zhàn)--認(rèn)證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡(jiǎn)單而安全的方法。

MD5、SHA1的破解

2004年8月17日，在美國(guó)加州圣芭芭拉召開的國(guó)際密碼大會(huì)上，山東大學(xué)王小云教授在國(guó)際會(huì)議上首次宣布了她及她的研究小組的研究成果——對(duì)MD5、HAVAL－128、MD4和RIPEMD等四個(gè)著名密碼算法的破譯結(jié)果。2005年2月宣布破解SHA-1密碼。

實(shí)際應(yīng)用

以上就是一些關(guān)于hash以及其相關(guān)的一些基本預(yù)備知識(shí)。那么在emule里面他具體起到什么作用呢?

大家都知道emule是基于P2P （Peer-to-peer的縮寫，指的是對(duì)等連接的軟件）， 它采用了“多源文件傳輸協(xié)議”（MFTP，the Multisource FileTransfer Protocol）。在協(xié)議中，定義了一系列傳輸、壓縮和打包還有積分的標(biāo)準(zhǔn)，emule 對(duì)于每個(gè)文件都有md5-hash的算法設(shè)置，這使得該文件獨(dú)一無(wú)二，并且在整個(gè)網(wǎng)絡(luò)上都可以追蹤得到。

什么是文件的hash值呢?

MD5-Hash-文件的數(shù)字文摘通過(guò)Hash函數(shù)計(jì)算得到。不管文件長(zhǎng)度如何，它的Hash函數(shù)計(jì)算結(jié)果是一個(gè)固定長(zhǎng)度的數(shù)字。與加密算法不同，這一個(gè)Hash算法是一個(gè)不可逆的單向函數(shù)。采用安全性高的Hash算法，如MD5、SHA時(shí)，兩個(gè)不同的文件幾乎不可能得到相同的Hash結(jié)果。因此，一旦文件被修改，就可檢測(cè)出來(lái)。

當(dāng)我們的文件放到emule里面進(jìn)行共享發(fā)布的時(shí)候，emule會(huì)根據(jù)hash算法自動(dòng)生成這個(gè)文件的hash值，他就是這個(gè)文件唯一的身份標(biāo)志，它包含了這個(gè)文件的基本信息，然后把它提交到所連接的服務(wù)器。當(dāng)有他人想對(duì)這個(gè)文件提出下載請(qǐng)求的時(shí)候， 這個(gè)hash值可以讓他人知道他正在下載的文件是不是就是他所想要的。尤其是在文件的其他屬性被更改之后（如名稱等）這個(gè)值就更顯得重要。而且服務(wù)器還提供了，這個(gè)文件當(dāng)前所在的用戶的地址，端口等信息，這樣emule就知道到哪里去下載了。

一般來(lái)講我們要搜索一個(gè)文件，emule在得到了這個(gè)信息后，會(huì)向被添加的服務(wù)器發(fā)出請(qǐng)求，要求得到有相同hash值的文件。而服務(wù)器則返回持有這個(gè)文件的用戶信息。這樣我們的客戶端就可以直接的和擁有那個(gè)文件的用戶溝通，看看是不是可以從他那里下載所需的文件。

對(duì)于emule中文件的hash值是固定的，也是唯一的，它就相當(dāng)于這個(gè)文件的信息摘要，無(wú)論這個(gè)文件在誰(shuí)的機(jī)器上，他的hash值都是不變的，無(wú)論過(guò)了多長(zhǎng)時(shí)間，這個(gè)值始終如一，當(dāng)我們?cè)谶M(jìn)行文件的下載上傳過(guò)程中，emule都是通過(guò)這個(gè)值來(lái)確定文件。

那么什么是userhash呢?

道理同上，當(dāng)我們?cè)诘谝淮问褂胑mule的時(shí)候，emule會(huì)自動(dòng)生成一個(gè)值，這個(gè)值也是唯一的，它是我們?cè)趀mule世界里面的標(biāo)志，只要你不卸載，不刪除config，你的userhash值也就永遠(yuǎn)不變，積分制度就是通過(guò)這個(gè)值在起作用，emule里面的積分保存，身份識(shí)別，都是使用這個(gè)值，而和你的id和你的用戶名無(wú)關(guān)，你隨便怎么改這些東西，你的userhash值都是不變的，這也充分保證了公平性。其實(shí)他也是一個(gè)信息摘要，只不過(guò)保存的不是文件信息，而是我們每個(gè)人的信息。

那么什么是hash文件呢?

我們經(jīng)常在emule日志里面看到，emule正在hash文件，這里就是利用了hash算法的文件校驗(yàn)性這個(gè)功能了，文章前面已經(jīng)說(shuō)了一些這些功能，其實(shí)這部分是一個(gè)非常復(fù)雜的過(guò)程，在ftp,bt等軟件里面都是用的這個(gè)基本原理，emule里面是采用文件分塊傳輸，這樣傳輸?shù)拿恳粔K都要進(jìn)行對(duì)比校驗(yàn)，如果錯(cuò)誤則要進(jìn)行重新下載，這期間這些相關(guān)信息寫入met文件，直到整個(gè)任務(wù)完成，這個(gè)時(shí)候part文件進(jìn)行重新命名，然后使用move命令，把它傳送到incoming文件里面，然后met文件自動(dòng)刪除，所以我們有的時(shí)候會(huì)遇到hash文件失敗，就是指的是met里面的信息出了錯(cuò)誤不能夠和part文件匹配，另外有的時(shí)候開機(jī)也要瘋狂hash，有兩種情況一種是你在第一次使用，這個(gè)時(shí)候要hash提取所有文件信息，還有一種情況就是上一次你非法關(guān)機(jī)，那么這個(gè)時(shí)候就是要進(jìn)行排錯(cuò)校驗(yàn)了。

關(guān)于hash的算法研究，一直是信息科學(xué)里面的一個(gè)前沿，尤其在網(wǎng)絡(luò)技術(shù)普及的今天，他的重要性越來(lái)越突出，其實(shí)我們每天在網(wǎng)上進(jìn)行的信息交流安全驗(yàn)證，我們?cè)谑褂玫牟僮飨到y(tǒng)密鑰原理，里面都有它的身影，特別對(duì)于那些研究信息安全有興趣的朋友，這更是一個(gè)打開信息世界的鑰匙，他在hack世界里面也是一個(gè)研究的焦點(diǎn)。

一般的線性表、樹中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較”的基礎(chǔ)上，查找的效率與比較次數(shù)密切相關(guān)。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而查找時(shí)，只需根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f找到給定值K的像f（K）。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f（K）的存儲(chǔ)位置上，由此不需要進(jìn)行比較便可直接取得所查記錄。在此，稱這個(gè)對(duì)應(yīng)關(guān)系f為哈希函數(shù)，按這個(gè)思想建立的表為哈希表（又稱為雜湊法或散列表）。

哈希表不可避免沖突（collision）現(xiàn)象：對(duì)不同的關(guān)鍵字可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash（key2）。具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來(lái)說(shuō)稱為同義詞（synonym）。因此，在建造哈希表時(shí)不僅要設(shè)定一個(gè)好的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。可如下描述哈希表：根據(jù)設(shè)定的哈希函數(shù)H（key）和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集（區(qū)間）上并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，這種表被稱為哈希表。

對(duì)于動(dòng)態(tài)查找表而言，（1）表長(zhǎng)不確定；（2）在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。因此，一般情況需建立一個(gè)函數(shù)關(guān)系，以f（key）作為關(guān)鍵字為key的錄在表中的位置，通常稱這個(gè)函數(shù)f（key）為哈希函數(shù)。（注意：這個(gè)函數(shù)并不一定是數(shù)學(xué)函數(shù)）

哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可。

現(xiàn)實(shí)中哈希函數(shù)是需要構(gòu)造的，并且構(gòu)造的好才能使用的好。

用途：加密，解決沖突問(wèn)題。

用途很廣，比特精靈中就使用了哈希函數(shù)，你可以自己看看。

具體可以學(xué)習(xí)一下數(shù)據(jù)結(jié)構(gòu)和算法的書。

字符串

（著名的ELFhash算法）

<pre data-lang="cpp">int?ELFhash(char*key){????unsigned?long?h=0;????while(*key)????{????????h?=?(h?<<?4)?+?*key++;????????unsigned?long?g?=?h?&?0xF0000000L;????????if(g)????????????h?^=?g?>>?24;????????h?&=?~g;????}????return?h?%?MOD;}