哈希函数：经验比较

• 下载源代码 - 79.16 KB

引言

哈希表是存储键值对的流行数据结构。哈希函数用于将键值（通常是string）映射到数组索引。这些函数与密码学哈希函数不同，因为它们应该快得多，并且不需要抵抗原像攻击。哈希表中使用的函数主要有两类：

• 乘法哈希函数，简单快速，但冲突数量多；
• 更复杂的函数，质量更好，但计算时间更长。

哈希函数基准测试通常包括理论指标，如冲突数量或分布均匀性（例如，请参阅“龙书”中的哈希函数比较）。显然，更复杂的函数分布会更好，因此它们在这些基准测试中表现更优。

问题在于**使用复杂的函数是否能让程序运行得更快**。复杂的函数每个键需要更多的操作，因此可能更慢。冲突的代价是否高到足以证明额外的操作是合理的？

乘法哈希函数

任何乘法哈希函数都是以下算法的特例

unsigned HashMultiplicative(const char *key, size_t len) {
   unsigned hash = INITIAL_VALUE;
   for(unsigned i = 0; i < len; ++i)
      hash = M * hash + key[i];
   return hash % TABLE_SIZE;
}

(有时使用XOR运算代替加法，但这差别不大。) 哈希函数仅在INITIAL_VALUE和乘数（M）的值上有所不同。例如，流行的**Bernstein函数**使用INITIAL_VALUE为5381，M为33；**Kernighan和Ritchie函数**使用INITIAL_VALUE为0，M为31。

乘法函数通过将字母按乘数的幂进行加权来累加。例如，单词TONE的哈希值为

INITIAL_VALUE * M^4  +  'T' * M^3  +  'O' * M^2  +  'N' * M  +  'E'

让我们输入几个相似的string，并观察函数的输出

     Bernstein Kernighan
        (M=33)     (M=31)
 too   b88af17     1c154
 top   b88af18     1c155
 tor   b88af1a     1c157
 tpp   b88af39     1c174
a000  7c9312d6    2cd22f
a001  7c9312d7    2cd230
a002  7c9312d8    2cd231
a003  7c9312d9    2cd232
a004  7c9312da    2cd233
a005  7c9312db    2cd234
a006  7c9312dc    2cd235
a007  7c9312dd    2cd236
a008  7c9312de    2cd237
a009  7c9312df    2cd238
a010  7c9312f7    2cd24e
   a     2b606        61
  aa    597727       c20
 aaa   b885c68     17841

Too和top仅在最后一个字母上不同。字母P在O之后，因此哈希函数的值相差1（1c154和1c155，b88af17和b88af18）。a000..a009也是如此。

现在，我们比较top和tpp。它们的哈希值为

  INITIAL_VALUE * M^3 + 'T' * M^2 + 'O' * M + 'P'
  INITIAL_VALUE * M^3 + 'T' * M^2 + 'P' * M + 'P'

哈希值将相差M * ('P' - 'O') = M。类似地，当第一个字母相差x时，它们的哈希值将相差x * M^2。

当可能存在的字母少于33个时，Bernstein函数会将它们打包成一个数字（类似于Radix40打包方案）。例如，大小为33³的哈希表将为所有小写英文字母的三个字母单词提供完美的哈希（无任何冲突）。实际上，单词更长，哈希表更小，因此会出现一些冲突（即不同的string具有相同的哈希值）。

如果string太长而无法放入32位数字，则第一个字母仍然会影响哈希函数的值，因为乘法是模2³²进行的（在32位寄存器中），并且乘数选择为与2³²没有公因数（换句话说，它必须是奇数），因此位不会仅仅被移出。

选择乘数没有确切的规则，只有一些启发式方法

• 乘数应足够大，以容纳大多数可能的字母（例如，3或5太小）。
• 乘数应易于通过移位和加法进行计算（例如，33 * hash可以计算为（hash << 5）+ hash）。
• 乘数应为奇数，原因如上所述。
• 素数是好的乘数。

复杂哈希函数

这些函数能很好地混合源单词的位。输入位的一个变化会改变输出位的一半（参见雪崩效应），因此结果看起来完全是随机的。

     Paul Hsieh One At Time
 too   3ad11d33  3a9fad1e  
 top   78b5a877  4c5dd09a  
 tor   c09e2021  f2aa9d35  
 tpp   3058996d  d5e9e480  
