機器學習背景下的哈希演算法

作者：Tyler Elliot Bettilyon

編譯：weakish

編者按：Tyler Elliot Bettilyon深入淺出地介紹了哈希演算法以及基於機器學習的索引結構。

圖片來源：Tobias Fischer（Unsplash）

2017年12月，Google和MIT的研究人員發表了一篇刺激的論文，關於「learned index structures」（學習索引結構）。作者們在摘要中如此寫道：

我們相信將數據管理系統的核心組件替換為學習模型的想法，對未來的系統設計有著深遠的影響，這篇論文僅僅提供了對未來的可能性的短暫一瞥。

B樹（B-Tree）和哈希表（Hash Map）是索引演算法的基石，而Google和MIT的研究人員可能發現了新的競爭方案。這一發現可謂是「一石驚起千重浪」。

新研究提供了一個重新檢視某個領域的基礎的絕佳機會；而像索引這樣基礎（同時研究充分）的主題可不是經常有機會出現突破的。本文的主旨是介紹哈希表，簡要地總結影響其性能的因素，並直觀地介紹上述論文中應用於索引的機器學習概念。

（如果你很熟悉哈希表、碰撞處理策略、哈希函數性能，你可以跳讀本文，或者直接跳過本文，閱讀底部鏈接的三篇文章，以深入這些主題。）

作為對Google/MIT的回應，Peter Bailis及其斯坦福研究團隊警告我們不要扔掉演算法教材。Peter Bailis及其團隊在不使用任何機器學習的前提下，得到了Google/MIT論文中相似的結果（他們使用的是經典的Cuckoo哈希）。

無獨有偶，Thomas Neumann描述了基於B樹和樣條插值取得相似結果的方法。

當然，其實Google/MIT的論文中已經寫了：

值得重視的是，我們並不主張用學習索引結構完全取代傳統的索引結果。相反，我們只是概述了一種創建索引的新方法，該方法可以作為現有工作的補充，並且，可能為一個數十年的舊領域開啟了一個全新的研究方向。

所以，這些人在爭論什麼？哈希表和B樹是不是已經被欽定為衰老的名人堂成員？機器將重寫演算法教科書嗎？如果機器學習策略真比我們熟知的索引演算法更好，那將意味著什麼？在什麼情況下，學習索引優於舊演算法？

要回答這些問題，我們需要了解什麼是索引，索引解決什麼問題，什麼因素使一種索引方案比另一種更合適。

什麼是索引？

就核心而言，索引讓事物更容易找到和獲取。早在計算機發明之前，人類已經在創建索引了。文件櫃、百科全書、雜貨店的商品標籤，都是索引。

亞歷山大圖書館的第一任館長澤諾多托斯，設計了一個索引系統，將藏書按體裁分置於不同房間，同一體裁的書籍上架時按字母順序排列。他的同事卡利馬科斯進一步為圖書館編製了一份目錄（《Pinakes》），使館員可以通過作者姓名查找其著作在圖書館中的位置。（更多詳情，請閱讀The Great Library of Alexandria?一文。）自此以後，圖書館索引有不少創新，包括1876年發明的杜威十進位圖書分類法。

在亞歷山大圖書館，索引將一段信息（書名或作者）映射到圖書館中的物理位置。儘管我們的計算機是數字設備，計算機中的信息實際上存儲於物理位置。文章的文本也好，信用卡的交易信息也罷，甚至是受到驚嚇的喵星人的視頻，數據存在於計算機的某個或某些物理位置。

在內存和固態硬碟中，數據以流經一系列晶體管的電壓的形式儲存。在硬碟中，數據以磁性的形式儲存在碟片的磁軌上。當我們索引計算機中的信息時，我們創建將某部分信息映射到計算機中的物理位置的演算法。我們稱這一位置為地址（address）。

資料庫是典型的索引用例。我們設計資料庫，以儲存大量信息，一般而言，我們希望能高效地從資料庫獲取信息。搜索引擎的核心是互聯網信息的巨型索引。哈希表（hash table）、二叉搜索樹（binary search tree）、前綴樹（trie）、B樹（B-Tree）、布隆過濾器（bloom filter）都是索引。

不難想見，在巨大的亞歷山大圖書館錯綜複雜的大廳里尋找特定的東西很有挑戰性，但我們不應該想當然地以為人類產生的數據以指數級增長。互聯網上的信息遠遠超過了任何時代的圖書館，而Google的目標是索引全部這些信息。人類已經創建了許多索引的策略，這裡我們將查看一個一直以來都很常用的數據結構，它碰巧是一個索引結構：哈希表。

