优化哈希策略

概述

用于散列键的策略可以直接影响散列集合（例如 HashMap 或 HashSet）的性能。

内置的散列函数被设计为通用的，并且在广泛的用例中都能很好地工作。我们能否做得更好，特别是如果我们对用例有很好的了解？

测试哈希策略

在上一篇文章中，我研究了多种测试哈希策略的方法，尤其是研究了一种针对“正交位”进行了优化的哈希策略，该策略着眼于确保每个哈希结果尽可能不同，仅基于一个有点变化。

但是，如果您有一组已知的要散列的元素/键，您可以针对该特定用例进行优化，而不是试图找到一个通用的解决方案。

最小化碰撞

在散列集合中要避免的主要事情之一是冲突。这是两个或多个键映射到同一个桶的时候。这些冲突意味着您必须做更多的工作来检查密钥是否是您期望的密钥，因为现在同一个存储桶中有多个密钥。理想情况下，每个桶中最多有 1 个密钥。

我只需要唯一的哈希码，不是吗？

一个常见的误解是，要避免冲突，您只需要拥有一个唯一的哈希码即可。虽然非常希望拥有唯一的哈希码，但这还不够。

假设您有一组密钥，并且所有密钥都有唯一的 32 位散列码。如果你有一个包含 40 亿个桶的数组，每个键都有自己的桶，并且不会发生冲突。通常不希望所有哈希集合都具有如此大的数组。事实上，HashMap 和 HashSet 受到数组的两个大小的最大幂的限制，即 2^30 或刚刚超过 10 亿。

当你有一个更实际大小的散列集合时会发生什么？桶的数量需要更小，哈希码需要对桶的数量取模。如果桶的数量是 2 的幂，您可以使用最低位的掩码。

让我们看看这个例子： ftse350.csv 。如果我们将第一列作为键或元素，我们将得到 352 个字符串。这些字符串具有唯一的 String.hashCode() s，但假设我们采用这些哈希码的低位。我们看到碰撞了吗？

面具	String.hashCode() 被屏蔽	哈希表.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位	103次碰撞	92次碰撞

加载因子为 0.7（默认值）的 HashMap 的大小为 512，它使用低 9 位的掩码。正如您所看到的，即使我们从唯一的哈希码开始，大约 30% 的键也会发生冲突。

HashTesterMain 的代码在这里。

为了减少糟糕的散列策略的影响，HashMap 使用了一个搅拌函数。在 Java 8 中，它相当简单。

来自 HashMap.hash 的来源。您可以阅读 Javadoc 以获取更多详细信息：


 static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这将哈希码的高位与低位混合以提高低位的随机性。对于上述碰撞率较高的情况，有改进。见第三栏。

看看字符串的哈希函数

String.hashCode() 的代码：


 static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

注意：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 的源代码

哈希函数	最佳乘数	最低碰撞	最差乘数	最高碰撞
散列()	130795	81次碰撞	126975	250次碰撞
xorShift16(散列())	2104137237	68次碰撞	-1207975937	237 碰撞
addShift16（散列（））	805603055	68次碰撞	-1040130049	243次碰撞
xorShift16n9(散列())	841248317	69次碰撞	467648511	177次碰撞

要查看的关键代码是：


 static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如您所见，如果您提供了一个好的乘数，或者恰好与您的密钥集配合得很好的乘数，则每个散列加上下一个字符的重复乘法是合理的。如果将 130795 作为乘数而不是 31 进行比较，则测试的密钥集只会发生 81 次冲突而不是 103 次冲突。

如果您也使用搅拌功能，您可以获得大约 68 次碰撞。这接近于将数组大小加倍时的相同碰撞率。即在不使用更多内存的情况下提高碰撞率。

但是当我们向散列集合中添加新键时会发生什么，我们的幻数是否仍然对我们有好处？这是我查看最差碰撞率的地方，以确定哪种结构可能会为更广泛的可能输入产生良好的结果。 hash() 的最坏情况是 250 次冲突。那是 70% 的按键发生碰撞，这非常糟糕。搅拌功能稍微改善了这一点，但仍然不是很好。注意：如果我们添加移位后的值而不是对它进行异或运算，在这种情况下我们会得到更糟糕的结果。

