-
雜湊算法
鎖定
雜湊(Hashing) 是電腦科學中一種對資料的處理方法，通過某種特定的函數/算法（稱為雜湊函數/算法）將要檢索的項與用來檢索的索引（稱為雜湊，或者雜湊值）關聯起來，生成一種便於搜索的數據結構（稱為雜湊表）。也譯為散列。舊譯哈希（誤以為是人名而採用了音譯）。它也常用作一種資訊安全的實作方法，由一串資料中經過雜湊算法 (Hashing algorithms) 計算出來的資料指紋 (data fingerprint)，經常用來識別檔案與資料是否有被竄改，以保證檔案與資料確實是由原創者所提供。
如今，雜湊算法也被用來加密存在數據庫中的密碼 (password) 字串，由於雜湊算法所計算出來的雜湊值 (Hash Value) 具有不可逆 (無法逆向演算回原本的數值) 的性質，因此可有效的保護密碼。
[1]
- 類 型
- 經濟術語
有時候雜湊函數是一個壓縮映像，因此不可避免會發生衝突，因此在建造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有應用。
- 參考資料
-
- 1. 雜湊算法 ．MBA智庫[引用日期2020-06-25]