什麼是哈希表？

初看起來，哈希表是一個基於哈希函數的簡單數據結構。有各種不同的哈希函數，本文中的哈希函數限於哈希表中用的哈希函數，不包括密碼學上的哈希函數，校驗值（checksum），及其他種類的哈希函數。

哈希函數接受某個輸入值（例如一個數字或一段文本），然後返回一個整數，這個整數稱為哈希碼（hash code）或哈希值（hash value）。對任何給定輸入而言，哈希碼總是相同的；也就是說，哈希函數是確定的。

創建哈希表時，我們首先分配一些空間（在內存中或在存儲器中）——你可以將其想像為新創建一個尺寸隨意的數組。如果有很多數據，我們可能會使用一個較大的數組；如果數據不多，我們可能會使用一個較小的數組。當我們想要索引一段數據時，我們創建一個鍵值對，其中鍵為辨別數據的信息（比如資料庫記錄的主鍵），值為數據本身（比如一整條資料庫記錄）。

我們將鍵傳給哈希函數，以便將值插入哈希表。哈希函數返回一個整數（哈希碼），我們使用這個整數——以數組大小為模——作為數組的存儲索引。如果我們想從哈希表中取回值，我們直接根據鍵重新計算哈希碼，然後根據所得位置從數組中取得數據。

在使用杜威十進位系統的圖書館中，「鍵」是圖書所屬的分類，「值」是圖書本身。「哈希碼」是使用杜威十進位過程創建的數值。例如，一本解析幾何的書的「哈希碼」是516.3. 自然科學是500，數學是510，幾何是516，解析幾何是516.3. 從這一角度來說，杜威十進位系統可以被看成圖書的哈希函數，圖書根據其哈希值擺放。

這不是一個完美的類比。和杜威十進位數字不同，哈希表中用於索引的哈希值通常不包含什麼信息——在一個完美的類比下，圖書館的書目將包含每本書的精確位置，基於有關書的一段信息編排（也許是書名，也許是作者的姓氏，也許是ISBN號……），但圖書不會按照任何有意義的方式排列，除了同鍵的圖書會放在同一個書架上，你可以通過圖書的鍵在圖書館的書目系統中查找書架號。

這一簡單過程是所有哈希表的基礎。然而，基於這一簡單想法的技術，產生了很多複雜性，這是為了確保哈希索引的正確和高效。

哈希索引的性能考量

哈希表的複雜度和優化主要源於哈希碰撞。當兩個以上鍵產生同一哈希碼時，碰撞就發生了。考慮以下簡單哈希函數（假定鍵為整數）：

儘管任何獨特的整數乘以13後都將產生獨特的整數，根據鴿巢原理，所得哈希碼終將出現重複：我們無法把6件物品放到5個筐里，同時保證不把兩件物品放到一個筐里。因為我們的存儲空間是有限的，我們不得不使用以數組大小為模的哈希值，因此我們總會遇到碰撞。

稍後我們將討論處理這些無法避免的碰撞的策略，但首先值得一提的是，哈希函數的選擇將提高或減少碰撞的幾率。想像一下我們有16個存儲位置，同時我們將從以下兩個哈希函數中選一個：

在這一情形下，如果我們哈希0-32，將產生28次碰撞，哈希值0、4、8、12將各有7次碰撞。而的碰撞將均勻散布在每個索引上，共有16次碰撞。這是因為的乘數4是哈希表尺寸16的因子。而選用的是一個質數，所以除非哈希表的尺寸是13的倍數，我們不會碰到的分組問題。

我們可以寫一段代碼驗證這一點：

這種選用質數作乘數的策略實際上非常常見。質數降低了哈希碼和數組尺寸共有同一因子的可能性，從而降低了碰撞的機會。

multiply-shift哈希是一個類似的策略，但用快速的移位運算代替了模運算。Murmur哈希和Tabulation哈希與multiply-shift哈希類似，分別用循環移位運算及異或運算（結合查表）代替了模運算。評測這些哈希函數涉及比較運算速度、產生的哈希碼分布、處理不同種類數據（例如，整數、浮點數、字元串）的靈活性。SMhasher提供了哈希函數的評測套件。

選擇良好的哈希函數可以降低碰撞率，加快計算速度。不幸的是，無論選擇哪個哈希函數，我們終將遇到碰撞。如何處理碰撞對哈希表的總體性能將有顯著影響。處理碰撞的兩個常用策略是鏈表法（chaining）和線性探測法（linear probing）。

