科学家找到数据存储和时间的最佳平衡|广达杂志

大约 70 年前，IBM 一位名叫 Hans Peter Luhn 的工程师悄然改变了计算机科学的进程。卢恩已经拥有多项专利，其中一项是关于一种可以测量布料纱支数的设备，另一项是关于确定可以用厨房里的原料制作什么混合饮料的指南。但在 1953 年的 IBM 内部论文中，他提出了一种用于存储和检索信息的新技术，该技术现已内置于几乎所有计算系统中：哈希表。

哈希表是一类主要的数据结构。它们提供了一种特别方便的方法来访问和更改大型数据库中的信息。但这项技术不可避免地需要权衡。

在1 1957中 纸 发表在 IBM 研究与开发杂志, W. Wesley Peterson 指出了哈希表带来的主要技术挑战：它们需要速度快，这意味着它们可以快速检索必要的信息。但它们也需要紧凑，使用尽可能少的内存。这两个目标从根本上是不一致的。当哈希表拥有更多内存时，可以更快地访问和修改数据库；在使用较少空间的哈希表中，操作会变得更慢。自从彼得森提出这一挑战以来，研究人员一直试图找到时间和空间之间的最佳平衡。

计算机科学家现在已经从数学上证明他们已经找到了最佳权衡。解决方案来自一个 对 最近的 文件 这是相辅相成的。 “这些论文解决了有关最佳时空权衡的长期悬而未决的问题，产生了令人非常惊讶的结果，我预计这些结果将在未来许多年产生重大影响，”说 迈克尔·米岑马赫哈佛大学的计算机科学家，没有参与这两项研究。

“我肯定会说这是一件大事，”补充道 拉斯穆斯·帕格，哥本哈根大学计算机科学家。 “很多人都在研究这个问题，试图看看可以在多大程度上压缩空间，同时还能实现高效的操作。这是我很想解决的问题。”

对其进行哈希处理

哈希表是当今最古老、最简单、最快且使用最广泛的数据结构之一。它们旨在执行三个基本操作：插入，将新项目添加到数据库；查询，访问一个项目或检查它是否存在；和删除。哈希表可以是短暂的（仅在特定程序运行时才存在），也可以是计算机操作系统的永久部分。 Chrome 或 Safari 等网络浏览器可能有多个内置哈希表，用于跟踪不同类型的数据。

哈希表中的条目成对存储，项目（信息本身）连接到标识信息的键。将一个键插入哈希表的查询算法中，它就会直接带您到该项目。这听起来可能没什么特别的，但对于庞大的数据库来说，它可以节省大量时间。

举一个极其简单的例子，看看《牛津英语词典》，它有超过 600,000 个单词的定义。如果数字版本依赖于哈希表，您可以简单地使用给定的单词作为键并直接进行定义。如果没有哈希表，字典可能会依赖于速度慢得多的搜索机制，使用消除过程最终收敛到所请求的定义。虽然哈希表可以在恒定的时间内（通常是一秒的一小部分）找到任何单词，但其他方法的搜索时间可能会随着字典中单词数量的增加而增加。哈希表还具有另一个优点：它可以保持字典动态，从而可以轻松插入新单词和删除过时的单词。

研究人员花了几十年的时间构建哈希表，试图最大限度地提高速度并最大限度地减少内存。在 20 世纪，解决方案往往只在某一方面（时间或空间）提供显着的收益。然后在 2003 年，研究人员 显示 从理论上讲，在时间和空间上同时实现效率的重大飞跃是可能的。然而，研究人员还需要二十年的时间才能找到两者之间的理想平衡点。

数据洗牌

2022 年，我们朝着这一目标迈出了重要的第一步 主要计算机科学会议 在罗马。在那里，一个团队提出了一种具有新功能的哈希表，可以提供迄今为止所设想的时间和空间效率的最佳组合。该论文的第一作者（按字母顺序排列）是石溪大学的 Michael Bender，因此通常被称为 Bender 等人。哈希表。虽然该团队没有尝试构建一个有效的哈希表，但他们证明原则上可以使用他们描述的功能来构建它。

为了评估他们提出的哈希表，该小组制作了一条权衡曲线——该曲线在一个轴上绘制每次操作（插入或删除）的时间，在另一轴上绘制内存占用的空间。但该图以一种特殊的方式定义空间：由于哈希表的构建方式，哈希表需要更多的内存，而不仅仅是存储给定的一组项目所需的最低内存。计算机科学家将这些额外的空间称为“浪费的位”，尽管它们并没有真正浪费，而且在某种程度上是必要的。权衡曲线上的空间轴测量每个密钥浪费的位数。

通过分析权衡曲线，研究人员可以计算出使用给定空间量的哈希表的最快时间。他们还可以翻转问题来找出给定操作时间内的最小可能空间。通常，一个变量的微小变化会导致另一个变量的微小变化，说 威廉·库兹莫尔，哈佛大学理论计算机科学家，也是 2022 年论文的合著者。 “如果你把时间加倍，也许每个密钥浪费的位数就会减半。”

