一名本科生推翻了图灵奖得主姚期智延续40年的数据科学猜想，能让哈希表平均查询时间成为一个与 x 无关的常数

自从计算机诞生以来，哈希表（hash table）就被视为最基础、最常用、研究最充分的数据结构之一。它能帮我们在海量数据中快速“插入、删除、查询”——效率之高使其遍布现代应用：从数据库管理到网络路由，再到编程语言的底层实现，几乎无处不在。也正因为它的重要性，围绕哈希表的理论研究和实践优化在过去几十年里始终没有停歇。

那么，哈希表还能多快？

在1985年的一篇里程碑式论文中，图灵奖得主姚期智（Andrew Yao）提出了一个被广泛接受的判断：在特定类型的哈希表中，要想在最坏情况下（例如表里只剩下最后一个空位）进行插入或查询，所需的操作次数与哈希表的“填充度”x（接近99%、99.9%乃至更高）呈正比。换言之，当哈希表已几近装满，要寻找空位或者特定元素时，每一次都需要“多试几个位置”才行。而这一推论，40年来一直是计算机科学领域的共识之一。

这次，一个来自本科生的意外发现，却推翻了这条“铁律”。

安德鲁·克拉皮文（Andrew Krapivin）本是罗格斯大学的一名普通本科生，却在阅读一篇名为“微型指针”（Tiny Pointers）的论文时，突发奇想：如果指针可以变得更“微型”，那能否连带着重新设计哈希表本身？结果不但设计出了全新结构，速度超出预期，更挑战了业界对“最坏情况下插入和查询速度”的旧有认知。在导师和合作者的帮助下，他证明这种新型哈希表在几近满载时，寻找元素或空位的耗时仅仅和(log𝑥)²成正比，而非 x 。 这一成果直接动摇了姚期智的著名猜想。

更令人惊讶的是，他们还证明了一个“平均查询时间”上的突破。

传统的研究结论认为，满足某些性质（例如“贪心”插入）的哈希表，其平均查询时间至少要达到(log𝑥)。但克拉皮文团队给出的非贪心策略却把这个瓶颈彻底打破，甚至能让平均查询时间成为一个与 x 无关的常数。这是此前的研究几乎无人想到的可能性。

具体信息可以看 QuantaMagazine 的这篇报道《Undergraduate Upends a 40-Year-Old Data Science Conjecture》。

点击图片查看原图

点击图片查看原图