stevessr
(Stevessr)
1
前奏：
被推翻：
others:
本科生推翻姚期智40年前的猜想，提出全新哈希表算法突破搜索效率极限 - 知乎
弹性哈希
然而，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²)。该映射的设计确保了在插入过程中，较早被访问的探测位置能够更高效地找到空槽，从而降低整体探测复杂度。
漏斗哈希
在弹性哈希方法的基础上，研究者进一步提出了一种新的贪婪开放寻址（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。在每一层的插入尝试中，元素会随机选择一个子块，并依次扫描该子块中的位置以寻找空槽。这种分层探测策略确保了大多数插入操作可以在前几层完成，而仅有极少数插入会进入最底层的存储区域。
1 Like
moxcops
(VIM)
6
请问您这里方不方便放一个论文原文，很好奇，但没搞过论文，对我比较麻烦。
tig
(ひぐらしのなく頃に)
7
system
(system)
Closed
9
此话题已在最后回复的 30 天后被自动关闭。不再允许新回复。