然而，如果我们进行两次移位——不仅混合最高位和最低位，而且混合来自生成的哈希码的四个不同部分的位——我们发现最坏情况下的冲突率要低得多。这向我表明，如果键的选择发生变化，我们不太可能得到不好的结果，因为结构更好，幻数的选择或输入的选择更不重要。

如果我们在哈希函数中使用 `add` 而不是 `xor` 怎么办？

在搅拌函数中使用 xor 可能比使用 add 更好。如果我们改变 h = multiplier * h + s.charAt(i); 到 h = multiplier * h ^ s.charAt(i); ？

哈希函数	最佳乘数	最低碰撞	最差成绩	最高碰撞
散列()	1724087	78次碰撞	247297	285次碰撞
xorShift16(散列())	701377257	68次碰撞	-369082367	271次碰撞
addShift16（散列（））	-1537823509	67次碰撞	-1409310719	290次碰撞
xorShift16n9(散列())	1638982843	68次碰撞	1210040321	206次碰撞

最好情况下的数字稍好一些，但最坏情况下的碰撞率明显更高。这向我表明幻数的选择更重要，但这也意味着键的选择更重要。这似乎是一个冒险的选择，因为您必须考虑到密钥可能会随着时间而改变。

为什么我们选择奇数乘法器？

当您乘以奇数时，结果的低位有相同的机会为 0 或 1。这是因为 0 * 1 = 0 和 1 * 1 = 1。但是，如果您乘以偶数，则低位总是趋向于 0。即它不再是随机的。假设我们重复之前的测试但只使用偶数，这看起来如何？

哈希函数	最佳乘数	最低碰撞	最差成绩	最高碰撞
散列()	82598	81次碰撞	290816	325碰撞
xorShift16(散列())	1294373564	68次碰撞	1912651776	301碰撞
addShift16（散列（））	448521724	69次碰撞	872472576	306碰撞
xorShift16n9(散列())	1159351160	66次碰撞	721551872	212碰撞

如果你幸运并且为你的幻数输入了正确的结果，那么结果和奇数一样好，但是如果你不幸运，结果可能会很糟糕。 325 次碰撞意味着 512 个桶中只有 27 个被使用。

更高级的哈希策略有何不同？

对于我们使用的基于 City、Murmur、XXHash 和 Vanilla Hash（我们自己的）的哈希策略：

哈希策略一次读取 64 位，比逐字节读取更快。
计算的工作值是两个 64 位值。
工作值减少到 64 位长。
结果使用了更多的乘法常数。
搅拌功能更为复杂。

我们在实现中使用长哈希码作为：

我们针对 64 位处理器进行了优化
Java中最长的原始数据类型是64位
如果您有大量散列集合（即数百万），则 32 位散列不太可能是唯一的。

总之

通过探索我们如何生成哈希码，我们找到了将 352 个键的冲突次数从 103 次减少到 68 次的方法，但也有信心，如果键集发生变化，我们已经减少了这可能产生的影响有。

这没有使用更多的内存，甚至没有更多的处理能力。

我们仍然可以选择使用更多内存。

为了比较，你可以看到将数组的大小加倍可以改善最好的情况，但是你仍然有一个问题，即键集和幻数之间的不匹配仍然会产生很高的冲突率。

哈希函数	最佳乘数	最低碰撞	最差成绩	最高碰撞
散列()	2924091	37次碰撞	117759	250次碰撞
xorShift16(散列())	543157075	25次碰撞	- 469729279	237 碰撞
addShift16（散列（））	-1843751569	25次碰撞	- 1501097607	205次碰撞
xorShift16n9(散列())	-2109862879	27次碰撞	-2082455553	172次碰撞

结论

在您拥有稳定密钥集的情况下，您可以通过调整所使用的散列策略来显着提高冲突率。

您还需要一些测试来表明如果密钥集在没有重新优化的情况下发生变化，事情可能会变得多么糟糕。

结合使用这两者，您可以开发新的哈希策略来提高性能，而无需使用更多内存或更多 CPU。

概述