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