Credit:pix abay/CC0 Public Domain包括麻省理工学院计算机科学博士学生威廉·库兹莫尔(William Kuszmaul)在内的三名研究人员发现了一种可能导致计算机中更有效的数据存储和检索的方法。该团队的发现与所谓的“线性探测哈希表”有关，该哈希表于1954年推出，是当今最古老、最简单、最快的数据结构之一。数据结构提供了在计算机中组织和存储数据的方法，哈希表是最常用的方法之一。在线性探测散列表中，可以存储信息的位置位于线性阵列中。
库兹莫尔建议，例如，假设一个数据库被设计用来存储10，000人的社会保障号码。“我们取你的社保号x，然后我们计算x，h(x)的哈希函数，得到一个1到10，000之间的随机数。”下一步是取那个随机数，h(x)，到数组中的那个位置，把x，社会安全号，放到那个位置。
如果已经有什么东西占据了那个位置，库兹莫尔说，“你只要向前移动到下一个自由位置，把它放在那里。这就是术语“线性探测”的由来，因为你一直线性前进，直到找到一个开阔的地方。”为了以后检索那个社会安全号码x，你只需要去指定的地点h(x)，如果它不在那里，你就向前移动，直到你找到x或者来到一个自由的位置，并得出x不在你的数据库中的结论。
删除一个项目有一个稍微不同的协议，比如社会保险号。如果您只是在删除信息后在哈希表中留下了一个空位置，这可能会在您稍后尝试查找其他内容时造成混乱，因为空位置可能会错误地暗示您正在查找的项目在数据库中找不到。为了避免这个问题，Kuszmaul解释说，“你可以去元素被移除的地方，在那里放一个叫做‘墓碑’的小标记，这表明这里曾经有一个元素，但现在它不见了。”
这个通用程序已经遵循了半个多世纪。但在那段时间里，几乎所有使用线性探测散列表的人都认为，如果你让它们变得太满，长段被占用的点会聚集在一起形成“簇”。结果，找到一个空闲位置所需的时间会急剧增加——事实上是二次增加——时间长到不切实际。因此，人们被训练在低容量下操作散列表——这种做法可能会通过影响公司必须购买和维护的硬件数量而造成经济损失。
但是这个由来已久的原则，长期以来一直不利于高负荷因素，已经被库兹莫尔和他的同事，石溪大学的迈克尔·本德和谷歌的布拉德利·库兹莫尔的工作彻底颠覆了。他们发现，对于插入和删除数量保持不变的应用程序，并且添加的数据量大致等于删除的数据量，线性探测哈希表可以在不牺牲速度的情况下以高存储容量运行。
此外，该团队设计了一种新的策略，称为“墓地散列法”，包括人为增加放置在阵列中的墓碑数量，直到它们占据大约一半的空闲位置。然后，这些墓碑会保留空间，以供将来插入。
库兹莫尔说，这种方法违背了人们通常被要求做的事情，“可以在线性探测哈希表中获得最佳性能。”或者，正如他和他的合著者在他们的论文中所坚持的那样，“墓碑的精心设计使用可以完全改变……线性探测行为的景观。”
库兹莫尔在今年早些时候发表的一篇论文中与本德和库兹莫尔一起总结了这些发现，该论文将于2月份在科罗拉多州博尔德市举行的计算机科学基金会(FOCS)研讨会上发表。
Kuszmaul的博士论文顾问，麻省理工学院计算机科学教授Charles E. Leiserson(他没有参与这项研究)同意这一评估。“这些新的令人惊讶的结果推翻了关于哈希表行为的最古老的传统智慧之一，”雷瑟森说。"这些经验教训将在理论家和实践者中间回响多年."
至于将他们的结果转化为实践，Kuszmaul指出，“构建哈希表需要考虑很多因素。虽然我们从理论角度大大推进了这个故事，但我们才刚刚开始探索事物的实验方面。”
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
