本科生颠覆姚期智40年前猜想！意外发现新型哈希表，数据搜索速度突破理论上限

明敏 发自 凹非寺
量子位 | 公众号 QbitAI

姚期智40年前猜想被本科生意外颠覆！

00后本科生 安德鲁·克拉皮文 （Andrew Krapivin，简称小克） 发现了一种新型哈希表，数据搜索速度超过以往所有方法。

要知道，哈希表因为简易快速高性能，被广泛应用于计算机科学和编程中。

而这种新型哈希表在最坏情况下的查询和插入时间与(log x) ²成正比，远比之前认为的x快。

后者正是姚期智在1985年提出的猜想。

不仅如此，小克他们还发现非贪婪哈希表的平均查询时间可以达到一个与哈希表x无关的恒定值，这一发现也完全出乎意料。

网友：这太疯狂了！总是学生们实现了这些疯狂的发现。

这一发现对于理解和改进数据结构至关重要。

一场意外的颠覆

哈希表（Hash table）是根据键而直接访问在存储器存储位置的数据结构。

也就是说，它通过计算一个键值的函数，将所需查询的数据映射到表中一个位置让人来访问，这加快了查找速度。这个映射函数被称为哈希函数，存放记录的数组称作哈希表。

更通俗比喻，哈希表就好比一个很大的文件柜，其中有很多个抽屉（槽）。每个抽屉可以存放一个文件（数据项）。但是，文件柜很大，手动找文件肯定很麻烦。所以，你使用一个 文件编号（哈希函数） ，它会告诉你应该把某个文件放到哪个抽屉里，或者当你要找某个文件时，告诉你该去哪个抽屉。

比如存放一个文件，文件名是“苹果”，通过文件编号规则（哈希函数）得到一个数字，假设是 3，那么就把“苹果”文件放到文件柜的第3个抽屉。

如果两个文件（比如“苹果”和“香蕉”）的编号规则（哈希函数）计算出来是一样的（例如都被放到抽屉 3），那么就会发生 冲突 。为了应对这个问题，哈希表采用了处理冲突的策略，比如在抽屉里放一个“文件夹”（链表）来存放所有冲突的文件，或者把文件放到下一个抽屉。

衡量哈希表已使用空间与总空间的比例，被称为 负载因子 （Load Factor）。

负载因子(α)=存储元素的数量/哈希表桶的数量=n/m

当负载因子较小时，哈希表的空桶多、冲突少，查找效率较高，但可能浪费内存。

当负载因子较高时，哈希表冲突增加，查找性能可能下降。

1985年，姚期智在论文 《Uniform Hashing Is Optimal》 中提出，在具有特定属性的哈希表中，查找单个元素或空位的最佳方法是均匀探测（uniform probing），而且最坏情况的插入时间与x成正比。

即如果哈希表已经99%满了，那么需要查看100个不同位置，才能找到一个空位。

其中，x表示哈希表被填满的距离。

当x=100时，表示哈希表已经被填充了99%，负载因子为0.99。当x=1000时，表示哈希表被填充了99.9%，负载因子为0.999。

这个猜想在2021年被撼动了，不过这一切其实是场意外。

当时正在罗格斯大学读本科的小克读了一篇名为 《Tiny Pointers》 的论文。

这篇论文提出了tiny pointer的概念，它能指向计算机内存中的一段信息或一个元素。

读过论文后，小克意识到有一种方法可以进一步降低tiny pointer内存使用的方法。

为此，他需要使用哈希表来存储tiny pointer指向的数据。

在这个过程中，他发现了一种工作速度更快的哈希表。

即最劣查询和插入所需时间与（log x）²成正比，比之前姚期智论文中提出的x快得多。

最开始，小克的导师对这个新发现表示怀疑，毕竟哈希表从20世纪50年代诞生以来，已经被研究得很透彻了。

为了验证这一发现是否正确，导师法拉·科尔顿（Farach-Colton）找到了卡内基梅隆大学的威廉姆·库斯莫尔（William Kuszmaul）一起验证。

结果就是库斯莫尔发现，小克不仅发现了一个新的哈希表， 更进一步推翻了40年前的猜想。

网友：“不知”反而可以摆脱传统路径

为啥小克能轻松颠覆猜想呢？

因为他本来压根不知道姚期智提出的猜想，也是一种无心插柳了。

有人因此感慨：创新的最佳方式总是要忽略以往的一些路径。现在人们总是容易陷入前人的思维模式。

而且无独有偶，有人表示一位医学人员再次发现了复合梯形公式。

当然，能够提出新哈希表，也是因为小克本身就很优秀。

他本科就读于罗格斯大学，双修数学和计算机科学。