美本科生改进哈希表, 颠"覆40年"数：据科学

Rutgers大学本科生Andrew Krapivin发明新哈希表，搜索速度超乎想象，推翻40年猜想，揭示数据存储新可能。

2021年秋天，Rutgers大学本科生Andrew Krapivin偶然读到一篇论文，当时他并未太在意。两年后，他终于抽出时间细读这篇名为“Tiny Pointers”的文章，纯粹出于兴趣，却没想到这会彻底改变他对计算机科学的看法。文中提到的“指针”是引导你找到计算机内存中某个信息的箭头般存在。Krapivin突发奇想，能否让这些指针更“小巧”，占用更少的内存。可要实现这个目标，他得先找到一种更聪明的办法来整理这些指针指向的数据。

他把目光投向了常用的哈希表。这种数据存储方式简单实用，但在摆弄过程中，Krapivin发现自己无意间创造出了一种全新哈希表。它的速度快得惊人，查找特定元素时用时更短、步骤更少。他的前教授Martín Farach-Colton起初并不看好这个设计。毕竟，哈希表是计算机科学里研究最透彻的结构之一，这样的突破听起来像是天方夜谭。为了保险起见，Farach-Colton请来了常合作的伙伴William Kuszmaul帮忙验证。Kuszmaul却兴奋地说：“你不只是搞了个酷炫的哈希表，你直接推翻了一个40年的老猜想！”

Krapivin(现为剑桥大学研究生)、Farach-Colton(现任职纽约大学)和Kuszmaul联手在2025年1月发表论文，证明这个新哈希表确实能以超乎想象的速度找到元素，直接否定了长期被视为真理的猜想。Cornell Tech的Alex Conway评价道：“这篇论文意义重大。哈希表是最古老的数据结构之一，至今仍是存储数据的高效手段，但仍有未解之谜。这篇文章出人意料地解开了几个。”

哈希表之所以无处不在，是因为它简单好用。它只支持三种操作：搜索元素、删除元素、插入元素。早在1950年代，第一批哈希表就已出现，此后科学家们从未停止研究，想弄清这些操作的速度极限。比如，搜索或插入能有多快？这通常取决于在哈希表中找到空位的时间，而空位多少又跟表的“满度”有关。满度可以用百分比表示，比如50%或90%，但研究者常处理几乎满载的情况，于是用一个数字“x”来描述离100%满还有多近。x是100时，表满99%；x是1000时，满99.9%。这个指标让评估操作耗时变得更直观。

过去的研究表明，在常见哈希表中，最糟情况下的插入(比如插到最后一个空位)所需时间与x成正比。Kuszmaul解释：“如果表满99%，你可能得检查100个位置才能找到空位。”1985年，计算机科学家Andrew Yao在一篇论文中提出，对于某些特定哈希表，最佳搜索方式是随机检查位置，也就是“均匀探测”。他还断言，在最糟情况下，找到最后一个空位的时间不可能比x更快。40年来，大多数人都信了他的猜测。

Krapivin却是个例外，因为他根本不知道这个猜想。“我完全没听说过Yao的理论，”他说。他从微型指针入手，摸索出一种不靠均匀探测的新哈希表。在这个表里，最糟情况下的搜索和插入时间与(log x)²成正比，远比x快得多，直接戳破了Yao的猜想。Farach-Colton和Kuszmaul帮他证明，(log x)²是对Yao研究的那类热门哈希表的最佳极限。Carnegie Mellon的Guy Blelloch称：“这个结果美妙极了，解决了一个经典难题。”

滑铁卢大学的Sepehr Assadi补充：“他们不仅推翻了猜想，还找到了最优解。没准我们还得再等40年才能知道答案。”更令人震惊的是，这篇论文还挑战了Yao的另一个结论。1985年，Yao研究了所有可能的平均查询时间，证明对于某些“贪婪”哈希表(新元素必须插到第一个空位)，平均时间不可能优于log x。Krapivin团队好奇这个限制是否适用于非贪婪哈希表。他们给出了反例：一种非贪婪哈希表的平均查询时间远超log x，甚至跟x无关。Farach-Colton说：“你得到的是个常数，跟表有多满没关系。”这种恒定时间的发现，连作者自己都没料到。

这些成果或许不会立刻改变现实应用，但Conway认为意义深远：“深入理解这类数据结构很重要。谁知道呢，也许某天这个发现会解锁实用中的新突破。”从Rutgers的课堂到剑桥的研究室，Krapivin用好奇心和创造力，掀翻了40年的定论，也让人看到数据科学的无限可能。

本文译自 Quanta Magazine，由BALI编辑发布。

（内容来源：上观新闻）