Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡?，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡(jiǎn)單的說就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。

　　哈希表是根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突方法將一組關(guān)鍵字映射到一個(gè)有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的象作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表或散列，所得存儲(chǔ)位置稱為哈希地址或散列地址。作為線性數(shù)據(jù)結(jié)構(gòu)與表格和隊(duì)列等相比，哈希表無疑是查找速度比較快的一種。

　　通過將單向數(shù)學(xué)函數(shù)（有時(shí)稱為“哈希算法”）應(yīng)用到任意數(shù)量的數(shù)據(jù)所得到的固定大小的結(jié)果。如果輸入數(shù)據(jù)中有變化，則哈希也會(huì)發(fā)生變化。哈?？捎糜谠S多操作，包括身份驗(yàn)證和數(shù)字簽名。也稱為“消息摘要”。

　　簡(jiǎn)單解釋：哈希（Hash）算法，即散列函數(shù)。它是一種單向密碼體制，即它是一個(gè)從明文到密文的不可逆的映射，只有加密過程，沒有解密過程。同時(shí)，哈希函數(shù)可以將任意長(zhǎng)度的輸入經(jīng)過變化以后得到固定長(zhǎng)度的輸出。哈希函數(shù)的這種單向特征和輸出數(shù)據(jù)長(zhǎng)度固定的特征使得它可以生成消息或者數(shù)據(jù)。

　　常用hash算法的介紹：

　?。?）MD4

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

　?。?）MD5

　　MD5（RFC 1321）是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)，與 MD4 相同。MD5比MD4來得復(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算法的原理

　　散列表，它是基于快速存取的角度設(shè)計(jì)的，也是一種典型的“空間換時(shí)間”的做法。顧名思義，該數(shù)據(jù)結(jié)構(gòu)可以理解為一個(gè)線性表，但是其中的元素不是緊密排列的，而是可能存在空隙。

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

　　比如我們存儲(chǔ)70個(gè)元素，但我們可能為這70個(gè)元素申請(qǐng)了100個(gè)元素的空間。70/100=0.7，這個(gè)數(shù)字稱為負(fù)載因子。我們之所以這樣做，也是為了“快速存取”的目的。我們基于一種結(jié)果盡可能隨機(jī)平均分布的固定函數(shù)H為每個(gè)元素安排存儲(chǔ)位置，這樣就可以避免遍歷性質(zhì)的線性搜索，以達(dá)到快速存取。但是由于此隨機(jī)性，也必然導(dǎo)致一個(gè)問題就是沖突。所謂沖突，即兩個(gè)元素通過散列函數(shù)H得到的地址相同，那么這兩個(gè)元素稱為“同義詞”。這類似于70個(gè)人去一個(gè)有100個(gè)椅子的飯店吃飯。散列函數(shù)的計(jì)算結(jié)果是一個(gè)存儲(chǔ)單位地址，每個(gè)存儲(chǔ)單位稱為“桶”。設(shè)一個(gè)散列表有m個(gè)桶，則散列函數(shù)的值域應(yīng)為［0，m-1］。

　　解決沖突是一個(gè)復(fù)雜問題。

　　沖突主要取決于：

　?。?）散列函數(shù)，一個(gè)好的散列函數(shù)的值應(yīng)盡可能平均分布。

　?。?）處理沖突方法。

　?。?）負(fù)載因子的大小。太大不一定就好，而且浪費(fèi)空間嚴(yán)重，負(fù)載因子和散列函數(shù)是聯(lián)動(dòng)的。

　　解決沖突的辦法：

　　（1）線性探查法：沖突后，線性向前試探，找到最近的一個(gè)空位置。缺點(diǎn)是會(huì)出現(xiàn)堆積現(xiàn)象。存取時(shí)，可能不是同義詞的詞也位于探查序列，影響效率。

　　（2）雙散列函數(shù)法：在位置d沖突后，再次使用另一個(gè)散列函數(shù)產(chǎn)生一個(gè)與散列表桶容量m互質(zhì)的數(shù)c，依次試探（d+n*c）%m，使探查序列跳躍式分布。

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

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

　　1. 直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H（key）=key或H（key） = a？key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）

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

　　3. 平方取中法：取關(guān)鍵字平方后的中間幾位作為散列地址。

　　4. 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。

　　5. 隨機(jī)數(shù)法：選擇一隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)值作為散列地址，通常用于關(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)生同義詞。

　　查找的性能分析

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

　　查找過程中，關(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 可以說是目前應(yīng)用最廣泛的Hash算法，而它們都是以 MD4 為基礎(chǔ)設(shè)計(jì)的。那么他們都是什么意思呢？

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

　　（1） MD4

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

　?。?） MD5

　　MD5（RFC 1321）是 Rivest 于1991年對(duì)MD4的改進(jìn)版本。它對(duì)輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)，與 MD4 相同。MD5比MD4來得復(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相同原理，并且模仿了該算法。

　　哈希表不可避免沖突（collision）現(xiàn)象：對(duì)不同的關(guān)鍵字可能得到同一哈希地址 即key1≠key2，而hash（key1）=hash（key2）。因此，在建造哈希表時(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)造的好才能使用的好。

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

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

　　（1） 文件校驗(yàn)

　　我們比較熟悉的校驗(yàn)算法有奇偶校驗(yàn)和CRC校驗(yàn)，這2種校驗(yàn)并沒有抗數(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)單而安全的方法。

　　文件hash值

　　MD5-Hash-文件的數(shù)字文摘通過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è)出來。

　　Hash函數(shù)還有另外的含義。實(shí)際中的Hash函數(shù)是指把一個(gè)大范圍映射到一個(gè)小范圍。把大范圍映射到一個(gè)小范圍的目的往往是為了節(jié)省空間，使得數(shù)據(jù)容易保存。除此以外，Hash函數(shù)往往應(yīng)用于查找上。所以，在考慮使用Hash函數(shù)之前，需要明白它的幾個(gè)限制：

　　1. Hash的主要原理就是把大范圍映射到小范圍；所以，你輸入的實(shí)際值的個(gè)數(shù)必須和小范圍相當(dāng)或者比它更小。不然沖突就會(huì)很多。

　　2. 由于Hash逼近單向函數(shù)；所以，你可以用它來對(duì)數(shù)據(jù)進(jìn)行加密。

　　3. 不同的應(yīng)用對(duì)Hash函數(shù)有著不同的要求；比如，用于加密的Hash函數(shù)主要考慮它和單項(xiàng)函數(shù)的差距，而用于查找的Hash函數(shù)主要考慮它映射到小范圍的沖突率。

　　應(yīng)用于加密的Hash函數(shù)已經(jīng)探討過太多了，在作者的博客里面有更詳細(xì)的介紹。所以，本文只探討用于查找的Hash函數(shù)。

　　Hash函數(shù)應(yīng)用的主要對(duì)象是數(shù)組（比如，字符串），而其目標(biāo)一般是一個(gè)int類型。以下我們都按照這種方式來說明。

　　一般的說，Hash函數(shù)可以簡(jiǎn)單的劃分為如下幾類：

　　1. 加法Hash；

　　2. 位運(yùn)算Hash；

　　3. 乘法Hash；

　　4. 除法Hash；

　　5. 查表Hash；

　　6. 混合Hash；