优化一个哈希策略

xdld 9年前

优化一个哈希策略

通过接合两种哈希策略可以创造出一种更高效的算法，且不会有额外的内存与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 规定，我们并没有多大机会去改动它。但我们的确可以定义一个新哈希策略。

哈希策略的组成部分

我会留意哈希策略里的两部分，

  • Magic numbers (魔法数字)。你可以尝试不同的数字以取得最佳效果。

  • 代码的结构。你想要的代码结构应该能提供一个好的结果，无论魔法数字的选取是多么地丧心病狂。

魔法数字固然重要，但你不会想让它变得过于重要；因为总有些时候，你所选的数字并不合适。这就是为什么你同时需要一个即使在魔法数选取很糟糕的情况下最坏情况产出仍然低的代码结构。

让我们用别的乘数来代替 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

最佳情况下的表现稍微变好了些，然而最差情况下的冲突率明显地变差了。由此我看出，魔法数选取的重要性上升了，也就是说，键的选取将会产生更大的影响。考虑到随着时间的推移键的选取可能会发生变化，这种选择显得有些危险。


为何选择奇数作为乘数

当与一个奇数相乘时，结果的地位既可能是0，又可能是1；因为0 * 1 = 0, 1 * 1 = 1. 然而，如果与偶数相乘，最低位将必定是0. 也就是说，这一位不再随机变化了。让我们看看，重复先前的测试，但仅仅采用偶数，结果会是什么样。

哈希函数 最佳乘数 最低冲突数 最差乘数 最高冲突数
hash() 82598 81 collisions 290816 325 collisions
xorShift16(hash()) 1294373564 68 collisions 1912651776 301 collisions
addShift16(hash()) 448521724 69 collisions 872472576 306 collisions
xorShift16n9(hash()) 1159351160 66 collisions 721551872 212 collisions

如果你够幸运，魔法数选对了，所得的结果将会和奇数情况下一样好。然而如果倒霉，结果可能就很糟了。325处冲突即是说，512个桶里被使用的仅仅只有27个。

更为先进的哈西策略有何差异

对于我们使用的基于 City, Murmur, XXHash，以及 Vanilla Hash(我们自己实现的)：

  • 该策略一次读取64为数据，比一字节一字节地读取更快

  • 所得的有效值是两个64位长的值

  • 有效值被缩短至64位

  • 从结果上来看，采用了更多的常量乘数

  • 扰动函数更为复杂

我们在实现中使用长哈希值，因为：

  • 我们为64位处理器做优化

  • Java中最长的数据类型是64位的

  • 如果你的哈希集很大(上百万)，32位哈希值难以保持唯一

总结

通过探索哈希值的产生过程，我们得以将352个键的冲突数量从103处降至68处。同时，我们还有一定信心认为，如果键集发生变化，我们也已经降低了变化所可能造成的影响。

这是在没有使用更多内存，甚至更多运算时间的情况下做到的。

我们仍可以选择去利用更多的内存。

作为对比，可以看到，将桶数组大小翻倍可以提高最佳情况的下的表现，但你还是要面对老问题：魔法数与键集的不契合将会带来高冲突。

哈希函数 最佳情况 最低冲突 最坏情况 最高冲突
hash() 2924091 37 collisions 117759 250 collisions
xorShift16(hash()) 543157075 25 collisions - 469729279 237 collisions
addShift16(hash()) -1843751569 25 collisions - 1501097607 205 collisions
xorShift16n9(hash()) -2109862879 27 collisions -2082455553 172 collisions

结论

在拥有稳定键集的情况下，调整哈希策略可以显著降低冲突概率。

你同时得测试，在没有再优化的情况下，如果键集改变，情况将会变坏到何种程度。

结合这两者，你就能够发展出不需更多内存便能提升表现的哈希策略。