为什么Knuth，CLRS哈希函数不足

Question

很容易证明，给定一些具有未知分布的密钥集，我们不能构造一个将这些密钥作为输入的函数输出均匀分布的值的函数。

因此，我们着眼于未知分布的通用散列函数。

Knuth建议利用无理数字的非重复数字 - 最值得注意的是黄金比例 - 以便将键均匀分布在表格范围内。

CLRS建议您简单地将钥匙mod作为一个大的素数，再次将键大致均匀分布在表格范围内，并分解重复模式。

在这两种情况下，目标似乎是均匀分配密钥。但是，在研究诸如Murmur2，SeaHash等解决方案时，他们似乎在确保“蝴蝶状”效果方面付出了相当大的努力：给定一个键，更改任何1位都有很好的机会改变每一个位在散列。

为什么这种行为是可取的？在TAOCP和CLRS中提出的解决方案的缺点是什么？

如果期望的行为是分解输入键集合中的任何模式，那么这里隐含的假设是，显示模式类型的键集合更可能是疯狂的？这是否合理？

对不起，如果我不精确。

编辑：不需要具有加密强度。目的是尽量减少碰撞。

Answer 1

我不是100％确定这一点，但这可能是不同作者在不同情境下所做出的不同假设的人工产物。

Knuth在TAoCP中的工作是在任何其他书籍或散列函数开发之前完成的。当时，Knuth在某种意义上开创了如何分析和思考不同的算法和数据结构。当时，“使用某种方案将物品分配给水桶”的想法是众所周知的，但没有人认真考虑过如何最好地选择该方案。他的方法在数学上简单而优雅，并且在当代（20世纪70年代）的硬件上运行得很快。总的主题是“如果你打算根据某种功能进行分配，这里有一个非常好用和简单的使用方法，并且有一个很好的理论背后的原因”。

Knuth的第一篇分析数据结构或算法IIRC的论文是在散列表上。他在假设散列码是一致随机的假设下做了分析，并表明在这些假设下散列表性能良好。正如你所提到的，很明显，如果你选择任何固定散列函数，你将会退化输入情况。一群人开始思考如何处理这个问题，许多人尝试从可用散列函数池中随机选择散列函数。在二十世纪七十年代后期，Wegman发表了一篇名为Universal Classes of Hash Functions的论文，其中概述了一个正式的数学定义，它将一系列散列函数作为一个很好的散列函数来选择。本文包含一个证明，即通用散列函数族具有较低的期望碰撞次数，这使得它们适用于链式散列表。

CLRS的第一版于1990年出版，并纳入了Knuth对线性探测的分析（假设真正随机的散列码）和对使用通用散列的链式散列表的分析。换句话说，它承认你在选择哈希函数时必须小心（没有一个固定函数总是可以工作，所以看看通用哈希函数），但是在假设你有一个“足够好”的哈希函数的情况下也做了一些数学计算。 （后来的理论发展包括里程碑式的论文“Why Simple Hash Functions Work，”解释了为什么弱哈希函数与输入分布中的一小部分熵结合在一起，实际上就像真正的随机函数一样，而后来的一些工作表明，独立的散列函数是你在线性探测表中获得非常好的性能所需要的。）

所有上述工作都在理论学习中，其目标是建立良好的数学框架来分析数据结构并制定具体的为实现良好的分配和效率而在实践中提出方法建议。

然后是真实世界，在那里从业者并不总是得到数学，数学经常落后于从业者正在做的事情。

如果你看看哈希函数的大部分工作，许多哈希函数假定你正在处理的数据可以很容易地以有意义的方式分解为整数单元。但真实的数据并不总是以这种方式分解。或者您可能拥有像C++，Java，Python等语言，其中每个对象都有一个“a”散列码，它与其相关的散列码，而不是理论家们推荐的具有可用散列函数系列的理由。 （1）疯狂快速评估，（2）可以在同一程序或多个机器的不同运行中工作，以及（3） ）在实践中“足够好”，人们不会抱怨。这就是你获得像MurmurHash之类的散列函数的地方 - 它们真的很好地满足了这个需求。假设你没有针对敌对选择的输入工作，这些散列函数都很好。

有趣的是，我们现在看到Knuth的 乘法散列函数的复苏。允许您将不同散列函数组合在一起的库（如Boost的hash_combine）使用该技术给出确定性但散布良好的散列码，给定多个现有散列作为输入。

总结：

• 很多的这些差异是历史。 Knuth为如何分析哈希函数奠定了理论基础，并考虑了您拥有单一哈希函数的情况。后来关于通用哈希的研究给出了使用哈希函数类的不同视角和框架。

• 理论与实践之间始终存在差距。对于非对抗情况，像MurmurHash这样的非随机哈希码很简单，快速并且运行良好。与单个整数值相比，它们也适用于可变长度输入。