英文原文：
Optimizing a Hashing Strategy
通过接合两种哈希策略可以创造出一种更高效的算法，且不会有额外的内存与CPU开销。
简介
对于像 HashMap 或 HashSet 这些经过哈希排序的集合，key 的哈希策略对于它们的性能有直接影响。
内置的哈希算法是专门设计用于常规的哈希计算，并且在很多场景下都很适用。但在某些场景下（特别是当我们有一些更好的想法时）我们是否有更好的策略？
一种 hash 策略的测试
在前篇文章中我翻了不少测试 hash 策略的方法，并着重看了为“Orthogonal Bits”特别设计的测试同方法，即：只改变原始输入的一个 bit，其 hash 结果是否也会改变。
另外，如果需要进行 hash 运算的元素/键是已知的，你应该为这种特殊情况进行优化而不是试图使用常规的解决方案。
减少碰撞
在一个需要进行 hash 运算的容器中，最重要的是避免碰撞。碰撞就是两个或多个 key 映射到了同一个位置。这也意味着你需要做一些额外工作来检查某个 key 是否是你需要的那个，因为现在有多个 key 放到了同一个位置上。在理想情况下，每个位置最多只能有一个 key。
我需要的哈希码是惟一的
避免碰撞的一个常见误区是只保证哈希码惟一就可以了。虽然惟一的哈希码确实很需要，但只有它也不够。
告诉你有一个键值的集合，并且它们都有唯一的 32 位哈希码。假设你有一个 40 亿量的数组桶（bucket），每一个键值都有它自己的桶，不能冲突。对这么大的数组构成的哈希集合通常是很让人烦的。实际上，HashMap 和 HashSet 容纳的量也是有限的，是 2^30，大致刚刚超过 10 亿。
当你有一个实际大小的散列集合的时候会发生什么？大量的桶需要更小，哈希代码需要按模计算桶的数量。如果桶的数量是 2 的幂，你可以使用最低位掩码。
请看这个例子：ftse350.csv。 如果我们把此表的第一列作为 key 或元素，那就是 352 个字符串。这些字符串都有自己独一无二的 String.hashCode() 返回值。然而，如果仅仅采用此返回值的一部分，会产生冲突吗？
掩码位长
|
将掩码用于String.hashCode()返回值后的结果
|
将掩码用于HashMap.hash(
String.hashCode())返回值后的结果
|
|
32 位 |
无冲突 |
无冲突 |
|
16 位 |
1 处冲突 |
3 处冲突 |
|
15 位 |
2 处冲突 |
4 处冲突 |
|
14 位 |
6 处冲突 |
6 处冲突 |
|
13 位 |
11 处冲突 |
9 处冲突 |
|
12 位 |
17 处冲突 |
15 处冲突 |
|
11 位 |
29 处冲突 |
25 处冲突 |
|
10 位 |
57 处冲突 |
50 处冲突 |
|
9 bits |
103 处冲突 |
92 处冲突 |
我们采用装载因子为 0.7 (默认值)的 HashMap，它的范围为 512。可以看到，在采用低 9 位的掩码之后，会产生约 30% 的冲突，即便原始数据都是独一无二的。
这里是 HashTesterMain 的代码。
为了减少坏的哈希策略所带来的影响，HashMap 采用扰动函数。Java 8 的实现比较简单。我们从 HashMap.hash 的源码中摘录一段，阅读 Java 文档可以了解到更多的细节:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
此方法将原始哈希值的高位和低位混合，以降低低位部分的随机性。上例中的高冲突情境可通过这一手段得到缓解。参照其第三列。
初探 String 类的哈希函数
下面是 String.hashCode() 的代码:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
注意：由于 String 类的实现由 Javadoc 规定，我们并没有多大机会去改动它。但我们的确可以定义一个新哈希策略。
哈希策略的组成部分
我会留意哈希策略里的两部分，
魔法数字固然重要，但你不会想让它变得过于重要；因为总有些时候，你所选的数字并不合适。这就是为什么你同时需要一个即使在魔法数选取很糟糕的情况下最坏情况产出仍然低的代码结构。
让我们用别的乘数来代替 31。
|
乘数 |
冲突次数 |
|
1 |
230 |
|
2 |
167 |
|
3 |
113 |
|
4 |
99 |
|
5 |
105 |
|
6 |
102 |
|
7 |
93 |
|
8 |
90 |
|
9 |
100 |
|
10 |
91 |
|
11 |
91 |
可以发现，魔法数的选取的确有所影响，但值得一试的数字未免太多了。我们需要写一个程序，随机选取足够的情况用以测试。HashSearchMain的源码。
哈希函数
|
最佳乘数 |
最低冲突次数 |
最差乘数 |
最高冲突次数 |
|
hash() |
130795 |
81 collisions |
126975 |
250 collisions |
|
xorShift16(hash()) |
2104137237 |
68 collisions |
-1207975937 |
237 collisions |
|
addShift16(hash()) |
805603055 |
68 collisions |
-1040130049 |
243 collisions |
|
xorShift16n9(hash()) |
841248317 |
69 collisions |
467648511 |
177 collisions |
代码的关键部分：
public static int hash(String s, int multiplier) {
int h = 0;
for (int i = 0; i < s.length(); i++) {
h = multiplier * h + s.charAt(i);
}
return h;
}
private static int xorShift16(int hash) {
return hash ^ (hash >> 16);
}
private static int addShift16(int hash) {
return hash + (hash >> 16);
}
private static int xorShift16n9(int hash) {
hash ^= (hash >>> 16);
hash ^= (hash >>> 9);
return hash;
}可以发现，如果提供了好的乘数，或者刚好对你的键集合奏效的乘数，那重复相乘每个哈希值与下一字符之和就是有意义的。对比一下，对被测试的键集合采用130795作乘数仅仅发生了81次冲突，而采用31做乘数则发生了103次。
如果你同时还用的扰动函数，冲突将会减少至约68次。这样的冲突率已经快要接近将桶数组所产生的效果了：我们并没有占用更多内存，却降低了冲突率。
但是，当我们向哈希集中添加新的键时会发生什么？我们的魔法数字还能持续奏效吗？正是在这个前提下，我们研究最坏冲突率，以决定在面对更大范围的输入可能时，哪种代码结构可能会表现得更好。hash() 的最坏表现是 250 处冲突：70% 的键冲突了，表现的确有点糟。扰动函数使得情况有所改进，但仍不够好。注意：如果我们选择与被移值相加而非去异或，所得的结果将会更糟。
然而，如果选择位移两次 —— 不仅仅是混合高低位两部分，而是从四个部分hash函数所得哈希值的四个不同部分进行混合 —— 我们会发现，最坏情况的冲突率大幅下降。由此我想到，在所选键集会发生改变的情况下，如果我们的结构够好，魔法数的影响够低；我们得到坏结果的可能性就会降低。
如果在哈希函数中我们选择了相加而非异或，会发生什么？
在扰动函数中采用异或而非相加可能会得到更好的结果。那如果我们将
h = multiplier * h + s.charAt(i);
替换成
h = multiplier * h ^ s.charAt(I);
会怎样？
|
哈希函数 |
最佳乘数 |
最低冲突数 |
最差乘数 |
最高冲突数 |
|
hash() |
1724087 |
78 collisions |
247297 |
285 collisions |
|
xorShift16(hash()) |
701377257 |
68 collisions |
-369082367 |
271 collisions |
|
addShift16(hash()) |
-1537823509 |
67 collisions |
-1409310719 |
290 collisions |
|
xorShift16n9(hash()) |
1638982843 |
68 collisions |
1210040321 |
206 collisions |
最佳情况下的表现稍微变好了些，然而最差情况下的冲突率明显地变差了。由此我看出，魔法数选取的重要性上升了，也就是说，键的选取将会产生更大的影响。考虑到随着时间的推移键的选取可能会发生变化，这种选择显得有些危险。
本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。
2KB翻译工作遵照
CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。
2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务
