按年被提到
20252025 · 6 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:2501.02305 · cs.DS

Optimal Bounds for Open Addressing Without Reordering

无重排开放寻址哈希表的最优界
Martin Farach-Colton, Andrew Krapivin, William Kuszmaul · 2025

不重排元素的开放寻址哈希表,探测次数远优于旧结论

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 6 人首次 2025-02-10 · 最近 2025-05-18
6不同的人
3活跃月份
4讨论串
5被引(OpenAlex)

论文重新审视开放寻址哈希表:在不对已插入元素重排的前提下,如何用尽量少的探测次数完成查找。作者给出新的插入策略,使期望(摊还与最坏情况)查找复杂度明显优于此前认为的极限,并推翻了 Yao 在 Uniform Hashing is Optimal 中留下的核心猜想,所有结果都配有匹配的下界。

HN 为什么提它

这篇论文是 Wired 等媒体报道的哈希表突破背后的原始论文,HN 上的人用它讨论新插入策略为什么要越过第一个空槽继续探测。

奠基之作难度 4 / 5约 90 分钟经得起时间
读之前最好知道
1哈希表与开放寻址(open addressing)
2摊还分析(amortized analysis)
3概率与期望计算
4Yao 的均匀哈希(uniform hashing)结论

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用orlp · 2025-02

“Skimming the paper [1], the key difference they used is that their hash table insertion algorithm will probe further than the first empty slot, instead of greedily filling the first empty slot it finds.”

略读论文,指出关键差别是插入时会探测超过第一个空槽,而非贪心填充
Undergraduate shows that searches within hash tables can be much faster原评论 ↗
引用gield · 2025-02

“The actual paper with the breakthrough is from January 2025: Optimal Bounds for Open Addressing Without Reordering.”

指出报道的突破其实出自 2025 年 1 月的这篇原论文
Undergraduate shows that searches within hash tables can be much faster原评论 ↗
引用kaathewise · 2025-02

“The dereference table allows allocations to fail:”

指出论文第 12 页说明 dereference table 允许分配失败
Undergraduate shows that searches within hash tables can be much faster原评论 ↗
引用mNovak · 2025-03

“In any case, the full paper is here [1] if you don't want to scroll through the Wired article.”

给出论文全文,免得翻 Wired 的文章
Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of Hash Table原评论 ↗
被提交为 story · 2 次