a000   7552599f  ed3859d8  
a001   3cc1d896  fef7fd57  
a002   c6ff5c9b  08a610b3  
a003   dcab7b0c  1a88b478  
a004   780c7202  3621ebaa  
a005   7eb63e3a  47db8f1d  
a006   6b0a7a17  b901717b  
a007   cb5cb1ab  caec1550  
a008   5c2a15c0  e58d4a92  
a009   33339829  f75aee2d  
a010   eb1f336e  bd097a6b  
   a   115ea782  ca2e9442  
  aa   008ad357  7081738e  
 aaa   7dfdc310  ae4f22ec

为了实现这种行为，哈希函数执行大量的移位、XOR和加法。但是我们需要复杂的函数吗？哪个更快：容忍冲突并通过链式法解决它们，还是通过更复杂的函数来避免冲突？

测试条件

基准测试使用单独链式法算法进行冲突解决。内存分配和其他“重”函数已从基准测试代码中排除。使用RDTSC指令进行基准测试。测试在Pentium-M处理器上进行。

基准测试在表中插入一些键，然后以与插入顺序相同的顺序查找它们。测试数据包括：

• 维基词典的常用词列表（500项）
• Colorer语法高亮方案的Win32函数列表（1992项）
• 来自a000到a499的500个名称（模仿自动生成的源代码中的名称）
• 带有长前缀和后缀的常用词列表
• WordPress 2.3.2源文件中wp-includes文件夹的所有变量名（1842个名称）
• 莎士比亚《十四行诗》中的所有单词列表（模仿一个单词计数程序；3228个单词）

结果

	单词		Win32		数字		前缀		后缀		变量		莎士比亚
Bernstein	145	[135]	889	[478]	92	[500]	325	[116]	320	[121]	659	[391]	895	[646]
K&R	145	[117]	883	[511]	88	[500]	321	[113]	316	[117]	659	[411]	897	[641]
x17 展开	136	[99]	842	[491]	73	[24]	303	[107]	298	[113]	636	[434]	856	[638]
x65599	138	[129]	857	[432]	82	[258]	319	[119]	314	[146]	642	[440]	861	[628]
FNV-1a	157	[154]	975	[528]	88	[124]	366	[106]	362	[118]	711	[443]	955	[640]
Sedgewick	153	[126]	963	[477]	84	[48]	366	[113]	361	[119]	704	[404]	948	[627]
Weinberger	169	[125]	1214	[495]	73	[100]	474	[138]	472	[152]	834	[421]	1052	[892]
Paul Larson	139	[117]	879	[470]	64	[16]	323	[119]	317	[117]	649	[421]	858	[656]
两个字符	126	[305]	738	[3458]	500	[12250]	297	[1323]	223	[877]	1109	[12431]	1693	[14425]
Paul Hsieh	157	[130]	851	[476]	107	[138]	282	[120]	275	[113]	678	[399]	991	[676]
一次一个	160	[118]	1018	[481]	99	[131]	382	[120]	376	[125]	745	[422]	990	[601]
lookup3	150	[114]	837	[474]	95	[108]	290	[118]	282	[106]	656	[412]	958	[619]
Arash Partow	154	[120]	1009	[510]	149	[1530]	376	[123]	367	[97]	731	[402]	951	[643]
CRC-32	154	[114]	986	[519]	84	[64]	371	[125]	362	[108]	720	[385]	958	[632]
Ramakrishna	151	[130]	971	[476]	80	[100]	370	[153]	360	[124]	705	[414]	925	[603]
Fletcher	129	[158]	691	[467]	190	[2880]	233	[155]	221	[124]	581	[732]	874	[1453]
Murmur2	140	[122]	795	[469]	84	[119]	262	[133]	257	[131]	632	[445]	875	[654]

每个单元格包括执行时间，然后是冲突数量（方括号内）。执行时间以千个时钟周期为单位（数字越小越好）。每个测试中最好的三个结果用粗体突出显示。

Kernighan和Ritchie的函数出自他们著名的书籍《C程序设计语言》第三版；Weinberger的哈希函数和乘数为65599的哈希函数来自“龙书”。后者函数在gawk、sdbm和其他Linux程序中使用。x17是我自己的函数（乘数=17；每个字母代码减去32）。

