线性探测哈希表新钻研功能有看让合计机更实用天存储战检索数据

发布时间：2025-11-18 04:50:30 来源： 作者：开发者笔记

麻省理工教院 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 讲，那类格式与人们夷易近俗上被调拨的做法相同，"可能导致线性探测哈希表的最佳功能"。或者，正如他战他的开做者正在他们的论文中所坚持的那样，"详尽设念的墓碑的操做可能残缺修正......线性探测的动做格式。"

相关文章