solidot新版网站常见问题,请点击这里查看。

科学家找到数据存储和时间的最佳平衡

数据存储
Wilson (42865)发表于 2024年02月10日 21时04分 星期六

来自钢之色
1953 年 IBM 科学家 Hans Peter Luhn 提出了一种存储和检索信息的新方法,它就是哈希表(hash table),如今已内置在几乎所有计算机系统中。哈希表是历史最悠久、速度最快、最简单且使用最广泛的数据结构之一,它设计执行三个操作:插入,在数据库里加入新条目;查询,获取一个条目或检查该条目是否存在;删除。Chrome 或 Safari 等浏览器可能内置了多个哈希表去跟踪不同类的数据。哈希表不可避免的存在权衡取舍。1957 年另一位 IBM 计算机科学家 W. Wesley Peterson 指出了哈希表面临的技术挑战:需要足够快以快速检索必要的信息,需要紧凑使用尽可能少的内存。两个目标从根本上是矛盾的:哈希表有更多内存时能更快访问和修改数据库,哈希表使用更少空间时操作会很慢。几十年来,研究人员一直在寻找哈希表时间和空间的最佳平衡。2022 年纽约石溪大学的 Michael Bender 等人发表论文,提出了一种具有时间和空间效率最佳组合的新哈希表。2023 年普林斯顿大学 Huacheng Yu 领导的一个团队证明 Bender 的哈希表是理论上的最优解。由于新哈希表太复杂,还没人尝试在短时间去构建,而且理论上快的算法在实践中未必快。


https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/
https://arxiv.org/abs/2111.00602
https://arxiv.org/abs/2306.02253