线性探测哈希表新研究成果有望让计算机更有效地存储和检索数据

“线性探测哈希表”于 1954 年推出，是当今最古老、最简单和最快的数据结构之一。数据结构提供了在计算机中组织和存储数据的方法，而哈希表是最常用的方法之一。在线性探测哈希表中，可以存储信息的位置是沿着一个线性阵列。

例如，假设一个数据库被设计用来存储 10000 人的身份证号码，Kuszmaul 建议：“我们取你的身份证号码x，然后计算 x 的哈希函数，h(x)，它给你一个 1 到10000之间的随机数。下一步是拿着这个随机数 h(x)，走到数组中的那个位置，把 x，即身份证号码，放到那个位置”。

Kuszmaul 说，如果已经有东西占据了那个位置，你只需前进到下一个空闲位置并把它放在那里。这就是“线性探测”一词的由来，因为你一直线性地向前移动，直到找到一个空位。

为了以后检索那个社会安全号码，x，你只要去指定的位置，h(x)，如果它不在那里，你就向前走，直到你找到 x 或来到一个空闲位置，并得出结论说 x 不在你的数据库中。

对于删除一个项目，如社会安全号码，有一个有点不同的协议。如果你在删除信息后只是在哈希表中留下一个空位，那么当你后来试图寻找其他东西时就会造成混乱，因为这个空位可能会错误地暗示你正在寻找的项目在数据库中无处可寻。为了避免这个问题，Kuszmaul 解释说，你可以去元素被移除的地方，在那里放一个叫做“墓碑”（tombstone）的小标记，表示这里曾经有一个元素，但现在已经消失了。

这个常规程序已经被遵循了半个多世纪。但在所有这些时间里，几乎所有使用线性探测哈希表的人都认为，如果你允许它们变得太满，长长的被占点会跑到一起形成"集群"。因此，找到一个空闲位置所需的时间会急剧上升--事实上是四倍--需要如此长的时间，以至于不切实际。因此，人们被训练成在低容量下操作哈希表--这种做法会影响公司必须购买和维护的硬件数量，从而造成经济损失。

该团队还设计了一种新的策略，称为“墓地散列”（graveyard hashing），其中包括人为地增加放置在阵列中的墓碑数量，直到它们占据了大约一半的空闲位置。然后，这些墓碑保留了可用于未来插入的空间。

Kuszmaul 说，这种方法与人们习惯上被指示的做法相反，"可以导致线性探测哈希表的最佳性能"。或者，正如他和他的合作者在他们的论文中所坚持的那样，"精心设计的墓碑的使用可以完全改变......线性探测的行为方式。"