麻省理工學院 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 說，這種方法與人們習慣上被指示的做法相反，"可以導致線性探測雜湊表的最佳效能"。或者，正如他和他的合作者在他們的論文中所堅持的那樣，"精心設計的墓碑的使用可以完全改變......線性探測的行為方式。"
