哈希表（hash table）是计算机科学中最基础也最重要的数据结构之一，它的历史可以追溯到 20 世纪 50 年代早期。哈希表的核心思想是通过一个哈希函数，将任意范围的键值映射到一个固定大小的数组空间中。
图丨一个作为哈希表的小型电话簿（来源：WikiPedia）
这种数据结构就像一个巨大的抽屉柜，每个数据都可以被迅速放入某个抽屉中，并在需要时快速取出。但当抽屉柜接近装满时，找到合适的空抽屉就变得越来越困难。
也就是说，当一个哈希表接近装满时（比如说已经占用了 99% 的空间），要在剩余空间中找到一个空位至少需要进行与填充率成正比的次数搜索。这就意味着，如果哈希表已经 99% 满了，那么在最坏情况下，需要大约 100 次尝试才能找到一个空位。这个理论限制就像物理学中的光速极限一样，被认为是不可逾越的。
1985 年，图灵奖得主姚期智在其具有里程碑意义的论文 Uniform Hashing is Optimal 中提出在具有特定属性的哈希表中，随机选择抽屉的方法，即均匀探测（uniform probing）是最优的选择。
图丨相关论文（来源：Journal of the ACM）
近 40 年来，计算机科学家们普遍认为姚期智的这个猜想是正确的。这种共识不仅影响了数据库系统的设计，也深刻影响了众多依赖高效数据存储的现代应用程序。然而，这个看似坚不可摧的理论堡垒，最近被一位年轻的本科生撼动了。
因为“无知”推翻 40 年来的猜想
这个突破性的发现源于一个看似偶然的机会。2021 年秋天，罗格斯大学的本科生 Andrew Krapivin 在浏览学术论文时，发现了一篇名为 Tiny Pointers 的文章。这篇论文探讨了一种新型的数据指针技术，能够大幅减少计算机内存的使用。那时候 Krapivin 并没有想太多，但两年后，当他真正开始深入研究这篇论文时，他意识到这里面隐藏着更多的可能性。
图丨相关论文（来源：arXiv）
Tiny Pointers 这篇论文探讨了一个看似简单但意义深远的问题：如何用更少的比特位来存储计算机中的指针。传统的指针需要 log n 个比特才能在 n 个位置中定位一个元素。但这篇论文提出了一个巧妙的思路：如果我们预先知道指针属于哪个用户，那么就可以利用这个额外信息来压缩指针的大小。
正是这种压缩指针的思路启发了 Krapivin 对哈希表的新认识，在哈希表搜索过程中，我们其实也可以利用之前探测获得的信息来指导后续的搜索。
相比之下，传统方法则假设每次探测都是独立的、均匀随机的。而 Krapivin 没有被这一种方式所束缚，其实也只是因为他并不知道这种方法。
他用 Tiny Pointers 进行的探索导致了一种新型的哈希表——一种不依赖于均匀探测的哈希表。对于这种新的哈希表，最坏情况下的查询和插入所需的时间与 (log x)2 成正比——比 x 快得多。这一结果直接反驳了姚期智的猜想。
当 Krapivin 向他的前教授、Tiny Pointers 的共同作者 Martín Farach-Colton 展示这个设计时，后者最初显得相当怀疑。这种谨慎是可以理解的：哈希表是计算机科学中研究最充分的数据结构之一，重大突破似乎不太可能。但当论文的另一位合作者、卡内基梅隆大学的 William Kuszmaul 仔细审视这项工作时，他意识到了其革命性意义。
“你并不是仅仅发明了一个新的哈希表，”Kuszmaul 对 Krapivin 说，“你实际上完全推翻了一个存在了 40 年的猜想！”
最终，他们共同合作，完成了这篇论文。
图丨相关论文（来源：arXiv）
康奈尔理工学院的 Alex Conway 评价道：“这是一项开创性的工作。尽管哈希表已经有着悠久的历史，但关于它们的工作原理，我们仍然有很多需要了解的地方。这篇论文以令人惊讶的方式回答了其中的几个根本性问题。”
“弹性哈希”
要理解这项工作的开创性，我们需要先明确传统哈希表面临的根本性挑战。
在传统的开放寻址哈希表中，当我们需要插入一个新元素时，会按照某个预定义的探测序列逐个检查位置，直到找到第一个空位。这种方法就被称为“贪婪策略”，因为它总是急于接受第一个可用的位置。姚期智在 1985 年的论文中证明，在这种贪婪策略下，当哈希表接近满载时（比如说留有δ比例的空位），最坏情况下需要 O(δ^-1) 次探测才能找到一个空位。并且他猜想这个界限对于任何贪婪策略都是最优的。
然而，Krapivin 的工作证明，如果我们愿意放弃贪婪策略，实际上可以获得显著更好的性能。研究提出了一种新的哈希表构造方法，命名为“弹性哈希”（Elastic Hashing），成功实现了均摊探测复杂度 O(1) 的最优解，同时使得最坏情况的探测复杂度降至 O(log δ⁻¹)。这一研究不仅推翻姚期智的猜想，还在不依赖重排操作的前提下，首次证明了更优的探测复杂度下界。
就像 Tiny Pointers 通过利用额外的上下文信息来减少存储开销，弹性哈希通过收集更多的探测信息来做出更有效的放置决策。其核心思想是将整个哈希表划分为多个子数组，并通过一种二元探测结构进行索引。
在该模型中，哈希表被拆分为一系列大小指数递减的子数组，例如 A₁、A₂、...、A_⌈log n⌉，其中 |Aᵢ₊₁| = |Aᵢ|/2 ± 1。这种层次结构为非贪婪探测提供了可能，使得插入操作可以优先在负载较低的区域进行，同时保证查找过程的高效性。研究者引入了一个特定的映射 φ(i,j)，使得二维探测序列 hᵢ,ⱼ (x) 可以映射到一维探测序列 hφ(i,j)(x)，其中 φ(i,j) ≤ O(i·j²)。该映射的设计确保了在插入过程中，较早被访问的探测位置能够更高效地找到空槽，从而降低整体探测复杂度。
（来源：Quanta Magazine）
具体来说，弹性哈希采用分批次插入策略，以确保各个子数组的负载水平得到合理分配。首先，在初始批次 B₀中，哈希表的第一个子数组 A₁ 被填充至约 75% 的负载。随后，在后续的批次 Bᵢ 中，插入操作主要发生在 Aᵢ和 Aᵢ₊₁ 之间，确保每个子数组的负载保持在合理范围内。
插入过程中，如果某个子数组仍有较多可用槽位（空位比例高于 δ/2），新元素将尝试在该子数组内找到合适的位置。而当子数组接近满载时，插入算法会自动转向下一级子数组，以提高存储效率。此外，在最坏情况下，即所有子数组的空位都非常有限时，算法会退回到均匀探测策略，但这种情况的概率极低，确保了整体复杂度的优化。
数学分析表明，该方法能够显著降低均摊探测复杂度和最坏情况探测复杂度。首先，在均摊探测复杂度方面，研究者证明了弹性哈希的平均探测次数为 O(1)，这意味着大多数操作只需要常数次探测就能完成。远优于均匀探测的 O(log δ⁻¹)。其根本原因在于，弹性哈希将大多数插入操作限制在负载较低的子数组中，使得多数元素能够在少量探测后成功存储。
其次，在最坏情况探测复杂度方面，研究表明在无重排的情况下，任何开放寻址哈希的最坏情况探测复杂度必须至少达到 Ω(log δ⁻¹)，而弹性哈希实现了这一下界的最优匹配。
“漏斗哈希”
在弹性哈希方法的基础上，研究者进一步提出了一种新的贪婪开放寻址（Open Addressing）策略，命名为“漏斗哈希”（Funnel Hashing）。通过构造一种层级结构的哈希表，该方法实现了最坏情况的期望探测复杂度 O(log²δ⁻¹)，并且证明了这一界限的最优性。
漏斗哈希的基本思想是在哈希表中引入多级结构，使得元素在不同负载水平的区域之间进行分层存储，从而降低高负载情况下的探测次数。具体而言，哈希表被划分为多个层级，每一层内部进一步分为若干个等大小的子数组，所有子数组的大小按几何级数递减。假设哈希表的总容量为 n，研究者首先将其划分为两部分，其中一部分（记为A_α+1）的大小约为 δn，用于存储最难插入的元素，而剩余部分（记为 A'）再细分为 α 个子数组 A₁、A₂、...、Aα。这些子数组的大小递减关系满足 |Aᵢ₊₁| ≈ 3|Aᵢ|/4，并且每个 Aᵢ 进一步划分为若干个小块，每个小块的大小设定为 β，其中 β 取 O(logδ⁻¹)。
在插入过程中，每个元素首先会尝试插入最上层的子数组A₁，如果失败则依次尝试 A₂, A3,……直到成功找到空位或最终进入专门的存储区 A_α+1。在每一层的插入尝试中，元素会随机选择一个子块，并依次扫描该子块中的位置以寻找空槽。这种分层探测策略确保了大多数插入操作可以在前几层完成，而仅有极少数插入会进入最底层的存储区域。
数学分析表明，漏斗哈希的最坏情况期望探测复杂度为 O(log²δ⁻¹)，显著优于均匀探测的 O(δ⁻¹)。其核心证明建立在以下几个关键步骤之上。
首先，研究者证明了每个子数组在一定插入次数后都会达到接近饱和的状态，即子数组内部空槽的数量受严格控制。这意味着即使在较高负载的情况下，仍然可以保证大多数插入操作在 O(logδ⁻¹) 次探测内成功。其次，通过分析插入元素在不同层级上的分布，研究者证明了即使在最坏情况下，元素也只需经历 O(log²δ⁻¹) 次探测，即可找到一个可用的位置。此外，研究者还证明了这一界限的最优性，表明任何贪婪开放寻址哈希表都无法突破 Ω(log²δ⁻¹) 的最坏情况探测复杂度。
除了在期望探测复杂度上的优化，漏斗哈希还具备良好的高概率最坏情况保证。研究者进一步证明，在绝大多数情况下（即以1-1/poly(n) 的概率），任意一个元素的最坏情况探测复杂度不会超过 O(log²δ⁻¹ + log log n)。这意味着即使在极端负载的情况下，该方法仍然能够保持较为稳定的性能，而不会出现大幅度退化的情况。
图丨 Farach-Colton（来源：Andrew Farach-Colton）
总之，这一方法的提出不仅解答了姚期智在 1985 年提出的未解决问题，即最坏情况的期望探测复杂度是否可以低于 O(δ⁻¹)，还证明了均匀探测在贪婪算法框架下并非最优。对于贪婪哈希表，最坏情况下的探测复杂度可以降低到 O(log²δ⁻¹)，而对于非贪婪哈希表，平均查询时间甚至可以完全独立于负载因子 δ。
“这只是一个常数，与哈希表是否满无关”，Farach-Colton 说。无论哈希表是否满，查询的平均时间都可以达到常数级别，这个发现甚至出乎研究者自己的意料。
即便目前该研究可能不会立即带来工业界的应用，但理解数据结构的基础理论非常重要，因为“你永远不知道这样的结果什么时候会解锁某种新的突破，让实际应用变得更加高效。”Conway 表示。
参考资料：
1.https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
2.https://doi.org/10.1145/3828.3836
3.https://arxiv.org/abs/2501.02305
4.https://arxiv.org/abs/2111.12800
