「資料結構與演算法」雜湊演算法的原理和應用詳解

在程式設計師的實際開發中，雜湊演算法常常能用得到，本文以雜湊演算法的原理和應用為核心，和大家詳細講解一下雜湊演算法的概念、常見演算法以及原理、在資訊保安的應用等等。

一、概念

雜湊表就是一種以鍵-值（key-indexed）儲存資料的結構，我們只要輸入待查詢的值即key，即可查詢到其對應的值。雜湊的思路很簡單，如果所有的鍵都是整數，那麼就可以使用一個簡單的無序陣列來實現：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對於簡單的鍵的情況，我們將其擴充套件到可以處理更加複雜的型別的鍵。

使用雜湊查詢有兩個步驟:

1。使用雜湊函式將被查詢的鍵轉換為陣列的索引。在理想的情況下，不同的鍵會被轉換為不同的索引值，但是在有些情況下我們需要處理多個鍵被雜湊到同一個索引值的情況。所以雜湊查詢的第二個步驟就是處理衝突。

2。處理雜湊碰撞衝突。有很多處理雜湊碰撞衝突的方法，本文後面會介紹拉鍊法和線性探測法。雜湊表是一個在時間和空間上做出權衡的經典例子。如果沒有記憶體限制，那麼可以直接將鍵作為陣列的索引。那麼所有的查詢時間複雜度為O（1）；如果沒有時間限制，那麼我們可以使用無序陣列並進行順序查詢，這樣只需要很少的記憶體。雜湊表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調整雜湊函式演算法即可在時間和空間上做出取捨。

在Hash表中，記錄在表中的位置和其關鍵字之間存在著一種確定的關係。這樣我們就能預先知道所查關鍵字在表中的位置，從而直接透過下標找到記錄。使ASL趨近於0。

1）雜湊（Hash）函式是一個映象，即將關鍵字的集合對映到某個地址集合上，它的設定很靈活，只要這個地址集合的大小不超出允許範圍即可；

2）由於雜湊函式是一個壓縮映象，因此，在一般情況下，很容易產生“衝突”現象，即： key1！=key2，而 f （key1） = f（key2）。

3）只能儘量減少衝突而不能完全避免衝突，這是因為通常關鍵字集合比較大，其元素包括所有可能的關鍵字，而地址集合的元素僅為雜湊表中的地址。在構造這種特殊的“查詢表” 時，除了需要選擇一個“好”（儘可能少產生衝突）的雜湊函式之外；還需要找到一種“處理衝突” 的方法。

二、常用雜湊演算法的介紹：

1.MD4

MD4（RFC 1320）是 MIT 的Ronald L。 Rivest在 1990 年設計的，MD 是 Message Digest（訊息摘要）的縮寫。它適用在32位字長的處理器上用高速軟體實現——它是基於 32位運算元的位操作來實現的。

2.MD5

MD5（RFC 1321）是 Rivest 於1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。MD5比MD4來得複雜，並且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。

3.SHA-1及其他

SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小於264的輸入，產生長度為160bit的雜湊值，因此抗窮舉（brute-force）性更好。SHA-1 設計師基於和MD4相同原理，並且模仿了該演算法。

三、常見雜湊演算法的原理

散列表，它是基於快速存取的角度設計的，也是一種典型的“空間換時間”的做法。顧名思義，該資料結構可以理解為一個線性表，但是其中的元素不是緊密排列的，而是可能存在空隙。

散列表（Hash table，也叫雜湊表），是根據關鍵碼值（Key value）而直接進行訪問的資料結構。也就是說，它透過把關鍵碼值對映到表中一個位置來訪問記錄，以加快查詢的速度。這個對映函式叫做雜湊函式，存放記錄的陣列叫做散列表。

比如我們儲存70個元素，但我們可能為這70個元素申請了100個元素的空間。70/100=0。7，這個數字稱為負載因子。我們之所以這樣做，也是為了“快速存取”的目的。我們基於一種結果儘可能隨機平均分佈的固定函式H為每個元素安排儲存位置，這樣就可以避免遍歷性質的線性搜尋，以達到快速存取。但是由於此隨機性，也必然導致一個問題就是衝突。所謂衝突，即兩個元素透過雜湊函式H得到的地址相同，那麼這兩個元素稱為“同義詞”。這類似於70個人去一個有100個椅子的飯店吃飯。雜湊函式的計算結果是一個儲存單位地址，每個儲存單位稱為“桶”。設一個散列表有m個桶，則雜湊函式的值域應為［0，m-1］。