最好看的新闻,最实用的信息
05月16日 13.9°C-15.2°C
澳元 : 人民币=4.82
霍巴特
今日澳洲app下载
登录 注册

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

2021-11-22 来源: cnBeta 原文链接 评论0条

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

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

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

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

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

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

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

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

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

转载声明:本文为转载发布,仅代表原作者或原平台态度,不代表我方观点。今日澳洲仅提供信息发布平台,文章或有适当删改。对转载有异议和删稿要求的原著方,可联络content@sydneytoday.com。
今日评论 网友评论仅供其表达个人看法,并不表明网站立场。
最新评论(0)
暂无评论


Copyright Media Today Group Pty Ltd.隐私条款联系我们商务合作加入我们

电话: (02) 8999 8797

联系邮箱: info@sydneytoday.com 商业合作: business@sydneytoday.com网站地图

法律顾问:AHL法律 – 澳洲最大华人律师行新闻爆料:news@sydneytoday.com

友情链接: 华人找房 到家 今日支付Umall今日优选