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