字符串哈希算法比较（转载）

谁借莪１个温暖的怀抱￠ 2022-08-27 12:59 140阅读 0赞

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px">    
 <tbody> 
  <tr> 
   <td>Hash函数</td> 
   <td>数据1</td> 
   <td>数据2</td> 
   <td>数据3</td> 
   <td>数据4</td> 
   <td>数据1得分</td> 
   <td>数据2得分</td> 
   <td>数据3得分</td> 
   <td>数据4得分</td> 
   <td>平均分</td> 
  </tr> 
  <tr> 
   <td>BKDRHash</td> 
   <td align="right">2</td> 
   <td align="right">0</td> 
   <td align="right">4774</td> 
   <td align="right">481</td> 
   <td align="right">96.55</td> 
   <td align="right">100</td> 
   <td align="right">90.95</td> 
   <td align="right">82.05</td> 
   <td align="right">92.64</td> 
  </tr> 
  <tr> 
   <td>APHash</td> 
   <td align="right">2</td> 
   <td align="right">3</td> 
   <td align="right">4754</td> 
   <td align="right">493</td> 
   <td align="right">96.55</td> 
   <td align="right">88.46</td> 
   <td align="right">100</td> 
   <td align="right">51.28</td> 
   <td align="right">86.28</td> 
  </tr> 
  <tr> 
   <td>DJBHash</td> 
   <td align="right">2</td> 
   <td align="right">2</td> 
   <td align="right">4975</td> 
   <td align="right">474</td> 
   <td align="right">96.55</td> 
   <td align="right">92.31</td> 
   <td align="right">0</td> 
   <td align="right">100</td> 
   <td align="right">83.43</td> 
  </tr> 
  <tr> 
   <td>JSHash</td> 
   <td align="right">1</td> 
   <td align="right">4</td> 
   <td align="right">4761</td> 
   <td align="right">506</td> 
   <td align="right">100</td> 
   <td align="right">84.62</td> 
   <td align="right">96.83</td> 
   <td align="right">17.95</td> 
   <td align="right">81.94</td> 
  </tr> 
  <tr> 
   <td>RSHash</td> 
   <td align="right">1</td> 
   <td align="right">0</td> 
   <td align="right">4861</td> 
   <td align="right">505</td> 
   <td align="right">100</td> 
   <td align="right">100</td> 
   <td align="right">51.58</td> 
   <td align="right">20.51</td> 
   <td align="right">75.96</td> 
  </tr> 
  <tr> 
   <td>SDBMHash</td> 
   <td align="right">3</td> 
   <td align="right">2</td> 
   <td align="right">4849</td> 
   <td align="right">504</td> 
   <td align="right">93.1</td> 
   <td align="right">92.31</td> 
   <td align="right">57.01</td> 
   <td align="right">23.08</td> 
   <td align="right">72.41</td> 
  </tr> 
  <tr> 
   <td>PJWHash</td> 
   <td align="right">30</td> 
   <td align="right">26</td> 
   <td align="right">4878</td> 
   <td align="right">513</td> 
   <td align="right">0</td> 
   <td align="right">0</td> 
   <td align="right">43.89</td> 
   <td align="right">0</td> 
   <td align="right">21.95</td> 
  </tr> 
  <tr> 
   <td>ELFHash</td> 
   <td align="right">30</td> 
   <td align="right">26</td> 
   <td align="right">4878</td> 
   <td align="right">513</td> 
   <td align="right">0</td> 
   <td align="right">0</td> 
   <td align="right">43.89</td> 
   <td align="right">0</td> 
   <td align="right">21.95</td> 
  </tr> 
 </tbody> 
</table>

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。

在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。

BYVoid原创，欢迎建议、交流、批评和指正。

附：各种哈希函数的C语言程序代码

**\[cpp\]**  [view plain][] [copy][view plain]

