哈希游戏- 哈希游戏平台- 哈希游戏官方网站

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

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

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

　　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说：“你得到的是个常数，跟表有多满没关系。”这种恒定时间的发现，连作者自己都没料到。