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

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

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

　　Kuszmaul 說,，如果已經(jīng)有東西占據(jù)了那個位置,，你只需前進(jìn)到下一個空閑位置并把它放在那里。這就是“線性探測”一詞的由來，因為你一直線性地向前移動,，直到找到一個空位,。

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

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

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

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

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