麻省理工學院（MIT）計算機科學與人工智慧實驗室（CSAIL）的一項新研究，為我們指引了可提升計算機數據存儲和檢索效率的新方向。 包括該校博士生 William Kuszmaul 在內的三位研究人員指出，新發現與所謂的「線性探測哈希表」有關。 據悉，1954 年問世的該方法，也是當今可用的最古老、簡潔、快速的數據結構之一。

資料圖（via MIT News）

數據結構提供了在計算機中組織和存儲數據的方法，哈希表就是最常用的方法之一。 以線性探測哈希表（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）研討會上，他們還會作進一步的發表。