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

2021-11-22 11:44:02 文章来源:网络
“线性检测哈希表”于1954年推出。它是当今最古老、最简单和最快的数据结构之一。数据结构提供了在计算机中组织和存储数据的方法,哈希表是最常用的方法之一。在线性探测哈希表中,可以存储信息的位置是沿着线性阵列的,例如,假设数据库设计用于存储10000个人Id号。Kuszmaul建议:“我们取你的ID号x,然后计算x散列函数H(x),它会给你一个介于1和10000之间的随机数。接下来是保持这个随机数H(x)。转到数组中的某个位置,并将x,ID号放在该位置。如果某个位置已被占用,则只需转到下一个自由位置并将其放在该位置。这是术语“线性检测”的起源“,因为你线性向前移动,直到找到一个空缺
为了稍后检索该社会保险号码x,你只需转到指定的位置H(x)。如果它不在那里,你继续前进,直到你找到X或来到一个空闲的位置,并得出结论,X不在你的数据库中
对于删除一个项目,如社会保险号码,有一个稍微不同的协议。如果删除信息后只在哈希表中留下一个空格,那么在以后尝试查找其他内容时会造成混乱,因为这个空格可能会错误地暗示您正在查找的项目在数据库中找不到。为了避免这个问题,kuszmaul解释说,你可以去元素被移除的地方,在那里放置一个称为“墓碑”的小标记,表明这里有一个元素,但现在它已经消失了——这个惯例已经沿用了半个多世纪。但在所有这些时候,几乎所有使用线性探测哈希表的人都认为,如果让它们变得太满,长时间占用的点就会聚集在一起形成;集群";。因此,找到一个免费位置所需的时间将急剧增加——事实上是四倍——如此之久,这是不切实际的。因此,培训人员在低容量下操作哈希表-这种做法将影响公司必须购买和维护的硬件数量,导致经济损失
团队还设计了称为“墓地哈希”的新策略,这包括人为增加放置在阵列中的墓碑数量,直到它们占据大约一半的可用空间。然后,这些墓碑会保留空间,以便将来插入“这种方法与人们习惯于被指示的做法相反”;它可以导致线性探测哈希表的最佳性能;。或者,正如他和他的合作者在他们的论文中所坚持的那样,“我们的目标是:;使用精心设计的墓碑可以完全改变人类的行为。。。线性检测。
上一篇:冬季大衣这样“叠穿”保暖又时髦

下一篇:最后一页
热点
本站所刊登的各种资讯﹑信息和各种专题专栏资料,均为徐州都市网版权所有,未经协议授权禁止下载使用。

Copyright © 2000-2020 All Rights Reserved