前奏： 

被推翻： 

others: 


本科生推翻姚期智40年前的猜想，提出全新哈希表算法突破搜索效率极限 - 知乎 
弹性哈希 
然而，Krapivin 的工作证明，如果我们愿意放弃贪婪策略，实际上可以获得显著更好的性能。研究提出了一种新的哈希表构造方法，命名为“弹性哈希”（Elastic Hashing），成功实现了均摊探测复杂度 O(1) 的最优解，同时使得最坏情况的探测复杂度降至 O(log δ⁻¹)。这一研究不仅推翻姚期智的猜想，还在不依赖重排操作的前提下，首次证明了更优的探测复杂度下界。
就像 Tiny Pointers 通过利用额外的上下文信息来减少存储开销，弹性哈希通过收集更多的探测信息来做出更有效的放置决策。其核心思想是将整个哈希表划分为多个子数组，并通过一种二元探测结构进行索引。 
在该模型中，哈希表被拆分为一系列大小指数递减的子数组，例如 A₁、A₂、…、...