鏈表法直截了當，也容易實現。我們在哈希表的索引中存儲一個鏈表的頭指針。如果碰到碰撞，我們就將發生碰撞的值附加到鏈表末尾。因此，嚴格來說，查找哈希表不再是「常數時間」，因為我們需要遍歷一個鏈表。如果哈希函數產生許多碰撞，會形成非常長的鏈表，導致性能下降。

線性探測這個概念也很簡單，不過實現起來有點麻煩。在線性探測中，哈希表的每個索引仍然對應單個元素。如果索引i遇到碰撞，我們將檢查索引i+1是否為空，如果i+1為空，那麼我們就將數據儲存在那裡；如果i+1不為空，那麼我們就檢查i+2，如果仍不為空，我們再檢查i+3，以此類推，直到找到空位。同樣，嚴格來說，查找哈希表不再是「常數時間」，如果一個索引有很多碰撞，我們需要搜尋一個長序列。此外，每次碰撞都將增加出現下次碰撞的概率，因為，和鏈表法不同，碰撞項最終佔去一個新索引。

紅色表示碰撞

聽起來鏈表法更好，但由於性能上的特點，線性探測法得到了廣泛應用。主要而言，這是因為鏈表對緩存的利用很糟糕，而數組能很好地利用緩存。相同尺寸的情況下，檢查鏈表中的所有鏈接比檢查數組中的所有索引要慢太多。這是因為數組的索引在物理上是連續的。而在鏈表中，創建新節點時才指定其位置，這個新節點和它的鄰居在物理上不一定是連續的。結果導致鏈表中相鄰的節點很少在物理上相鄰（指RAM晶元的實際位置）。而CPU緩存的工作機制決定了，訪問連續的內存位置很快，而隨機訪問內存位置要慢得多。當然，實際情況比上面說的要複雜一點，詳見What Every Programmer Should Know About Memory一文。

機器學習基礎

想要理解機器學習如何用於重建哈希表（和其他索引技術）的關鍵特性，讓我們快速地回顧一下統計建模的主要思想。統計學中的模型是一個函數，它接受某個向量作為輸入，返回一個標籤（分類）或一個數值（回歸）。輸入向量包含數據點的所有相關信息，而標籤/數值輸出是模型的預測。

在一個預測高中生能不能上哈佛的模型中，向量可能包含學生的GPA、SAT分數、所屬的興趣社團，以及其他有關學術成就的值；標籤將是真/假（能上哈佛/不能上哈佛）。

在預測抵押貸款違約率的模型中，輸入向量可能包含信用分、信用卡賬戶數、超期率、年收入，以及其他抵押貸款申請人的經濟狀況信息；模型可能會返回0到1之間的數字，表示違約的概率。

一般而言，機器學慣用於創建統計模型。機器學習從業人員將大型數據集和機器學習演算法結合起來，在數據集上運行演算法得到的結果稱為訓練好的模型（trained model）。機器學習的核心是創造自動基於原始數據創建精確模型的演算法，無需人類幫助機器「理解」數據實際上表示什麼。這和其他人工智慧不同，在其他人工智慧中，人類細緻檢查數據，給計算機提供一些數據意味著什麼的線索（例如，通過定義啟發式演算法），並定義計算機如何使用數據（例如，使用極小化極大演算法或A*搜索演算法）。不過，在實踐中，機器學習經常組合經典的非學習技術；一個AI智能體將經常同時使用學習策略和非學習策略以達成目標。

考慮下著名的國際象棋AI「深藍」和最近的圍棋AI「AlphaGo」。深藍完全是一個非學習AI；人類計算機程序員和人類國際象棋專家合作創建了深藍。深藍從不「學習」任何東西——人類國際象棋專家仔細的編碼了機器的評估函數。

和深藍不同，AlphaGo在不藉助圍棋專家的明確指示的前提下創建了自己的評估函數。在這一情形下，評估函數是一個訓練好的模型。通過成千上萬次對局，機器學習演算法決定如何評估任何具體的棋盤狀態。AlphaGo通過查看數百萬樣本，教會自己哪一步將提供最大的獲勝幾率。

（以上大大簡化了AlphaGo這樣的系統的工作機制，請通過AlphaGo創造者DeepMind的博客了解詳情。）

作為索引的模型，偏離ML常態的做法

在論文中，Google的研究人員假定索引是模型，至少機器學習模型可以用作索引。他們主張：模型是接受某種輸入並返回標籤的機器；如果輸入是鍵，標籤是模型估計的內存地址，那麼模型可以用作索引。儘管這聽起來挺直截了當，索引問題並不特別適合機器學習，因此Google團隊的做法和常規的機器學習不大一樣。

