首頁(yè) 新隨筆新文章聯(lián)系聚合

posts - 269,comments - 32,trackbacks - 0

2013年1月

>

日

一

二

三

四

五

六

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

常用鏈接

留言簿(3)

隨筆分類(lèi)(267)

隨筆檔案(269)

常用鏈接

CODEGURU
CODEPROJECT
CSDN
MSDN
MULTI-PLATFORM
NSIS
PUDN
VC-CCTRY
VCKBASE

朋友博客

程序描繪人生
胡滿超的技術(shù)博客
用自信照亮人生

推薦博客

ggjucheng
k-eckel
Kevin Lynx
陳皓
羅朝輝（飄飄白云）

搜索

積分與排名

積分 - 757245
排名 - 21

閱讀排行榜

評(píng)論排行榜

（轉(zhuǎn)載）經(jīng)典的String Hash算法

設(shè)計(jì)高效算法往往需要使用Hash表，O(1)級(jí)的查找速度是任何別的算法無(wú)法比擬的。
所謂Hash，一般是一個(gè)整數(shù)，通過(guò)某種算法，可以把一個(gè)字符串"pack"成一個(gè)整數(shù)，這個(gè)數(shù)稱(chēng)為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是一種非常流行的算法，俗稱(chēng)"Times33"算法。Times33的算法很簡(jiǎn)單，就是不斷的乘33，原型如下

hash(i) = hash(i-1) * 33 + str[i]

Time33在效率和隨機(jī)性?xún)煞矫嫔暇慵选?/span>

其它常用字符串哈希函數(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/#RSHashFunction

Blizzard使用的算法比較精妙，被稱(chēng)為"One-Way Hash"，并且在Hash表中使用了三個(gè)哈希值(一個(gè)用來(lái)確定位置，另外兩個(gè)用來(lái)校驗(yàn))。

MD5等加密算法也屬于hash，不過(guò)已被中國(guó)學(xué)者找到碰撞檢測(cè)的破解算法

本文轉(zhuǎn)自：http://m.shnenglu.com/humanchao/archive/2012/12/26/196690.html

posted on 2013-01-07 16:29 王海光閱讀(1790) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): 算法

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: （轉(zhuǎn)載）海明距離（轉(zhuǎn)載）大小端問(wèn)題（轉(zhuǎn)載）循環(huán)有序數(shù)組查找問(wèn)題（轉(zhuǎn)載）經(jīng)典的String Hash算法散列表（哈希表）算法導(dǎo)論——基數(shù)排序（網(wǎng)易公開(kāi)課）算法導(dǎo)論——計(jì)數(shù)排序（網(wǎng)易公開(kāi)課）（轉(zhuǎn)）優(yōu)秀博客推薦：各種數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)入門(mén)經(jīng)典（不斷更新) 最短路徑算法—Floyd(弗洛伊德)算法分析與實(shí)現(xiàn)(C/C++) （轉(zhuǎn)）最短路徑算法—Dijkstra(迪杰斯特拉)算法分析與實(shí)現(xiàn)(C/C++)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(3)

隨筆分類(lèi)(267)

隨筆檔案(269)

常用鏈接

朋友博客

推薦博客

最新隨筆

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