量子位
·
本科生颠覆姚期智40年前猜想！意外发现新型哈希表，数据搜索速度突破理论上限
💡
原文中文，约2200字，阅读约需6分钟。
📝
内容提要
本科生安德鲁·克拉皮文意外发现了一种新型哈希表，其查询速度超越了姚期智40年前的猜想，最坏情况下时间复杂度与(log x)²成正比。这一发现对数据结构的理解和改进具有重要意义，表明创新常源于意外探索。
🎯
关键要点
- 本科生安德鲁·克拉皮文发现了一种新型哈希表，查询速度超越姚期智40年前的猜想。
- 新型哈希表在最坏情况下的查询和插入时间与(log x)²成正比，远快于之前的x。
- 哈希表是一种根据键直接访问存储位置的数据结构，通过哈希函数加快查找速度。
- 负载因子衡量哈希表已使用空间与总空间的比例，影响查找效率。
- 姚期智在1985年提出的猜想认为最坏情况下的插入时间与x成正比。
- 小克的发现源于对《Tiny Pointers》论文的研究，意外发现了更快的哈希表。
- 小克的导师和其他学者验证了他的发现，推翻了40年前的猜想。
- 小克的成功与他对传统路径的忽视和自身的优秀背景有关。
➡️
