在程序員的實際開發(fā)中，哈希算法常常能用得到，本文以哈希算法的原理和應用為核心，和大家詳細講解一下哈希算法的概念、常見算法以及原理、在信息安全的應用等等。
一、概念
哈希表就是一種以 鍵-值(key-indexed) 存儲數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key，即可查找到其對應的值。哈希的思路很簡單，如果所有的鍵都是整數(shù)，那么就可以使用一個簡單的無序數(shù)組來實現(xiàn)：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復雜的類型的鍵。
使用哈希查找有兩個步驟:
1. 使用哈希函數(shù)將被查找的鍵轉(zhuǎn)換為數(shù)組的索引。在理想的情況下，不同的鍵會被轉(zhuǎn)換為不同的索引值，但是在有些情況下我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理沖突。
2. 處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文后面會介紹拉鏈法和線性探測法。哈希表是一個在時間和空間上做出權(quán)衡的經(jīng)典例子。如果沒有內(nèi)存限制，那么可以直接將鍵作為數(shù)組的索引。那么所有的查找時間復雜度為O(1)；如果沒有時間限制，那么我們可以使用無序數(shù)組并進行順序查找，這樣只需要很少的內(nèi)存。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調(diào)整哈希函數(shù)算法即可在時間和空間上做出取舍。
在Hash表中，記錄在表中的位置和其關(guān)鍵字之間存在著一種確定的關(guān)系。這樣我們就能預先知道所查關(guān)鍵字在表中的位置，從而直接通過下標找到記錄。使ASL趨近于0.
1)哈希(Hash)函數(shù)是一個映象，即將關(guān)鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可；
2)由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即： key1！=key2，而 f (key1) = f(key2)。
3)只能盡量減少沖突而不能完全避免沖突，這是因為通常關(guān)鍵字集合比較大，其元素包括所有可能的關(guān)鍵字， 而地址集合的元素僅為哈希表中的地址。在構(gòu)造這種特殊的“查找表” 時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一 種“處理沖突” 的方法。
二、常用哈希算法的介紹：
1.MD4
MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年設計的，MD 是 Message Digest（消息摘要） 的縮寫。它適用在32位字長的處理器上用高速軟件實現(xiàn)——它是基于 32位操作數(shù)的位操作來實現(xiàn)的。
2.MD5
MD5（RFC 1321）是 Rivest 于1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯(lián)，與 MD4 相同。MD5比MD4來得復雜，并且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現(xiàn)更好。
3.SHA-1及其他
SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小于264的輸入，產(chǎn)生長度為160bit的散列值，因此抗窮舉（brute-force）性更好。SHA-1 設計師基于和MD4相同原理，并且模仿了該算法。
三、常見哈希算法的原理
散列表，它是基于快速存取的角度設計的，也是一種典型的“空間換時間”的做法。顧名思義，該數(shù)據(jù)結(jié)構(gòu)可以理解為一個線性表，但是其中的元素不是緊密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值（Key value）而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
比如我們存儲70個元素，但我們可能為這70個元素申請了100個元素的空間。70/100=0.7，這個數(shù)字稱為負載因子。我們之所以這樣做，也是為了“快速存取”的目的。我們基于一種結(jié)果盡可能隨機平均分布的固定函數(shù)H為每個元素安排存儲位置，這樣就可以避免遍歷性質(zhì)的線性搜索，以達到快速存取。但是由于此隨機性，也必然導致一個問題就是沖突。所謂沖突，即兩個元素通過散列函數(shù)H得到的地址相同，那么這兩個元素稱為“同義詞”。這類似于70個人去一個有100個椅子的飯店吃飯。散列函數(shù)的計算結(jié)果是一個存儲單位地址，每個存儲單位稱為“桶”。設一個散列表有m個桶，則散列函數(shù)的值域應為［0，m-1］。
四、Hash算法在信息安全方面的應用
1.文件校驗
我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗并沒有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測并糾正數(shù)據(jù)傳輸中的信道誤碼，但卻不能防止對數(shù)據(jù)的惡意破壞。
MD5 Hash算法的“數(shù)字指紋”特性，使它成為目前應用最廣泛的一種文件完整性校驗和（Checksum）算法，不少Unix系統(tǒng)有提供計算md5 checksum的命令。
2.數(shù)字簽名
Hash 算法也是現(xiàn)代密碼體系中的一個重要組成部分。由于非對稱算法的運算速度較慢，所以在數(shù)字簽名協(xié)議中，單向散列函數(shù)扮演了一個重要的角色。 對 Hash 值，又稱“數(shù)字摘要”進行數(shù)字簽名，在統(tǒng)計上可以認為與對文件本身進行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點。
3.鑒權(quán)協(xié)議
鑒權(quán)協(xié)議又被稱作挑戰(zhàn)--認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
以上就是哈希算法的原理和應用詳解，不知道大家都明白了嗎？
另外，對現(xiàn)在我們的大多數(shù)朋友來說還是學編程技術(shù)最重要！栽一棵樹最好的時間是十年前，其次是現(xiàn)在。對于準備學習編程的小伙伴，如果你想更好地提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！
