散列法（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）摺疊法：這種方法是針對原始值為數字時使用，將原始值分為若干部分，然後將各部分疊加，得到的最後四個數字（或者取其他位數的數字都可以）來作為哈希值。
4）數據重排法：這種方法只是簡單的將原始值中的數據打亂排序。比如可以將第三位到第六位的數字逆序排列，然後利用重排後的數字作為哈希值。
