线性探测哈希表新研究成果有望让计算机更有效地存储和检索数据
麻省理工学院 CSAIL 一项关于线性探测哈希表的新研究成果,有望让计算机更有效地存储和检索数据。该成果由该校计算机科学博士生 William Kuszmaul 在内的三人研究小组取得,对 1954 年推出的“线性探测哈希表”进行了优化。
访问:
阿里云11.11上云狂欢节活动大厅
“线性探测哈希表”于 1954 年推出,是当今最古老、最简单和最快的数据结构之一。数据结构提供了在计算机中组织和存储数据的方法,而哈希表是最常用的方法之一。在线性探测哈希表中,可以存储信息的位置是沿着一个线性阵列。
例如,假设一个数据库被设计用来存储 10000 人的身份证号码,Kuszmaul 建议:“我们取你的身份证号码x,然后计算 x 的哈希函数,h(x),它给你一个 1 到10000之间的随机数。下一步是拿着这个随机数 h(x),走到数组中的那个位置,把 x,即身份证号码,放到那个位置”。
Kuszmaul 说,如果已经有东西占据了那个位置,你只需前进到下一个空闲位置并把它放在那里。这就是“线性探测”一词的由来,因为你一直线性地向前移动,直到找到一个空位。
为了以后检索那个社会安全号码,x,你只要去指定的位置,h(x),如果它不在那里,你就向前走,直到你找到 x 或来到一个空闲位置,并得出结论说 x 不在你的数据库中。
对于删除一个项目,如社会安全号码,有一个有点不同的协议。如果你在删除信息后只是在哈希表中留下一个空位,那么当你后来试图寻找其他东西时就会造成混乱,因为这个空位可能会错误地暗示你正在寻找的项目在数据库中无处可寻。为了避免这个问题,Kuszmaul 解释说,你可以去元素被移除的地方,在那里放一个叫做“墓碑”(tombstone)的小标记,表示这里曾经有一个元素,但现在已经消失了。
这个常规程序已经被遵循了半个多世纪。但在所有这些时间里,几乎所有使用线性探测哈希表的人都认为,如果你允许它们变得太满,长长的被占点会跑到一起形成"集群"。因此,找到一个空闲位置所需的时间会急剧上升--事实上是四倍--需要如此长的时间,以至于不切实际。因此,人们被训练成在低容量下操作哈希表--这种做法会影响公司必须购买和维护的硬件数量,从而造成经济损失。
该团队还设计了一种新的策略,称为“墓地散列”(graveyard hashing),其中包括人为地增加放置在阵列中的墓碑数量,直到它们占据了大约一半的空闲位置。然后,这些墓碑保留了可用于未来插入的空间。
Kuszmaul 说,这种方法与人们习惯上被指示的做法相反,"可以导致线性探测哈希表的最佳性能"。或者,正如他和他的合作者在他们的论文中所坚持的那样,"精心设计的墓碑的使用可以完全改变......线性探测的行为方式。"
关键词: 科学探索 线性探测哈希表新研究成果有望让计算机更有效地
推荐阅读
运动型轿车是什么 运动型轿车与普通车有何区别?
运动型轿车凭借着外观酷炫,动力性能强的特点,深受国内众多消费者的喜爱。特别是在年轻消费者心目中,运动型轿车基本上是购车的首选。但是 【详细】
汽油清洗剂是什么 汽油清洗剂加在汽油里是干嘛的?
最近有很多车主反映加油的时候总是建议用汽油清洁剂。但是,大部分人还是不太了解,还有就是一部分人纳闷汽油清洗剂加在汽油里是干嘛的?汽 【详细】
中国最便宜的汽车是哪个 最便宜的汽车汇总
现在汽车已经成为了大家最常见的交通代步工具了。但是,依然还是有很多的家庭非常的需要代步工具,却买不起特别贵的汽车。所以今天,我们就 【详细】
伊莱克斯冰箱质量怎么样 伊莱克斯冰箱质量好不好?
伊莱克斯冰箱质量怎么样:在2018年全球500强企业中,伊莱克斯排名第162位,在2020年全球2000强企业中,伊莱克斯排名第1965位,可见伊莱克斯 【详细】
劳动保护用品是什么 劳动保护用品有哪些?
劳动保护用品有哪些?劳动防护用品分为特殊劳动防护用品和一般劳动防护用品,一般劳动防护用品是指未列入目录的一般劳动防护用品。以下产品 【详细】
相关新闻
- 玛雅文明是什么 玛雅文明算一个高度发达的文明吗?
- 环球信息:如何在国内正常使用TikTok?
- 女闺蜜是什么意思(女生喜欢你的几大表现 你遇到过几个?)
- 快资讯丨shift键(Excel 中 Shift键的奇妙玩法,你知道几个?)
- 斐纳TOMEFON使用状况 斐纳TOMEFON吸尘器好不好用?
- 国产手机排名前十 国产手机排名前汇总
- 环球观点:至今还没有阳的人,他们天赋异禀,还是另有隐情?研究结果来了
- 新动态:iPhone 15 太炸了,标准版有大提升
- 全球即时看!vivo拒绝高价低配:骁龙870+144Hz屏,12GB+256GB跌至1769元
- 实现高并发秒杀的七种方式
- 全球看热讯:3D渲染引擎 HOOPS Visualize 2023全新发布-增加对顶点着色器支持
- 世界看热讯:「升级」Hubstudio多账号安全管理浏览器之扩展中心上线啦!
- 汽车早报 - 消息称蔚来布局百万元级别电动车 广汽称将继续为讴歌中国客户提供售后服务
- 今头条!车轮上的2022∣新能源与汽车出口带动:全国乘用车零售量同比增长1.9%
- 谷歌文档新功能:看到非打印字符
- 世界新消息丨一加新机质感高级,更有多项黑科技加持,3999的价格入手值吗?
- 焦点信息:中国手机品牌在2022年拿下俄罗斯市场份额65% 但高价机一个没有
- 2022年这5款熟悉的产品向我们告别
- 即时:陈副区长事件,引出一个老生常谈的问题,腾讯是否会保留聊天记录
- 我国首个具备独立运行能力的新能源储能项目在内蒙古并网通电