雜湊演算法

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

雜湊演算法（Hashing algorithms）

　　雜湊(Hashing) 是電腦科學中一種對資料的處理方法，通過某種特定的函數/演算法（稱為雜湊函數/演算法）將要檢索的項與用來檢索的索引（稱為雜湊，或者雜湊值）關聯起來，生成一種便於搜索的數據結構（稱為雜湊表）。也譯為散列。舊譯哈希（誤以為是人名而採用了音譯）。它也常用作一種資訊安全的實作方法，由一串資料中經過雜湊演算法 (Hashing algorithms) 計算出來的資料指紋 (data fingerprint)，經常用來識別檔案與資料是否有被竄改，以保證檔案與資料確實是由原創者所提供。

　　如今，雜湊演算法也被用來加密存在資料庫中的密碼 (password) 字串，由於雜湊演算法所計算出來的雜湊值 (Hash Value) 具有不可逆 (無法逆向演算回原本的數值) 的性質，因此可有效的保護密碼。

　　有時候雜湊函數是一個壓縮映像，因此不可避免會發生衝突，因此在建造hash’函數的時候不僅要設定一個好的hash函數，還要設定一種處理衝突的方法，哈希造表，散列表。

　　1、直接定址法 ：地址集合和關鍵字集合大小相同

　　2、數字分析法 ：根據需要hash的 關鍵字的特點選擇合適hash演算法，儘量尋找每個關鍵字的不同點。

　　3、平方取中法：取關鍵字平方之後的中間極為作為哈希地址，一個數平方之後中間幾位數字與數的每一位都相關，取得位數由表長決定。比如：表長為512,=2^9,可以取平方之後中間9位二進位數作為哈希地址。

　　4、摺疊法：關鍵字位數很多，而且關鍵字中每一位上的數字分佈大致均勻的時候，可以採用摺疊法得到哈希地址，

　　5、除留取餘法除P取餘，可以選P為質數，或者不含有小於20的質因數的合數

　　6、隨機數法：通常關鍵字不等的時候採用此法構造哈希函數較恰當。

　　實際工作中需要視不同的情況採用不同的hash函數：

　　1、考慮因素：計算哈希函數所需要的時間，硬體指令等因素。

　　2、關鍵字長度

　　3、哈希表大小

　　4、關鍵字分佈情況

　　5、記錄查找的頻率。（huffeman樹）

　　處理衝突的方法：

　　開放地址法：現行探測再散列，只要哈希表為填滿，總能找到一個不衝突的地址，二次探測再散列 表長為素數時才可能保證總能找到一個不衝突的地址，隨機探測再散列取決於偽隨機數列。

　　再哈希法：不易發生聚集，但是增加了計算的時間

　　鏈地址法；Chord協議中，一致性hash有應用。

　　對不同hash函數以及處理衝突的方法，計算了查找成功的平均長度以及不成功的平均長度。這些結果主要取決於裝填因數，裝填因數，可以將平均查找長度限定在一個範圍內。