为什么Knuth，CLRS散列函数不够？

Question

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

因此，我们将研究一般用途的散列函数，用于未知分布。

Knuth建议利用非理性数字的非重复数字--最显著的是黄金比率--来在表范围内均匀分配键。

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

在这两种情况下，目标似乎是平均分配钥匙。

但是，当考虑到Murmur2、SeaHash等解决方案时，他们似乎花了很大的精力来确保“蝶形”效应:给定一个键，任何1位都有很好的机会改变散列中的每一点。

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

如果想要的行为是打破输入键集合中的任何模式，那么这里的隐含假设是，显示任何类型模式的键集在野外更有可能发生？这合理吗？

抱歉，如果我说的不够精确。

编辑:不需要具有加密能力。目的是尽量减少碰撞。

Answer 1

我不能百分之百地肯定这一点，但这可能是不同作者在不同背景下所作不同假设的产物。

Knuth在TAoCP中的工作是在开发其他任何书籍或哈希函数之前完成的。当时，Knuth在某种意义上开创了如何分析和思考不同的算法和数据结构。当时，“用某种方案把东西分配到桶里”的想法是众所周知的，但没有人认真地想过如何最好地选择这个方案。他的方法在数学上简单而优雅，并且在当代(1970年代)硬件上运行得很快。一般的主题是“如果你要按某种功能发布，这里有一个非常好的、简单的使用方法和一个很好的理论支持。”

Knuth的第一篇分析数据结构或算法的论文IIRC是在哈希表上。他在假设哈希码是一致随机的基础上进行了分析，并表明在这些假设下，哈希表表现良好。

但是，正如您所提到的，很明显，如果您选择任何固定的散列函数，那么就会有退化的输入情况。一群人开始思考如何处理这个问题，许多人尝试从可用的散列函数池中随机选择一个散列函数。上世纪70年代末，韦格曼发表了一篇题为“哈希函数的通用类”的论文，概述了一个正式的数学定义，即一个哈希函数家族要成为一个很好的哈希函数类别，就意味着什么。本文证明了通用散列函数族具有较低的期望碰撞数，从而使其更适合链式哈希表。

CLRS第一版于1990年出版，它包含了Knuth对线性探测的分析(假设是真正随机的哈希码)和使用通用散列的链式哈希表的分析。换句话说，它承认在选择散列函数时必须小心(没有一个固定的函数总是工作的，所以看看通用散列)，但是在假设您有一个“足够好”的散列函数的前提下，还要做一些数学运算。

(后来的理论发展包括具有里程碑意义的论文“为什么简单哈希函数有效”，解释了为什么弱哈希函数与输入分布中的少量熵组合在本质上就像真正的随机函数，后来的一些工作表明，在线性探测表中，只有5个独立的哈希函数才能获得很好的性能。)

所有上述工作都生活在Theoryland，其目标是为分析数据结构建立良好的数学框架，并为实践中的方法提供具体建议，以获得良好的分布和效率。

然后是真实世界，那里的实践者并不总是掌握数学，而数学往往落后于实践者所做的事情。

如果您查看哈希函数的大多数工作，许多哈希函数假设您处理的数据可以很容易地分解为整数单位，以一种有意义的方式。但是真实的数据并不总是这样分解得很好。或者您有一种语言，如C++、Java、Python等，其中每个对象都有“一个”哈希代码，即与其关联的哈希代码，而不是理论上推荐的具有可用哈希函数系列的哈希代码。

在这种情况下，尝试构建一个哈希函数并不是那么不合理-- (1)快速评估，(2)可以在同一程序或多台机器的不同运行中工作，(3)在实践中工作得“足够好”，人们不会抱怨。这就是得到像MurmurHash之类的散列函数的地方--它们非常非常好地满足了这一需求。假设您没有针对对手选择的输入进行工作，这些哈希函数是很好的。

有趣的是，我们现在看到了Knuth的乘法散列函数的复兴。允许您将不同的哈希函数组合在一起的库，如Boost的hash_combine，使用这种技术提供一个确定性但传播良好的哈希代码，并将多个现有哈希作为输入。

概括地说：

• 这些差异中有很多是历史的。Knuth为如何分析散列函数奠定了理论基础，并考虑了只有一个散列函数的情况。后来关于通用散列的工作为处理类哈希函数提供了一个不同的视角和框架。
• 理论和实践之间总是有差距。对于非对抗性的情况，像MurmurHash这样的非随机散列是简单、快速和工作良好的.与单个整数值相比，它们还能很好地处理可变长度的输入。