哈希演算法

出自 MBA智库百科(https://wiki.mbalib.com/)

哈希演算法（Hash 演算法，Hash 算式，散列演算法，消息摘要演算法）

　　哈希演算法將任意長度的二進位值映射為較短的固定長度的二進位值，這個小的二進位值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨後的哈希都將產生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的，所以數據的哈希值可以檢驗數據的完整性。一般用於快速查找和加密演算法。

　　哈希表是根據設定的哈希函數H(key)和處理衝突方法將一組關鍵字映射到一個有限的地址區間上，並以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比，哈希表無疑是查找速度比較快的一種。

　　通過將單向數學函數（有時稱為“哈希演算法”）應用到任意數量的數據所得到的固定大小的結果。如果輸入數據中有變化，則哈希也會發生變化。哈希可用於許多操作，包括身份驗證和數字簽名。也稱為“消息摘要”。

　　簡單解釋：哈希(Hash)演算法,即散列函數。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時,哈希函數可以將任意長度的輸入經過變化以後得到固定長度的輸出。哈希函數的這種單向特征和輸出數據長度固定的特征使得它可以生成消息或者數據。

　　哈希演算法(散列演算法或者消息摘要演算法)是信息存儲和查詢所用的一項基本技術，它是一種基於Hash函數的文件構造方法，可實現對記錄的快速隨機存取。它把給定的任意長關鍵宇映射為一個固定長度的哈希值，一般用於鑒權、認證、加密、索引等。其主要優點是運算簡單，預處理時間較短，記憶體消耗低，匹配查找速度比較快，便於維護和刷新，支持匹配規則數多等。

　　(1)單向性。即給定一個輸入數，容易計算出它的哈希值，但是已知一個哈希值根據同樣的演算法不能得到原輸入數。

　　(2)弱抗碰撞性。即給定一個輸入數，要找到另一個得到給定數的哈希值，在使用同一種方法時，在計算上不可行。

　　(3)強抗碰撞性。即對於任意兩個不同的輸入數，根據同樣的演算法計算出相同的哈希值，在計算上不可行。

　　哈希演算法查找法易於實現，存儲需求小，支持範圍匹配和動態更新，但其效率受規則的分佈情況和規則數量影響大，當有衝突時，查找時間比較長。

　　用來產生一些數據片段（例如消息或會話項）的哈希值的演算法。使用好的哈希演算法，在輸入數據中所做的更改就可以更改結果哈希值中的所有位；因此，哈希對於檢測數據對象（例如消息）中的修改很有用。此外，好的哈希演算法使得構造兩個相互獨立且具有相同哈希的輸入不能通過計算方法實現。典型的哈希演算法包括 MD2、MD4、MD5 和 SHA-1。哈希演算法也稱為“哈希函數”。

　　另請參閱： 基於哈希的消息驗證模式 (HMAC), MD2, MD4, MD5,消息摘要, 安全哈希演算法 (SHA-1)。

　　MD5一種符合工業標準的單向 128 位哈希方案，由 RSA Data Security, Inc. 開發。 各種“點對點協議(PTP)”供應商都將它用於加密的身份驗證。哈希方案是一種以結果唯一併且不能返回到其原始格式的方式來轉換數據（如密碼）的方法。質詢握手身份驗證協議(CHAP) 使用質詢響應併在響應時使用單向 MD5哈希法。按照此方式，您無須通過網路發送密碼就可以向伺服器證明您知道密碼。

　　質詢握手身份驗證協議(CHAP)“點對點協議(PPP)”連接的一種質詢響應驗證協議，在 RFC 1994 中有所描述。 該協議使用業界標準 MD5哈希演算法來哈希質詢串（由身份驗證伺服器所發佈）和響應中的用戶密碼的組合。

　　點對點協議

　　用點對點鏈接來傳送多協議數據報的行業標準協議套件。RFC 1661 中有關於 點對點協議（PPP） 的文檔。

　　另請參閱： 壓縮控制協議 (CCP)，遠程訪問，征求意見文檔 (RFC)，傳輸控制協議/Internet 協議 (TCP/IP)，自主隧道。

　　哈希演算法在用於分類時，需要考慮不同關鍵字之間哈希值可能發生的地址衝突。一般採用的是開放定址法來解決衝突，即建立衝突解除區，並使用鏈表在衝突解除區中存放衝突的關鍵字。如圖1所示，當不同的輸入產生相同的Hash值時，後輸入的數將被以鏈表的形式存放在衝突解除區中。衝突的數越多，該Hash值後面的鏈表越長。在進行信息檢索時，如果所需的信息存放在衝突解除區或者沒有，由於輸出為輸入的散列值，需要遍歷衝突解除區中的該鏈表。因此，常規的Hash演算法用於對網路中數據包分類還存在如下的問題：當哈希演算法選擇不當的情況下，可能會造成較多碰撞，導致性能下降，最壞性能不能保證：運算量較大：不能針對不同的規則集通過優化來獲得一個最低的衝突率。

　　儘管提出了多種改進的方案，如雙Hash機制、可擴展Hash演算法等以解決這些問題。但是Hash演算法運用於海量信息查詢時，仍然存在上述效率較低的問題。