计算机科学领域中一直存在着一个关于哈希表数据结构的长期挑战：如何在访问速度和存储空间利用之间取得最佳平衡。哈希表是一种被广泛应用的数据结构，支持快速地查找、插入和删除数据项。然而，想要让哈希表运行得更快，往往需要增加内存占用；若要减少内存占用，就可能导致查询速度变慢。
为了解决这个难题，无数理论家们不断探寻更好的解决方案。大约70年前，IBM的一位工程师在内部论文中提出了哈希表这种数据结构的构想。随后，科学家们针对哈希表的优化进行了长达数十年的研究。但在上个世纪里，这些优化方案往往只能在时间或空间这两个方面带来显著的提升。
直到2003年，研究人员提出了在理论上可以在速度和空间上同时实现显著飞跃的方案。然而，理想的情况和实际执行之间还有明显的差距。2022年，一个研究团队提出了一种全新的哈希表方案，理论上能实现时间和空间效率的最佳组合。这个团队使用了主数据结构和辅助数据结构，通过调整主数据结构中数据项的排列顺序，巧妙地减少了对辅助数据结构中内存的占用，而无需损失速度。
2023年，另一个研究团队尝试进一步改进方案，但未能成功。于是他们试图以全新的角度去验证第一个团队方案的理论极限。他们用通信复杂性理论进行了严格论证，得出的结论是: 哈希表在查询速度及内存占用方面的表现存在不可突破的下限。而令人惊喜的是，该下限竟与2022年第一组团队提出的方案完全吻合。这证明首个团队提出的哈希表设计已经是最优解，从原理上无法被超越。
这项研究不仅解决了困扰科学家数十年的难题，也印证了新理论方法的力量。这些新方法可能启发更多相关领域的突破性进展。尽管实际应用层面要完全达到哈希表最优方案还有很大的技术难度，研究人员也在进行持续的改进。目前，基于新理论研究提出的新哈希表方案，已经超越了现有最佳方案，空间占用缩小了三倍，查询速度提升了两倍。
这项研究成果具有显著意义，它明确了哈希表性能优化的极限，让计算机科学家能聚焦于其他理论领域的挑战。在未来，哈希表可能还会以多种方式得到持续优化，为计算机存储管理带来更多更优化的解决方案。
本文基于AI编译自Quanta Magazine, 本文观点不代表“沙鸥科报”立场，转载请联系原作者。如有侵权，请联系编辑处理。
