散列法

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

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算法。