原文
' I5 x R K) L. k9 r6 O# bhttp://blog.csai.cn/user3/50125/archives/2009/35638.html
$ f9 u' q8 o0 m* F- P% \- w% y
0 v, m& N' q6 L! D) @/ N0 C[pre]文章转摘自http://www.cmykrgb123.cn/blog/string-hash-compare/ 7 s; G" Q) Y: d
1 ^. e2 k _2 x! P. @0 j8 `$ }常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用
- t2 C# E; V8 `2 P5 H0 A! w位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数, - A& m8 i% m$ d j+ c
这些函数几乎不可能找到碰撞。 7 y8 A/ C3 Y% ~& E! Y3 |
常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,
: A; l3 X) j/ A) P, ?. L( I% U% iPJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。 : N1 I# d0 g% L& v8 O
Hash函数 | 数据1 | 数据2 | 数据3 | 数据4 | 数据1得分 | 数据2得分 | 数据3得分 | 数据4得分 | 平均分 | BKDRHash | 2 | 0 | 4774 | 481 | 96.55 | 100 | 90.95 | 82.05 | 92.64 | APHash | 2 | 3 | 4754 | 493 | 96.55 | 88.46 | 100 | 51.28 | 86.28 | DJBHash | 2 | 2 | 4975 | 474 | 96.55 | 92.31 | 0 | 100 | 83.43 | JSHash | 1 | 4 | 4761 | 506 | 100 | 84.62 | 96.83 | 17.95 | 81.94 | RSHash | 1 | 0 | 4861 | 505 | 100 | 100 | 51.58 | 20.51 | 75.96 | SDBMHash | 3 | 2 | 4849 | 504 | 93.1 | 92.31 | 57.01 | 23.08 | 72.41 | PJWHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 | ELFHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 | : D1 M8 _4 @# I2 {, x3 [8 o5 J: B
其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句
( ~9 G2 F/ ]& n+ c子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。
7 L- h9 L9 P* V, ]- z. p数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。 5 r4 q8 X" I5 M
经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是
/ w) K3 \$ s& I- O编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与 0 f1 }. f* t% T: w& P3 y
SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。 " m' O. Y) h- X( ]4 p
在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。
" u3 y0 W3 ^+ G$ j# M/ w' tCmYkRgB123原创,欢迎建议、交流、批评和指正。 2 T; @8 i% w6 v9 i. g, [6 r% e* Z* t
, s" s R `4 Y8 z8 {. M' w
附:各种哈希函数的C语言程序代码 3 `- W+ d" c$ Z6 \
0 @0 j* r) t6 Funsigned int SDBMHash(char *str)
9 F" {6 D0 g6 r{
3 l+ x M7 v y unsigned int hash = 0; 7 L/ k: E0 }2 N+ [: @& p1 ?8 p1 R6 Z
! ]4 Y/ n/ L( U8 j while (*str) ; ?' E$ H2 I% P& y B$ }
{
2 F; E9 I/ {- U" Q! ~0 S // equivalent to: hash = 65599*hash + (*str++);
5 E+ g; b+ V2 E& d7 W$ c3 @ hash = (*str++) + (hash << 6) + (hash << 16) - hash;
, f) d. z6 u$ P/ a3 P- F }
, K; u( [+ Z( [! K% B- V$ j0 W4 ? # r2 V2 B- p6 G3 @
return (hash & 0x7FFFFFFF);
3 u, i8 @+ U" ^. z} * z/ m6 d& G" |5 d' s# U6 k6 y
4 o [* Q/ t- e3 A5 P9 J" `// RS Hash
4 k+ r6 v1 y& wunsigned int RSHash(char *str)
O/ C7 s& U+ z4 N/ S' X: g{ . H# M+ n( J- y8 i/ @" y+ _( w
unsigned int b = 378551; 5 P" F2 F/ u7 f4 r1 s) C2 C
unsigned int a = 63689;
& G. Z1 S, f8 D0 F unsigned int hash = 0; 9 E0 m7 i8 X1 n1 s* m
) C; d4 ~ T) [: [, t ]3 p while (*str) % A3 ~ R/ x* ~) l
{
9 g# c( y2 U9 `; G( m hash = hash * a + (*str++);
5 @ K0 @' E4 F$ \6 o* O- x" g a *= b;
" }$ G1 a2 o: V$ ^ }
+ s! Z: U' G3 e/ x j
8 M# d! `4 H# ^# R p' K return (hash & 0x7FFFFFFF); $ Y+ U9 _9 [% H- g
} 4 U5 L3 L! d# G) p
8 t* R, V9 j( k* \/ M& c6 R// JS Hash
0 U* P) L! h5 R( R$ a' A% r$ ^unsigned int JSHash(char *str)
1 e; [8 y! _' x3 H7 ^{ 9 F+ e/ Z/ i* d3 g/ z1 p* i
unsigned int hash = 1315423911; + O9 Q; ~( w9 R* h9 \- C# y
[" U/ k% S- O" m. P! E
while (*str) $ a+ S9 h3 S* V! m1 i
{
# {" r4 _0 D5 A& @ hash ^= ((hash << 5) + (*str++) + (hash >> 2));
j3 z; c% @" D3 v6 J$ B. ~ } , c! ~8 W5 a( w4 Q! T
+ v( L, _( ]9 @! {% Z" f
return (hash & 0x7FFFFFFF); ) ]+ ^1 ?3 |0 f# s6 [5 B0 Q! M
} / Y3 \5 z2 `4 U" n0 m3 r3 z1 F9 t
7 `. Y' t* v$ l& t// P. J. Weinberger Hash 9 }" z( T* Q; I/ g( X
unsigned int PJWHash(char *str), ?3 m: m5 i8 R/ M" z* ^
{
& d; {/ L! L- L8 o unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);8 u, |1 V; @1 E. K- d4 [
unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4);
; j3 [5 _5 L0 o8 X( C G4 I( M: S unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);$ y& C1 T d" l( B5 E
unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt [pre] - 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 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 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);} // DJB Hash unsigned int DJBHash(char *str){ unsigned int hash = 5381; while (*str) { hash += (hash << 5) + (*str++); } return (hash & 0x7FFFFFFF);} // AP Hash 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);}[/pre] |