研究人员为古老的线性探测哈希表注入了数据存储的新活力

资料图（viaMIT News）

数据结构提供了在计算机中组织和存储数据的方法，哈希表就是最常用的方法之一。以线性探测哈希表（linear-probing hash tables）为例，其特点是能够将信息存储于一个线性数组中。

William Kuszmaul 指出，假设某个数据库需要存储上万人的社保号码，我们需要依次得知社保号码（x），然后计算 x 的哈希函数 h（x），其提供了 1~10000 之间的随机数。

下一步，系统需要将随机数 h（x）移到数组中的相应位置，然后将社保号码（x）存入于此。

但若已经有东西占据了该位置，软件只需腾挪到下一个空闲位置，这也是‘线性探测’一词的由来。

后续需要检索该社保号码（x）的话，你只需前往指定的 h（x）位置。

若不存在，那就继续前进到下一个位置 —— 直到找到（x）、或到达了一个空闲位置，并最终得出（x）并不存在于数据库中的结论。

不过在删除特定条目的时候，通常会运用一些不同的协议。如果你在删除信息后，仅于哈希表中留下一个空位。那当稍后尝试查找其它内容时，可能会造成混淆。

为避免产生“数据库中不存在你正在寻找的条目”的混淆，数据库可以在那里做个“墓碑”（tombstone）小标记，以表明“这里曾经存在过一个元素，但现在已消失”。

这套理论已经延续了半个多月世纪，但此前几乎每个使用线性探测哈希表的人都认为 —— 如果你将哈希表填得太满，那长长的被占据的位置就会聚成一个‘集群’（clusters）。

结果就是想要找到一个空闲位置所花费的时间呈指数级（二次方）增长，直到完全脱离了实用的范畴。基于此，人们接受了以低容量来操作哈希表的培训。

长期以来，这个原则一直不利于高负载率。另一方面，它也让企业陷入了必须耗费重金来购买和维护硬件的尴尬。

好消息是，William Kuszmaul 刚刚和另外几位同事 —— 包括来自石溪大学的 Michael Bender、以及来自 Google  的 Brad Kuszmaul —— 彻底颠覆了既有的认知。

他们发现，对于插入和删除数量保持不变的应用程序（添加的数据量大致等于删除的数据量），线性探测哈希表可以在不牺牲速度的情况下、以高存储容量运行。

此外该团队设计了一种被称作‘墓地哈希’的新策略，涉及人为地增加放置在阵列中的‘墓碑’数量，直到它们占据大约一半的空闲位置。

作为保留空间，这些‘墓碑’可用于将来的数据插入。

William Kuszmaul 表示，这种方法与大家通常接受的“在线性哈希表中实现最佳性能”的相关指导背道而驰。

但正如他们在合著论文中所提到的那样，通过使用精心设计的“墓碑”，我们可以彻底改变线性探测的行为方式。

MIT News 指出，三人在今年早些时候发表的一篇论文中介绍了他们的最新发现。

此外在明年 2 月份于科罗拉多州博尔德举办的计算机科学基础（FOCS）研讨会上，他们还会作进一步的发表。