从表中可以看到，冲突数量最少的函数不总是最快的。例如，比较“数字”测试中的CRC-32和Larson的哈希。

结论

Paul Hsieh和Bob Jenkins的复杂函数经过优化，**适用于长键**，例如后缀和前缀测试中的键。请注意，它们在这些测试中并未提供最佳的冲突数量，但具有最佳的执行时间，这意味着函数比其他函数更快，这是因为循环展开。同时，它们对短键（“常用词”和“莎士比亚”测试）效果不佳。

对于单词计数程序、编译器或其他通常处理**短键**的应用程序，使用简单的乘法函数（如x17或Larson的哈希）通常是有利的。然而，这些函数在长键上表现不佳。

**Murmur2**是唯一一种为所有类型的键提供良好性能的复杂哈希函数。它可以作为通用哈希函数推荐。

变奏

XOR高低部分

对于小于2¹⁶的表大小，我们可以通过XOR高低字来提高哈希函数的质量，从而将更多的字母考虑在内。

   return hash ^ (hash >> 16);

减去常数

我的x17哈希函数从每个字母中减去一个空格，以截断0x00..0x1F范围内的控制字符。如果哈希键很长，并且只包含拉丁字母和数字，字母被移出的可能性会减小，总体冲突数量会降低。如果您知道键只包含英文字母，甚至可以减去'A'。

为编译器使用更大的乘数

Paul Hsieh指出，对于编译器中的哈希表，较大的乘数可能提供更好的结果，因为典型的源代码包含许多**单字母变量名**（i、j、s等），如果乘数小于字母表中的字母数量，它们就会发生冲突。

测试证实了这一假设：Kernighan & Ritchie的函数（M=33）比x17（M=17）的冲突数量少，但后者仍然更快（参见上表中的变量列）。

将哈希表大小设置为素数

测试表明，如果使用素数，冲突数量通常会较低，但素数模运算比2的幂的模运算花费的时间要长得多，因此这种方法不切实际。即使将除法替换为乘以倒数也无济于事。

	单词		Win32		数字		前缀		后缀		变量		莎士比亚
Bernstein % 2^K	145	[261]	880	[889]	426	[8030]	326	[214]	316	[226]	649	[697]	874	[1131]
Bernstein % 素数	186	[221]	1049	[995]	445	[5621]	364	[194]	357	[217]	805	[800]	1123	[1051]
Bernstein 优化模	160	[221]	960	[995]	416	[5621]	341	[194]	334	[217]	722	[800]	969	[1051]
x17 % 2^K	137	[193]	847	[1002]	81	[340]	314	[244]	300	[228]	641	[863]	832	[1012]
x17 % 素数	173	[256]	1010	[1026]	104	[324]	356	[246]	339	[216]	760	[760]	1046	[1064]
x17 优化模	155	[256]	915	[1026]	96	[324]	330	[246]	315	[216]	691	[760]	930	[1064]

实现开放寻址与单独链式法

使用开放寻址时，大多数哈希函数在“数字”测试中会表现出尴尬的聚集行为。

	Bernst.	K&R	x17	x17 展开	x65599	FNV	Univ	Weinb.	Hsieh	一次一个	Lookup3	Partow	CRC
OA	426	866	81	84	207	88	91	273	110	103	92	1042	79
	[8030]	[20810]	[340]	[340]	[3158]	[207]	[480]	[4360]	[342]	[267]	[205]	[20860]	[96]
h32	179	320	69	74	114	86	80	125	105	99	92	347	82
	[8030]	[20810]	[340]	[340]	[3158]	[207]	[480]	[4360]	[342]	[267]	[205]	[20860]	[96]
C	92	88	68	73	82	88	84	73	107	99	95	149	84
	[500]	[500]	[24]	[24]	[258]	[124]	[48]	[100]	[138]	[131]	[108]	[1530]	[64]

您可以通过使用链式法来解决冲突，从而避免最坏情况。然而，链式法需要更多的内存来存储下一个元素指针，因此性能提升并非免费。通常需要编写自定义内存分配器，因为为大量小型结构调用malloc()不是最优的。

一些实现（例如Python解释器中的哈希表）会存储完整的32位哈希值与项一起，以加快string比较的速度，但这不如链式法有效。

致谢

非常感谢Nils、Ace和Won提供的想法和建议，这帮助我改进了本文。