通常而言，機器學習模型的任務是給出估計。而對索引數據而言，用估計作為結果是不可接受。索引的唯一任務是找出數據在內存中的精確位置。因此，Google記錄了訓練中每個節點的最大和最小誤差。使用這些值作為邊界，可以通過在邊界內搜索找到元素的精確位置。

另一方面，機器學習通常需要小心地避開過擬合；過擬合的模型在訓練數據上能給出非常精確的預測，但在訓練集之外的表現非常糟糕。而在索引任務中，訓練數據就是被索引的數據，因此訓練數據同時也是測試數據。從這個意義上說，索引註定「過擬合」。不過，沒有免費的午餐，如果我們在索引中增加新的項，模型可能會給出極其糟糕的預測。因此，這一學習模型的應用範圍限制在只讀資料庫系統。

學習哈希

Google的研究人員感興趣的一個問題是：知道數據的分布是否有助於創建更好的索引？在我們之前提到的傳統策略（乘以質數、multiply-shift哈希、Murmur哈希……）中，數據的分布被明確地忽視了。每個待處理的項被視為獨立值，而不是一個更大的數據集（具有許多有價值的屬性可供考量）的一部分。結果，即使在許多最先進的哈希表中，都有很多空間被浪費了。

哈希表的常見實現使用50%的空間，這意味著哈希表佔用的空間為實際數據的2倍。如果我們在數組的所有筐內都放入項目的話，哈希表中仍有一半的地址是空的。研究人員發現，用機器學習模型取代標準哈希函數，可以顯著減少浪費的空間。

這沒什麼好驚訝的，基於輸入數據學習所得的哈希函數當然可以更均勻地分布數據，因為ML模型已經知道了數據的分布！這是一個潛在的顯著降低基於哈希的索引所需存儲空間的強有力的方法。不過，這不是沒有代價的，ML模型需要訓練步驟，因此比我們之前提到的標準哈希函數要慢。

也許基於ML的哈希函數可以用於像數據倉庫（data warehousing）這樣高效使用內存至關重要，同時算力不是瓶頸的場景。

然而，在內存效率很關鍵的場景中，我們已經有Cuckoo哈希了。

Cuckoo哈希

Cuckoo哈希是在2001年發明的，得名於杜鵑（Cuckoo）。Cuckoo哈希其實是處理碰撞的演算法（和之前提到的鏈表法、線性探測法的角色一樣，並非哈希函數）。Cuckoo哈希得名的由來是某些種類的杜鵑雌鳥會移除其他鳥的鳥巢中的蛋，以便下自己的蛋。在Cuckoo哈希中，待處理的數據竊取舊數據的地址。

Cuckoo哈希是這樣工作的：當你創建哈希表時，你將哈希表分為兩個地址空間；我們稱其為主地址空間和次地址空間。這兩個空間使用不同的哈希函數。這兩個哈希函數可能非常相似，比如都是「乘以質數」，只不過乘數不同。相應地，這兩個函數稱為主哈希函數和次哈希函數。

剛開始，在Cuckoo哈希插入新值只使用主地址空間。當遇到碰撞時，新數據將舊數據驅趕到次地址空間（舊數據將重新使用次哈希函數進行哈希）。

如果次地址空間中對應的位置已經被佔據了，會發生第二次驅趕，原本在次地址空間中的數據會被趕回主地址空間。由於這樣的驅趕可能造成死循環，通常會設定一個每次插入的驅趕次數的閾值。達到閾值時，會重建哈希表（分配更多空間或選擇新哈希函數）。

在內存受限的場景下，這一策略非常高效。即使在高佔用率下，Cuckoo哈希的性能依然穩定（鏈表法和線性探測法則不然）。

Bailis及其斯坦福團隊發現，通過一些優化，即使在99%佔用下，Cuckoo哈希仍然能夠保持高性能。基本上，Cuckoo哈希能夠達到「機器學習」哈希函數的高利用率，而無需昂貴的訓練階段。

索引的未來

隨著更多ML工具的研發，以及TPU之類的硬體的進展，索引能從機器學習獲益更多。另一方面，Cuckoo哈希這樣的演算法提醒我們機器學習技術不是萬能神葯。

索引的基礎看起來不會在一夜之間被機器學習策略取代，但自我調節索引這一想法是一個強大而激動人心的概念。在未來，DynamoDB、Cassandra，乃至PostgreSQL、MySQL都可能逐漸採用機器學習策略。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！