原文
0 g; Z6 { c0 S T; H N% Thttp://blog.csai.cn/user3/50125/archives/2009/35638.html 2 U/ W7 J) w# N' D
3 r3 R$ r0 {# M7 g$ S( g& O8 c1 ^% l[pre]文章转摘自http://www.cmykrgb123.cn/blog/string-hash-compare/
* z: G4 o( \+ d) R, w ; G) P) }2 N% |+ \
常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用
2 t9 Z" ^$ c0 q* X位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数, : P' J8 p/ Q. \$ g p
这些函数几乎不可能找到碰撞。 7 N* y' v) A5 ]
常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,
4 M0 ~* i* g6 x0 I$ w o( DPJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。
% n* F9 R8 k/ V) IHash函数 | 数据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 | - H4 ^$ T1 ^' k3 a3 v6 S2 a1 M* @
其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句
' l1 U- r8 V+ R- D2 W0 y5 d( v6 a子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。 7 w. Z" ~6 F# j4 o
数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。
, L$ x+ Q% Y3 V+ A/ ^' _/ x经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是
0 {# b& ]4 H- P; M. \! Z编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与 8 W! R& g, ?* J$ m6 x1 g' Q' b- Y" L+ _
SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。
9 T+ q2 w5 g# v/ c/ Y8 a" W. ~在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。 + x' {$ t9 d$ ^+ w
CmYkRgB123原创,欢迎建议、交流、批评和指正。
/ A1 q2 L0 k. m7 v9 ~
) P1 d6 D9 g$ ~% K6 @, M附:各种哈希函数的C语言程序代码 ' u: ~. V* d: K# u% j; N8 V
/ k3 y4 ]' V( [unsigned int SDBMHash(char *str)
% ?2 f. z# v6 f' e* m1 b! A{ & P% g3 ?# d% ^4 ~4 {
unsigned int hash = 0;
9 h7 ]9 l' a) D / Z( N$ v' O, R6 o1 _
while (*str) " D4 `3 k7 W8 s+ {
{
" x% f( g" ]% y // equivalent to: hash = 65599*hash + (*str++); ! A% p' f+ ]. l, Q
hash = (*str++) + (hash << 6) + (hash << 16) - hash; / V8 _5 ?% q4 z8 U
}
* {( A% X: `* w" _1 U3 @ ; g5 R, S. c V- j# }
return (hash & 0x7FFFFFFF); % K3 ^5 j0 l; I0 Q
}
/ q6 r- I- B4 F/ {) k# N- E
, z, D, S" U7 l: n// RS Hash
6 A- d' T& I& E. W F: X: {+ junsigned int RSHash(char *str)
}* Q$ F9 S& Q( @& [{
2 \* O; e9 y2 f% ~ b% u3 }0 \ unsigned int b = 378551;
9 G% ?5 E/ R0 @: H unsigned int a = 63689; ; f( ^. R8 i7 \2 Y
unsigned int hash = 0; 4 h- E; R' F; j2 n) q/ ^* C
0 q9 N4 O5 f9 S: [- m, ] while (*str) 9 ^5 S7 d) S" n; e, m
{ % @5 S+ Y' ~& l! y! f; p
hash = hash * a + (*str++);
# S1 d5 _% y3 d3 [ a *= b; Y# h F! b/ H p
} 7 \8 f0 Z4 X5 P5 h! V% U
' }2 u+ h8 V$ \
return (hash & 0x7FFFFFFF);
& f* z& Q# n/ K5 k}
9 S! X h" G' F! h% v7 _5 H 2 a" J! Q9 b. P# ~) |- c: D7 L9 ]! K1 y
// JS Hash 9 Z& L, }& y ~7 u! {+ F' K
unsigned int JSHash(char *str)
6 B2 S" ~) h6 K% D$ H{ : G4 N6 L" Y: P Z+ ~! y
unsigned int hash = 1315423911;
9 ~5 I. [4 A9 Z; M' p
7 C$ a; ^" a0 }4 W while (*str) 1 m- P8 t( V8 w( b; x. r9 p
{
# M ?; {7 C' q hash ^= ((hash << 5) + (*str++) + (hash >> 2));
/ W5 {3 e: M' ?( n+ e$ \2 K# a: G }
, ~2 ~+ c/ |3 \3 e Q 9 e4 S- O) i1 Z$ M- S
return (hash & 0x7FFFFFFF);
/ A; J1 L: \ R& s}
8 K. \& G4 V6 m6 |, i& ?9 U
m& l/ K) v9 x7 p+ U" H1 s9 e, M// P. J. Weinberger Hash
& t0 B3 ` ]" d. \. ]& K3 Ounsigned int PJWHash(char *str)
" D m Q' A/ D+ ^9 @$ @! S: I{0 z( }& @& E7 U9 d8 I' o
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
' p5 | @7 p: _2 B' y unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4);
3 G: h4 J; z7 Y- r( F2 z8 O9 ^4 O unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);
! P/ Z& H! |9 g. i# @% f 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] |