💡
原文中文，约3600字，阅读约需9分钟。
📝
内容提要
1985年，姚期智提出的哈希表猜想被本科生Krapivin推翻。他通过研究微型指针和新哈希表，发现其查询速度远超传统方法，颠覆了40年的观点。这一成果对计算机科学中的哈希表进行了重要的重新审视。
🎯
关键要点
- 1985年，姚期智提出的哈希表猜想被本科生Krapivin推翻。
- Krapivin通过研究微型指针和新哈希表，发现其查询速度远超传统方法。
- Krapivin的研究始于2021年秋季，他在阅读一篇论文后受到启发。
- 他提出了一种新的哈希表设计，能够更快地找到指定元素。
- Krapivin的教授起初对新设计持怀疑态度，但最终得到了验证。
- Krapivin的研究推翻了姚期智在1985年提出的核心猜想。
- 新哈希表的插入策略包括弹性哈希和漏斗哈希，证明了搜索复杂度超出以往认为的水平。
- 哈希表的核心思想是利用哈希函数将数据的键转换为数组的索引。
- Krapivin的研究表明，最坏情况查询和插入所需的时间与(log x)²成正比，远快于姚期智的猜想。
- 研究还表明，非贪婪哈希表的平均查询时间与哈希表的填满程度无关，始终是一个常量。
- 这一发现可能不会立即带来应用，但有助于更好地理解数据结构。
➡️
