美本科生改进哈希表，颠覆40年数据科学_iqoo|it芯片|手机评测|处理器

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评价道：“这篇论文意义重大。哈希表是最古老的数据结构之一，至今仍是存储数据的高效手段，但仍有未解之谜。这篇文章出人意料地解开了几个。 ”
【美本科生改进哈希表，颠覆40年数据科学】哈希表之所以无处不在，是因为它简单好用。它只支持三种操作：搜索元素、删除元素、插入元素。早在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)2成正比，远比x快得多，直接戳破了Yao的猜想。 Farach-Colton和Kuszmaul帮他证明， (log x)2是对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编辑发布。

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

推荐阅读

怎么看面条是熟了还是没熟，怎么样看面条熟了没

男耕女织是什么意思？——拥抱传统文化，传承中华民族优秀传统

禽类大肠杆菌病气囊炎表现如何

交通违章网上多久会更新

笔记本电脑排名推荐笔记本电脑排名2017

win10系统对文档快速加密方法

广州海珠区教育局关于发布2023年公办小学学位预警的通告

Redmi 10X搭载30倍变焦测评红米10x详细参数配置

同步通信卫星是什么通讯卫星是同步卫星吗

P 《星际争霸2》StarsWar预选赛 xiaoT vs Loner(T) #1

分享微商海报APP做出海报的图文操作。

MongoDB导入导出以及数据库备份,库昊

8万的车要首付多少钱

迎新年朋友圈哲理句子感谢有你的句子

净水器哪个牌子好安哪个好,我想买个净水机

坚果R1的nfc不知道出现什么毛病？