但他们设计的哈希表却并非如此。 “如果稍微增加一点时间，每个密钥浪费的比特数就会呈指数级减少，”Kuszmaul 说。权衡曲线如此陡峭，简直是超乎想象的。

该团队将哈希表分为两部分。他们有一个主数据结构，其中存储的项目根本没有任何浪费的位，还有一个辅助数据结构，帮助查询请求找到它正在寻找的项目。虽然该小组没有发明辅助数据结构的概念，但他们确实做出了一个重要的发现，使他们的超高效哈希表成为可能：结构的整体内存效率取决于主结构如何排列其存储的项目。

基本思想是，主结构中的每个项目都有首选的存储位置 - 最佳位置、第二最佳位置、第三最佳位置，依此类推。如果某个项目处于最佳位置，则会将数字 1 附加到该项目上，并将该数字存储在辅助数据结构中。为了响应查询，二级结构仅提供数字 1，该数字说明了该项目在一级结构中的确切位置。

如果该项目位于第 100 个最佳位置，则辅助数据结构会附加数字 100。由于系统使用二进制，因此将数字 100 表示为 1100100。当然，存储数字 1100100 比存储数字 1 需要更多的内存。 — 当物品位于最佳位置时分配给该物品的编号。如果您要存储（比如说）一百万个物品，这样的差异就会变得很明显。

因此，团队意识到，如果不断地将主数据结构中的项目转移到更喜欢的位置，则可以显着减少辅助结构消耗的内存，而无需增加查询时间。

“在这项工作之前，没有人意识到可以通过移动信息来进一步压缩数据结构，”帕格说。 “这就是本德论文的重要见解。”

作者表明，他们的发明为最有效的哈希表建立了新的上限，这意味着它是迄今为止在时间和空间效率方面设计的最佳数据结构。但其他人可能做得更好的可能性仍然存在。

一定会成功

第二年，一支由 于化成普林斯顿大学的计算机科学家试图改进本德团队的哈希表。 “我们真的很努力，但没能做到。” 周仁飞是北京清华大学的学生，也是余团队的成员。 “那时我们怀疑它们的上限也是下限”——这是可能实现的最好结果。 “当上限等于下限时，游戏就结束了，你就会得到答案。”无论你多么聪明，没有哈希表可以做得更好。

于的团队采用了一种新颖的策略，通过根据第一原理计算下限来确定这种预感是否正确。首先，他们推断，要执行插入或删除，哈希表（或者实际上任何数据结构）必须访问计算机内存一定次数。如果他们能够计算出节省空间的哈希表所需的最小次数，他们可以将其乘以每次访问所需的时间（常数），从而给出运行时的下限。

但是，如果他们对哈希表一无所知（除了它节省空间），研究人员如何计算出访问内存所需的最少次数？他们纯粹从理论中推导出来，使用了一个看似不相关的领域，即通信复杂性理论，该理论研究需要多少位来在双方之间传递信息。最终，团队成功了：他们计算出了数据结构每次操作必须访问其内存的次数。

这是他们的主要成就。然后，他们能够为任何节省空间的哈希表建立运行时下限。他们发现它与 Bender 哈希表完全匹配。 “我们（一开始）认为它可以改进，”周说。 “事实证明我们错了。”这反过来意味着彼得森的问题终于得到了解决。

库兹莫尔说，除了回答这个几十年前的问题之外，余证明的惊人之处还在于它的普遍性。 “它们的下限适用于所有可能的数据结构，包括尚未发明的数据结构。”这意味着在内存和速度方面没有任何数据存储方法可以击败 Bender 哈希表。

散列到未来

尽管新的哈希表具有前所未有的效率，但没有人可能会在短期内尝试构建它。建造起来太复杂了。 “理论上快的算法在实践中不一定快，”周说。

库兹莫尔说，理论与实践之间的这种差距长期存在并不罕见，因为理论家往往会忽视恒定的因素。执行操作所需的时间通常乘以一个数字，这是一个常数，从理论角度来看，其精确值可能并不重要。 “但在实践中，常数确实很重要，”他说。 “在现实世界中，10 的因子就是游戏终结者。”

实际的哈希表仍然在实质性方面有所改进，即使它们距离理论理想还很远。例如，一个新的哈希表称为 冰山HT由 Bender、Kuszmaul 等人建造的，比它的前辈要好得多。根据 Kuszmaul 的说法，它的速度是当今最节省空间的哈希表的两倍，并且使用的空间比最快的哈希表少三倍。

Mitzenmacher 希望 2023 年的结果可能很快会带来另一种好处：“每当你得到一个新的下限——尤其是涉及一些新技术的下限——总是希望你可以使用它们……解决相关问题。”

这位计算机科学家说，当你知道自己已经解决了一个长期存在的难题时，也会产生智力上的满足感。 彼得·英迪克 麻省理工学院的。 “一旦确定某些数据结构无法改进，就可以帮助集中研究工作。”最后，数据研究人员可以将注意力从彼得森的挑战上转移开，专注于理论计算机科学中并不缺乏的新问题。