1.  unsigned **int** SDBMHash(**char** \*str)  
2.  \{  
3.      unsigned **int** hash = 0;  
4.     
5.      **while** (\*str)  
6.      \{  
7.          // equivalent to: hash = 65599\*hash + (\*str++);  
8.          hash = (\*str++) + (hash << 6) + (hash << 16) - hash;  
9.      \}  
10.    
11.     **return** (hash & 0x7FFFFFFF);  
12. \}  
13.    
14. // RS Hash Function  
15. unsigned **int** RSHash(**char** \*str)  
16. \{  
17.     unsigned **int** b = 378551;  
18.     unsigned **int** a = 63689;  
19.     unsigned **int** hash = 0;  
20.    
21.     **while** (\*str)  
22.     \{  
23.         hash = hash \* a + (\*str++);  
24.         a \*= b;  
25.     \}  
26.    
27.     **return** (hash & 0x7FFFFFFF);  
28. \}  
29.    
30. // JS Hash Function  
31. unsigned **int** JSHash(**char** \*str)  
32. \{  
33.     unsigned **int** hash = 1315423911;  
34.    
35.     **while** (\*str)  
36.     \{  
37.         hash ^= ((hash << 5) + (\*str++) + (hash >> 2));  
38.     \}  
39.    
40.     **return** (hash & 0x7FFFFFFF);  
41. \}  
42.    
43. // P. J. Weinberger Hash Function  
44. unsigned **int** PJWHash(**char** \*str)  
45. \{  
46.     unsigned **int** BitsInUnignedInt = (unsigned **int**)(**sizeof**(unsigned **int**) \* 8);  
47.     unsigned **int** ThreeQuarters  = (unsigned **int**)((BitsInUnignedInt  \* 3) / 4);  
48.     unsigned **int** OneEighth      = (unsigned **int**)(BitsInUnignedInt / 8);  
49.     unsigned **int** HighBits        = (unsigned **int**)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);  
50.     unsigned **int** hash            = 0;  
51.     unsigned **int** test            = 0;  
52.    
53.     **while** (\*str)  
54.     \{  
55.         hash = (hash << OneEighth) + (\*str++);  
56.         **if** ((test = hash & HighBits) != 0)  
57.         \{  
58.             hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));  
59.         \}  
60.     \}  
61.    
62.     **return** (hash & 0x7FFFFFFF);  
63. \}  
64.    
65. // ELF Hash Function  
66. unsigned **int** ELFHash(**char** \*str)  
67. \{  
68.     unsigned **int** hash = 0;  
69.     unsigned **int** x  = 0;  
70.    
71.     **while** (\*str)  
72.     \{  
73.         hash = (hash << 4) + (\*str++);  
74.         **if** ((x = hash & 0xF0000000L) != 0)  
75.         \{  
76.             hash ^= (x >> 24);  
77.             hash &= ~x;  
78.         \}  
79.     \}  
80.    
81.     **return** (hash & 0x7FFFFFFF);  
82. \}  
83.    
84. // BKDR Hash Function  
85. unsigned **int** BKDRHash(**char** \*str)  
86. \{  
87.     unsigned **int** seed = 131; // 31 131 1313 13131 131313 etc..  
88.     unsigned **int** hash = 0;  
89.    
90.     **while** (\*str)  
91.     \{  
92.         hash = hash \* seed + (\*str++);  
93.     \}  
94.    
95.     **return** (hash & 0x7FFFFFFF);  
96. \}  
97.    
98. // DJB Hash Function  
99. unsigned **int** DJBHash(**char** \*str)  
100. \{  
101.     unsigned **int** hash = 5381;  
102.    
103.     **while** (\*str)  
104.     \{  
105.         hash += (hash << 5) + (\*str++);  
106.     \}  
107.    
108.     **return** (hash & 0x7FFFFFFF);  
109. \}  
110.    
111. // AP Hash Function  
112. unsigned **int** APHash(**char** \*str)  
113. \{  
114.     unsigned **int** hash = 0;  
115.     **int** i;  
116.    
117.     **for** (i=0; \*str; i++)  
118.     \{  
119.         **if** ((i & 1) == 0)  
120.         \{  
121.             hash ^= ((hash << 7) ^ (\*str++) ^ (hash >> 3));  
122.         \}  
123.         **else**  
124.         \{  
125.             hash ^= (~((hash << 11) ^ (\*str++) ^ (hash >> 5)));  
126.         \}  
127.     \}  
128.    
129.     **return** (hash & 0x7FFFFFFF);  
130. \}

[view plain]: http://blog.csdn.net/jpcfei/article/details/6643360#