麻省理工學(xué)院 CSAIL 一項(xiàng)關(guān)于線性探測(cè)哈希表的新研究成果，有望讓計(jì)算機(jī)更有效地存儲(chǔ)和檢索數(shù)據(jù)。該成果由該校計(jì)算機(jī)科學(xué)博士生 William Kuszmaul 在內(nèi)的三人研究小組取得，對(duì) 1954 年推出的“線性探測(cè)哈希表”進(jìn)行了優(yōu)化。

　　“線性探測(cè)哈希表”于 1954 年推出，是當(dāng)今古老、簡(jiǎn)單和ZUI快的數(shù)據(jù)結(jié)構(gòu)之一。數(shù)據(jù)結(jié)構(gòu)提供了在計(jì)算機(jī)中組織和存儲(chǔ)數(shù)據(jù)的方法，而哈希表是ZUI常用的方法之一。在線性探測(cè)哈希表中，可以存儲(chǔ)信息的位置是沿著一個(gè)線性陣列。

　　例如，假設(shè)一個(gè)數(shù)據(jù)庫(kù)被設(shè)計(jì)用來(lái)存儲(chǔ) 10000 人的身份證號(hào)碼，Kuszmaul 建議：“我們?nèi)∧愕纳矸葑C號(hào)碼x，然后計(jì)算 x 的哈希函數(shù)，h（x），它給你一個(gè) 1 到10000之間的隨機(jī)數(shù)。下一步是拿著這個(gè)隨機(jī)數(shù) h（x），走到數(shù)組中的那個(gè)位置，把 x，即身份證號(hào)碼，放到那個(gè)位置”。

　　Kuszmaul 說(shuō)，如果已經(jīng)有東西占據(jù)了那個(gè)位置，你只需前進(jìn)到下一個(gè)空閑位置并把它放在那里。這就是“線性探測(cè)”一詞的由來(lái)，因?yàn)槟阋恢本€性地向前移動(dòng)，直到找到一個(gè)空位。

　　為了以后檢索那個(gè)社會(huì)安全號(hào)碼，x，你只要去指定的位置，h（x），如果它不在那里，你就向前走，直到你找到 x 或來(lái)到一個(gè)空閑位置，并得出結(jié)論說(shuō) x 不在你的數(shù)據(jù)庫(kù)中。

　　對(duì)于刪除一個(gè)項(xiàng)目，如社會(huì)安全號(hào)碼，有一個(gè)有點(diǎn)不同的協(xié)議。如果你在刪除信息后只是在哈希表中留下一個(gè)空位，那么當(dāng)你后來(lái)試圖尋找其他東西時(shí)就會(huì)造成混亂，因?yàn)檫@個(gè)空位可能會(huì)錯(cuò)誤地暗示你正在尋找的項(xiàng)目在數(shù)據(jù)庫(kù)中無(wú)處可尋。為了避免這個(gè)問(wèn)題，Kuszmaul 解釋說(shuō)，你可以去元素被移除的地方，在那里放一個(gè)叫做“墓碑”（tombstone）的小標(biāo)記，表示這里曾經(jīng)有一個(gè)元素，但現(xiàn)在已經(jīng)消失了。

　　這個(gè)常規(guī)程序已經(jīng)被遵循了半個(gè)多世紀(jì)。但在所有這些時(shí)間里，幾乎所有使用線性探測(cè)哈希表的人都認(rèn)為，如果你允許它們變得太滿，長(zhǎng)長(zhǎng)的被占點(diǎn)會(huì)跑到一起形成“集群”。因此，找到一個(gè)空閑位置所需的時(shí)間會(huì)急劇上升--事實(shí)上是四倍--需要如此長(zhǎng)的時(shí)間，以至于不切實(shí)際。因此，人們被訓(xùn)練成在低容量下操作哈希表--這種做法會(huì)影響公司必須購(gòu)買和維護(hù)的硬件數(shù)量，從而造成經(jīng)濟(jì)損失。

　　該團(tuán)隊(duì)還設(shè)計(jì)了一種新的策略，稱為“墓地散列”（graveyard hashing），其中包括人為地增加放置在陣列中的墓碑?dāng)?shù)量，直到它們占據(jù)了大約一半的空閑位置。然后，這些墓碑保留了可用于未來(lái)插入的空間。

　　Kuszmaul 說(shuō)，這種方法與人們習(xí)慣上被指示的做法相反，“可以導(dǎo)致線性探測(cè)哈希表的ZUI佳性能”?；蛘?，正如他和他的合作者在他們的論文中所堅(jiān)持的那樣，“精心設(shè)計(jì)的墓碑的使用可以完全改變……線性探測(cè)的行為方式。”