一江春水向東流

做一個有思想的人,期待與每一位熱愛思考的人交流,您的關(guān)注是對我最大的支持。

BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

44 隨筆 :: 139 文章 :: 81 評論 :: 0 Trackbacks

<

2025年7月

>

日

一

二

三

四

五

六

29

30

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

常用鏈接

留言簿(12)

隨筆分類(23)

隨筆檔案(42)

文章分類(162)

文章檔案(139)

新聞檔案(10)

2006年11月 (10)

相冊

收藏夾(3)

技術(shù)文章(3) (rss)

搜索

閱讀排行榜

評論排行榜

若干經(jīng)典的字符串哈希函數(shù)

// ?RS?Hash?Function

unsigned? int ?RSHash( char ? * str)

{

????????unsigned? int ?b? = ? 378551 ;

????????unsigned? int ?a? = ? 63689 ;

????????unsigned? int ?hash? = ? 0 ;

???????? while ?( * str)

???????? {

????????????????hash? = ?hash? * ?a? + ?( * str ++ );

????????????????a? *= ?b;

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?JS?Hash?Function

unsigned? int ?JSHash( char ? * str)

{

????????unsigned? int ?hash? = ? 1315423911 ;

???????? while ?( * str)

???????? {

????????????????hash? ^= ?((hash? << ? 5 )? + ?( * str ++ )? + ?(hash? >> ? 2 ));

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?P.?J.?Weinberger?Hash?Function

unsigned? int ?PJWHash( char ? * str)

{

????????unsigned? int ?BitsInUnignedInt? = ?(unsigned? int )( sizeof (unsigned? int )? *

8 );

????????unsigned? int ?ThreeQuarters???? = ?(unsigned? int )((BitsInUnignedInt?? * ? 3 )

? / ? 4 );

????????unsigned? int ?OneEighth???????? = ?(unsigned? int )(BitsInUnignedInt? / ? 8 );

????????unsigned? int ?HighBits????????? = ?(unsigned? int )( 0xFFFFFFFF )? << ?(BitsInU

nignedInt? - ?OneEighth);

????????unsigned? int ?hash????????????? = ? 0 ;

????????unsigned? int ?test????????????? = ? 0 ;

???????? while ?( * str)

???????? {

????????????????hash? = ?(hash? << ?OneEighth)? + ?( * str ++ );

???????????????? if ?((test? = ?hash? & ?HighBits)? != ? 0 )

???????????????? {

????????????????????????hash? = ?((hash? ^ ?(test? >> ?ThreeQuarters))? & ?( ~ HighBits)

);

????????????????}

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?ELF?Hash?Function

unsigned? int ?ELFHash( char ? * str)

{

????????unsigned? int ?hash? = ? 0 ;

????????unsigned? int ?x???? = ? 0 ;

???????? while ?( * str)

???????? {

????????????????hash? = ?(hash? << ? 4 )? + ?( * str ++ );

???????????????? if ?((x? = ?hash? & ? 0xF0000000L )? != ? 0 )

???????????????? {

????????????????????????hash? ^= ?(x? >> ? 24 );

????????????????????????hash? &= ? ~ x;

????????????????}

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?BKDR?Hash?Function

unsigned? int ?BKDRHash( char ? * str)

{

????????unsigned? int ?seed? = ? 131 ;? // ?31?131?1313?13131?131313?etc..

????????unsigned? int ?hash? = ? 0 ;

???????? while ?( * str)

???????? {

????????????????hash? = ?hash? * ?seed? + ?( * str ++ );

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?SDBM?Hash?Function

unsigned? int ?SDBMHash( char ? * str)

{

????????unsigned? int ?hash? = ? 0 ;

???????? while ?( * str)

???????? {

????????????????hash? = ?( * str ++ )? + ?(hash? << ? 6 )? + ?(hash? << ? 16 )? - ?hash;

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?DJB?Hash?Function

unsigned? int ?DJBHash( char ? * str)

{

????????unsigned? int ?hash? = ? 5381 ;

???????? while ?( * str)

???????? {

????????????????hash? += ?(hash? << ? 5 )? + ?( * str ++ );

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

// ?AP?Hash?Function

unsigned? int ?APHash( char ? * str)

{

????????unsigned? int ?hash? = ? 0 ;

???????? int ?i;

???????? for ?(i = 0 ;? * str;?i ++ )

???????? {

???????????????? if ?((i? & ? 1 )? == ? 0 )

???????????????? {

????????????????????????hash? ^= ?((hash? << ? 7 )? ^ ?( * str ++ )? ^ ?(hash? >> ? 3 ));

????????????????}

???????????????? else

???????????????? {

????????????????????????hash? ^= ?( ~ ((hash? << ? 11 )? ^ ?( * str ++ )? ^ ?(hash? >> ? 5 )));

????????????????}

????????}

???????? return ?(hash? & ? 0x7FFFFFFF );

}

比較經(jīng)典的字符串hash就這些了吧,"ELF Hash Function" <-這個比較常用..?

posted on 2008-04-07 19:57 allic 閱讀(1756) 評論(0) 編輯收藏所屬分類: 算法及數(shù)據(jù)結(jié)構(gòu)

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 基于C語言的內(nèi)存池設計與實現(xiàn)[轉(zhuǎn)] 若干經(jīng)典的字符串哈希函數(shù) SQLite數(shù)據(jù)庫文件格式分析(B樹的基本組織) 行編輯器的數(shù)據(jù)結(jié)構(gòu)運用－－－堆棧 KMP字符串匹配算法

一江春水向東流

常用鏈接

留言簿(12)

隨筆分類(23)

隨筆檔案(42)

文章分類(162)

文章檔案(139)

新聞檔案(10)

相冊

收藏夾(3)

文章收集

搜索

最新評論

閱讀排行榜

評論排行榜