麻省理工學院（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）研討會上，他們還會作進一步的發表。