📌 📄 内容摘要:
Stevessr 在 【转】Optimal Bounds for Open Addressing Without Reordering | 无需重新排序的开放寻址的最佳边界 中发帖
前奏：
被推翻：
others:
本科生推翻姚期智40年前的猜想，提出全新哈希表算法突破搜索效率极限 - 知乎
弹性哈希
然而，Krapivin 的工作证明，如果我们愿意放弃贪婪策略，实际上可以获得显著更好的性能。研究提出了一种新的哈希表构造方法，命名为“弹性哈希”（Elastic Hashing），成功实现了均摊探测复杂度 O(1) 的最优解，同时使得最坏情况的探测复杂度降至 O(log δ⁻¹)。这一研究不仅推翻姚期智的猜想，还在不依赖重排操作的前提下，首次证明了更优的探测复杂度下界。
就像 Tiny Pointers 通过利用额外的上下文信息来减少存储开销，弹性哈希通过收集更多的探测信息来做出更有效的放置决策。其核心思想是将整个哈希表划分为多个子数组，并通过一种二元探测结构进行索引。
在该模型中，哈希表被拆分为一系列大小指数递减的子数组，例如 A₁、A₂、…、...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/431113/1
─────────────────────────────
📢 来源：LINUX DO
