設計高效算法往往需要使用Hash表，O(1)級的查找速度是任何別的算法無法比擬的。所謂Hash，一般是一個整數，通過某種算法，可以把一個字符串"pack"成一個整數，這個數稱為Hash，當然，一個整數是無法對應一個字符串的。所以Hash函數是Hash表最核心的部分，對于一個Hash函數，評價其優劣的標準應為隨機性或離散性，即對任意一組標本，進入Hash表每一個單元（cell）之概率的平均程度，因為這個概率越平均，兩個字符串計算出的Hash值相等hash collision的可能越小，數據在表中的分布就越平均，表的空間利用率就越高。Hash表的構造和沖突的不同實現方法對執行效率也有一定的影響.DJBHash是一種非常流行的算法，俗稱"Times33"算法。Times33的算法很簡單，就是不斷的乘33，原型如下hash(i) = hash(i-1) * 33 + str[i]Time33在效率和隨機性兩方面上俱佳。其它常用字符串哈希函數有：BKDRHash，APHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等。BKDRHash和APHash也是比較優秀的算法。當然要根據具體應用選擇合適的Hash算法，比如字符集的考慮。APHash作者Arash Partow有一個頁面很有參考價值，包括了各種Hash的介紹及代碼。http://www.partow.net/programming/hashfunctions/#RSHashFunctionBlizzard使用的算法比較精妙，被稱為"One-Way Hash"，并且在Hash表中使用了三個哈希值(一個用來確定位置，另外兩個用來校驗)。MD5等加密算法也屬于hash，不過已被中國學者找到碰撞檢測的破解算法
本文轉自：http://www.shnenglu.com/humanchao/archive/2012/12/26/196690.html
posted on 2013-01-07 16:29
王海光 閱讀(1777)
評論(0) 編輯 收藏 引用 所屬分類:
算法