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

2021-11-22 13:27:45来源：cnBeta.COM 关键词：存储数据阅读量：20698

导读：麻省理工学院 CSAIL 一项关于线性探测哈希表的新研究成果，有望让计算机更有效地存储和检索数据。

　　麻省理工学院 CSAIL 一项关于线性探测哈希表的新研究成果，有望让计算机更有效地存储和检索数据。该成果由该校计算机科学博士生 William Kuszmaul 在内的三人研究小组取得，对 1954 年推出的“线性探测哈希表”进行了优化。

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

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

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

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

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

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

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

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

上一篇：利用人工智能和物联网技术开发智能家居

下一篇：研究称奇特的新材料或是两种超导体的结合体具有重要的量子计算用途

我要评论

昵称

匿名

文明上网，理性发言。（您还可以输入200个字符)

表情

所有评论仅代表网友意见，与本站立场无关。

国家数据局综合司关于征集数据基础设施建设优秀案例的通知
为落实《国家数据基础设施建设指引》（简称《建设指引》）工作部署，加快推进数据基础设施建设，现组织征集数据基础设施建设优秀案例，总结数据基础设施建设经验，遴选推广先进做法，供各方借鉴参考。
数据基础设施
2025-04-28 10:13:06
江波龙2024年营收175亿大增72%，净利润翻倍
江波龙发布2024年年报，全年营收174.64亿元，同比增长72.48%；净利润4.99亿元，同比大增160.24%。公司高端存储产品占比提升带动毛利率显著改善，企业级存储和Lexar品牌业务成为增长新引擎。2025年将重点布局AI服务器存储、UFS高端产品及海外市场拓展。
2024年业绩报告存储
2025-04-01 10:35:36
以高质量数据促进人工智能发展国家数据局将开展四方面工作
近期人工智能技术发展出现新的进展，引发全球广泛关注。这背后，离不开算法、算力、数据的协同创新。国家数据局局长刘烈宏说，高质量数据与人工智能的结合，将会进一步发挥数据和人工智能的倍增效应。
人工智能数据
2025-03-30 13:52:34
烟台：数据跨部门调用 “e拍通”跑出改革加速度
山东坚持分步实施、有序推进，在全省范围大力推行“免证办事”“一码通行”，凡是通过电子证照、数据共享可以获取的信息，不再要求企业和群众提供相应材料。
电子证照数据
2025-03-11 11:45:10
聚焦物流行业发展问题开展物流数据开放互联试点工作
随着数字经济时代的到来，物流行业正经历着变革。数据作为新的生产要素，正在重塑物流行业的运营模式和价值链。物流业数据融合是指将来自不同来源、不同格式的物流数据进行整合、处理和分析，以提取有价值的信息和知识的过程。
物流行业数据
2025-02-20 10:24:45
三部委联合印发《国家数据基础设施建设指引》推动数据基础设施高质量发展
近日，国家发展改革委、国家数据局、工业和信息化部联合印发了《国家数据基础设施建设指引》，旨在深入贯彻落实党的二十届三中全会关于建设和运营国家数据基础设施、促进数据共享的部署要求，推动国家数据基础设施高质量发展。
数据
2025-01-08 10:22:31

版权与免责声明：

凡本站注明“来源：智能制造网”的所有作品，均为浙江兴旺宝明通网络有限公司-智能制造网合法拥有版权或有权使用的作品，未经本站授权不得转载、摘编或利用其它方式使用上述作品。已经本网授权使用作品的，应在授权范围内使用，并注明“来源：智能制造网”。违反上述声明者，本站将追究其相关法律责任。

本站转载并注明自其它来源（非智能制造网）的作品，目的在于传递更多信息，并不代表本站赞同其观点或和对其真实性负责，不承担此类作品侵权行为的直接责任及连带责任。如其他媒体、平台或个人从本站转载时，必须保留本站注明的作品第一来源，并自负版权等法律责任。如擅自篡改为“稿件来源：智能制造网”，本站将依法追究责任。

鉴于本站稿件来源广泛、数量较多，如涉及作品内容、版权等问题，请与本站联系并提供相关证明材料：联系电话：0571-89719789；邮箱：1271141964@qq.com。