哈希表（第二部分）

哈希表一个更重要但有些神秘的方面是编写哈希函数。哈希函数需要将你的数据（可能是固定大小的，也可能是可变大小的）转换成一个具有“良好分布”的固定大小的数字。如果你能做到这一点，就不会产生大量冲突。这意味着每次哈希查找只需要查看表中几个桶，因此会很快。

但是什么样的分布是好的呢？你又如何创建这样的函数呢？幸运的是，一位名叫 Bob Jenkins 的聪明人已经为你解决了这个问题。他说一个好的哈希函数是没有“漏斗”的——即输入中的 m 位在混合过程中只影响状态中较少的 n < m 位的情况。或者，显然，反过来也是一样，无论那意味着什么。

这能给你带来什么？嗯，你会得到一个具有雪崩性质的函数——输入字符串中的任何一位改变，平均会使输出中大约一半的位翻转。这很好，因为它意味着相似的输入会有非常不同的哈希码——这很有用，因为实际世界中的输入集合通常具有相当低的熵。换句话说，你的输入字符串会有很多结构上的相似性。这也很棒，因为它意味着哈希码的每一位都有用，所以你只需通过屏蔽低位几位就可以创建一个更小的好哈希。在下一部分中，我们将看到这为什么如此重要。

好的，现在我们知道哈希函数应该具备什么了。我们希望它“无漏斗”，从而实现“雪崩效应”。这具体意味着什么呢？嗯，这意味着你不能使用那种流行的黑客手法，即只取字符串的长度以及开头和末尾的几个字符来做哈希。这样做会使你的哈希函数极易受到病态输入集合的影响，从而导致可怕的冲突率，因为任何在两端相同但中间不同的输入集合都将哈希到相同的值。虽然对整个长字符串进行哈希运算可能很耗时，但通常将哈希码保存在字符串中并只计算一次完整的良好哈希是一个值得的权衡。

好的，既然如此，你如何才能真正创建一个具备这些特性且计算速度合理的函数呢？基本上，你需要通过位操作和魔法常量进行摸索，直到找到一个通过适当测试的函数。但你通常不必自己动手，因为其他人已经为你完成了这项工作。Bob Jenkins 本人就提供了一些优秀的哈希函数的代码，并推崇 FNV。

但其他人已经应用了他的哈希原理，并开发出计算速度更快且仍能产生良好结果的函数。

我发现用于字符串等任意长度数据最快的强哈希算法是 Paul Hsieh 恰如其名地命名的 SuperFastHash。这个哈希函数的基本思想是每次处理 16 位字符串，并与 32 位内部状态混合；大多数其他哈希函数每次只处理 8 位。该函数在每个步骤中只进行少量混合，然后在最后应用一些最终的扰乱操作。以 16 位块为单位处理实际上非常适合 UTF-16 Unicode 字符串，其中包含了 JavaScript 和 DOM 中使用的所有字符串。它们由 16 位块组成，因此该函数实际上可以进一步简化，无需担心未对齐访问或末尾的奇数字节。你可以在 WebCore/khtml/xml/dom_stringimpl.cpp 中找到我的版本示例。

对于固定大小的 32 位或 64 位数量，例如整数或指针，你实际上可以做得更好。Thomas Wang 介绍了32 位混合和 64 位混合函数，这些函数可以用很少的机器周期计算，但仍能提供良好的分布。你可以在 WebCore/khtml/misc/hashfunctions.h 中找到这些作为 pointerHash 函数。使用了一点模板魔法来根据你的平台指针大小选择合适的函数。

那么，最终结论是什么？了解一个好的哈希函数应具备哪些特性固然有用，但在大多数情况下，你最好还是使用现有经过测试且理论上可靠的哈希函数，而不是尝试自己创建。

在下一部分中，我们将探讨在实现哈希表时可以做出的一些选择，以及哪些选择与好的哈希函数最匹配。