研究人员为古老的线性探测哈希表注入了数据存储的新活力

文章正文
发布时间:2024-08-20 13:01

麻省理工学院(MIT)计算机科学与人工智能实验室(CSAIL)的一项新研究,为我们指引了可提升计算机数据存储和检索效率的新方向。包括该校博士生 William Kuszmaul 在内的三位研究人员指出,新发现与所谓的“线性探测哈希表”有关。据悉,1954 年问世的该方法,也是当今可用的最古老、简洁、快速的数据结构之一。

数据结构提供了在计算机中组织和存储数据的方法,哈希表就是最常用的方法之一。以线性探测哈希表(linear-probing hash tables)为例,其特点是能够将信息存储于一个线性数组中。

William Kuszmaul 指出,假设某个数据库需要存储上万人的社保号码,我们需要依次得知社保号码(x),然后计算 x 的哈希函数 h(x),其提供了 1~10000 之间的随机数。

下一步,系统需要将随机数 h(x)移到数组中的相应位置,然后将社保号码(x)存入于此。

但若已经有东西占据了该位置,软件只需腾挪到下一个空闲位置,这也是‘线性探测’一词的由来。

后续需要检索该社保号码(x)的话,你只需前往指定的 h(x)位置。

若不存在,那就继续前进到下一个位置 —— 直到找到(x)、或到达了一个空闲位置,并最终得出(x)并不存在于数据库中的结论。

不过在删除特定条目的时候,通常会运用一些不同的协议。如果你在删除信息后,仅于哈希表中留下一个空位。那当稍后尝试查找其它内容时,可能会造成混淆。

为避免产生“数据库中不存在你正在寻找的条目”的混淆,数据库可以在那里做个“墓碑”(tombstone)小标记,以表明“这里曾经存在过一个元素,但现在已消失”。

这套理论已经延续了半个多月世纪,但此前几乎每个使用线性探测哈希表的人都认为 —— 如果你将哈希表填得太满,那长长的被占据的位置就会聚成一个‘集群’(clusters)。

结果就是想要找到一个空闲位置所花费的时间呈指数级(二次方)增长,直到完全脱离了实用的范畴。基于此,人们接受了以低容量来操作哈希表的培训。

长期以来,这个原则一直不利于高负载率。另一方面,它也让企业陷入了必须耗费重金来购买和维护硬件的尴尬。

好消息是,William Kuszmaul 刚刚和另外几位同事 —— 包括来自石溪大学的 Michael Bender、以及来自 Google 的 Brad Kuszmaul —— 彻底颠覆了既有的认知。

他们发现,对于插入和删除数量保持不变的应用程序(添加的数据量大致等于删除的数据量),线性探测哈希表可以在不牺牲速度的情况下、以高存储容量运行。

此外该团队设计了一种被称作‘墓地哈希’的新策略,涉及人为地增加放置在阵列中的‘墓碑’数量,直到它们占据大约一半的空闲位置。

作为保留空间,这些‘墓碑’可用于将来的数据插入。

William Kuszmaul 表示,这种方法与大家通常接受的“在线性哈希表中实现最佳性能”的相关指导背道而驰。

但正如他们在合著论文中所提到的那样,通过使用精心设计的“墓碑”,我们可以彻底改变线性探测的行为方式。

MIT News 指出,三人在今年早些时候发表的一篇论文中介绍了他们的最新发现。

此外在明年 2 月份于科罗拉多州博尔德举办的计算机科学基础(FOCS)研讨会上,他们还会作进一步的发表。

首页
评论
分享
Top