散列法

散列法（Hashing）或哈希法是一種將字元組成的字元串轉換為固定長度（一般是更短長度）的數值或索引值的方法，稱為散列法，也叫哈希法。由於通過更短的哈希值比用原始值進行資料庫搜尋更快，這種方法一般用來在資料庫中建立索引並進行搜尋，同時還用在各種解密算法中。

基本介紹

• 中文名：散列法
• 外文名：Hashing
• 又名：哈希法
• 用途：在資料庫中建立索引並進行搜尋

定義

比如，在資料庫中存儲一些人名，排列方式可能是下面這樣：

Abernathy, Sara

Epperdingle, Roscoe

Moore, Wilfred

Smith, David

所有名字均按字母排序......

可以利用這些名字本身來作為資料庫的索引值。資料庫搜尋算法首先會逐個字元的進行名字的搜尋，直到找到為止。但是如果利用散列法對每個名字進行了轉換，就可能為資料庫中的每一個名字產生一個四位的索引值，其中位數長度取決於資料庫中到底有多少個人名，象下面這樣：

7864 Abernathy, Sara

9802 Epperdingle, Roscoe

1990 Moore, Wilfred

8822 Smith, David

等等......

這樣，下次搜尋名字時，就先搜尋哈希並對資料庫中的每個值進行一一對應。通常來講，尋找四位的數字比尋找未知長度的字元串要來得快得多。畢竟尋找數字時每一位只有10種可能，而名字的長度未定，且每一位都有26種可能。

散列算法

也稱為哈希函式——哈希的英文意思為“無用信息”，因此哈希函式一詞的由來可能是因為最終形成的哈希表裡面是各種看起來。除用來快速搜尋數據外，散列法還用來完成簽名的加密解密工作，這種簽名可以用來對收發訊息時的用戶簽名進行鑒權。先用哈希函式對數據簽名進行轉換，然後將數字簽名本身和轉換後的信息摘要分別獨立的傳送給接收人。通過利用和傳送人一樣的哈希函式，接收人可以從數字簽名獲得一個信息摘要，然後將此摘要同傳送過來的摘要進行比較，這兩個值相等則表示數字簽名有效。

利用哈希函式對資料庫中的原始值建立索引，以後每獲取一次數據時都要利用哈希函式進行重新轉換。因此，哈希函式始終是單向操作。沒有必要通過分析哈希值來試圖逆推哈希函式。實際上，一個典型的哈希函式是不可能逆推出來的。好的哈希函式還應該避免對於不同輸入產生相同的哈希值的情況發生。如果產生了哈希值相同的情況，稱為衝突。可接受的哈希函式應該將衝突情況的可能性降到非常小。

哈希函式

1）餘數法：先估計整個哈希表中的表項目數目大小。然後用這個估計值作為除數去除每個原始值，得到商和餘數。用餘數作為哈希值。因為這種方法產生衝突的可能性相當大，因此任何搜尋算法都應該能夠判斷衝突是否發生並提出取代算法。

2）摺疊法：這種方法是針對原始值為數字時使用，將原始值分為若干部分，然後將各部分疊加，得到的最後四個數字（或者取其他位數的數字都可以）來作為哈希值。

3）基數轉換法：當原始值是數字時，可以將原始值的數制基數轉為一個不同的數字。例如，可以將十進制的原始值轉為十六進制的哈希值。為了使哈希值的長度相同，可以省略高位數字。

4）數據重排法：這種方法只是簡單的將原始值中的數據打亂排序。比如可以將第三位到第六位的數字逆序排列，然後利用重排後的數字作為哈希值。

哈希函式並不通用，比如在資料庫中用能夠獲得很好效果的哈希函式，用在密碼學或錯誤校驗方面就未必可行。在密碼學領域有幾個著名的哈希函式。這些函式包括 MD2、MD4以及MD5，利用散列法將數字簽名轉換成的哈希值稱為信息摘要（message－digest），另外還有安全散列算法（SHA），這是一種標準算法，能夠生成更大的（60bit）的信息摘要，有點兒類似於MD4算法。