機器學習時代的哈希演算法，將如何更高效地索引數據

選自blog.bradfieldcs，作者：Tyler Elliot Bettilyon，機器之心編譯。

哈希演算法一直是索引中最為經典的方法，它們能高效地儲存與檢索數據。但在去年 12 月，Jeff Dean 與 MIT 等研究者將索引視為模型，探索了深度學習模型學習的索引優於傳統索引結構的條件。本文首先將介紹什麼是索引以及哈希演算法，並描述在機器學習與深度學習時代中，如何將索引視為模型學習比哈希演算法更高效的表徵。

2017 年 12 月，谷歌和麻省理工學院的研究人員發表了一篇研究論文 The Case for Learned Index Structures，該論文介紹了他們在「學習型索引結構」方面做出的探索。這些研究非常令人興奮，正如作者在摘要中所述：

「[…] 我們相信通過可學習的模型取代數據管理系統核心組件的想法對未來的系統設計有著深遠的影響，而我們這項工作對於未來的發展僅僅是驚鴻一瞥。」

事實上，谷歌和麻省理工學院研究人員提出的這項研究工作可以同索引世界中最為經典有效的 B-Tree 和哈希圖（Hash Map）相匹敵。工程界對機器學習的未來早已有了許多的觀點，因此這篇研究論文已經在 Hacker News，Reddit 乃至世界上所有的工業論壇中獲得了廣泛的關注和討論。

新的研究是重新審視一個領域基礎的絕佳機會，而且像索引等基礎性並且已經獲得足夠研究的技術很少會有機會取得更大的突破。本文作為哈希表的入門性介紹，簡要介紹了影響其快慢的主要因素，並為應用於索引構建技術的機器學習概念提供了直觀性理解。

針對谷歌/麻省理工學院合作發表的工作，Peter Bailis 和斯坦福大學的研究團隊回顧了索引構建的基礎知識，並勸誡我們不要扔掉經典的演算法書。Bailis 和他在斯坦福大學的團隊重新構建了可學習型索引策略，並且通過使用名為 Cuckoo Hashing 的經典哈希表策略，在不使用任何機器學習技術的條件下取得了相似的結果。

在另一個對谷歌/麻省理工學院合作發表的工作的回應中，Thomas Neumann 描述了另一種實現與學習型索引策略相似性能的方式，這種方式仍然使用了經過長久測試和深入理解的 B-Tree。當然，這些討論、對比實驗和對進一步研究的要求，正是谷歌/麻省理工學院團隊為之激動的理由，他們在論文中寫道：

「需要特彆強調的是：我們並不是要呼籲完全用學習型索引結構來替代傳統的索引結構。相反的是，我們勾畫出了一個全新的索引構建方法，它可以彌補現有工作的不足，甚至可以說是在已經有數十年歷史的研究領域中打開了一個全新的研究方向。」

那麼，究竟是什麼引起了人們如此的關注？哈希圖和 B-Trees（多路搜索樹）是否註定要被新技術所淘汰？機器是否即將重寫演算法教科書？如果機器學習策略真的比我們所知道和喜愛的通用索引策略更好，那麼它對計算機世界又意味著什麼呢？學習型索引在什麼情況下會超越舊的索引方式呢？

為了解決這些問題，我們需要理解什麼索引，它們解決了什麼問題以及是什麼決定了不同索引之間的優劣差異。

什麼是索引

索引的核心是要提高信息查詢和檢索的便捷性。早在計算機發明之前，人類就一直在對事物進行索引。當我們使用整齊的文件櫃時，我們使用的是一個索引系統。全卷百科全書可被視為一種索引策略，雜貨店裡的標籤過道也是一種索引。當我們有許多東西並且需要在集合中找到或識別特定的物品時，索引可以讓我們查詢的過程變得更加高效便捷。

Zenodotus，亞歷山大大圖書館的第一任館員，負責組織管理圖書館龐大的館藏。他設計的系統包括按照流派將書籍分組放入房間，並按字母順序放置書本。他的同行 Callimachus 走得更遠，引入了一個名為 pinakes 的中央目錄，它允許圖書管理員查找作者，並確定該作者的每本書在圖書館中的位置。包括 1876 年被發明的杜威十進位系統（Dewey Decimal System）在內，許許多多的圖書館索引構建方式相繼被發明出來。

在亞歷山大圖書館，索引被用於將一段信息（書或作者的名字）映射到圖書館內的物理位置。儘管我們的計算機是數字設備，但計算機中的任何特定數據實際上都駐留在至少一個物理位置。無論是文本、最近的信用卡交易記錄還是視頻，數據都存在於計算機上的某個物理磁碟位置。

在 RAM 和固態硬碟驅動器中，數據作為電壓存儲在一系列晶體管中。在較老的旋轉硬碟驅動器中，數據以磁碟格式存儲在磁碟的特定圓弧上。當我們將計算機中的信息編入索引時，我們創建了一些演算法，將部分數據映射到計算機中的物理位置。我們稱這個地址為地址。在計算機中，被索引的信息全部都是以比特形式存在的數據，索引用於將這些數據映射到它們的地址。

資料庫是索引編製的典型用例。資料庫旨在保存大量信息，並且一般來說，我們希望高效地檢索這些信息。搜索引擎的核心是對互聯網上可用信息的龐大索引，哈希表、二叉搜索樹、字典樹、B-樹和布隆過濾器都是索引的形式。

很容易想像在亞歷山大圖書館的迷宮大廳找到具體書籍會有多難，但我們不應該理所當然地認為人類產生數據的大小呈指數級增長。互聯網上人們可以獲取到的數據量遠遠超過任何時代的任何單個圖書館的容量，而谷歌的目標是將所有數據都編入索引。人類為索引創造了許多策略，我們在本文討論了歷史上最多產的數據結構之一，並且恰好是一種索引結構的哈希表。

什麼是哈希表

初看起來，哈希表是基於哈希函數的簡單數據結構，我們有許多種行為不同並且被用於不同目的的哈希函數。在接下來的部分中，我們將只描述哈希表中使用的哈希函數，而不對加密哈希函數、校驗和或任何其他類型的哈希函數展開討論。

哈希函數接受一些輸入值（例如數字或文本）並返回一個整數，我們稱之為哈希碼或哈希值。對於任何給定相同的輸入，哈希碼總是相同的，這意味著哈希函數必須是確定性的。

在構建哈希表時，我們首先為哈希表分配一些空間（在內存或磁碟中），我們可以視為創建一個任意大小的新數組。如果我們有很多數據，我們可能會使用較大的數組，如果我們只有少量數據，則可以使用更小的數組。任何時候我們想索引一個單獨的數據，就需要創建一個鍵值對，其中鍵（Key）是關於數據的一些標識信息，而值（Value）是數據本身。

我們需要將值插入哈希表中，將數據的鍵發送給哈希函數。哈希函數返回一個整數（哈希碼），我們使用這個整數（以數組的大小為模）作為我們數組中數值的存儲索引。如果我們想從哈希表中檢索值，我們只需重新計算鍵中的哈希碼並從數組中的該位置獲取數據，這個位置就是我們數據的物理地址。

在使用杜威十進位系統的圖書館中，「鍵」是書本所屬的一系列分類，「值」是書本身。「哈希碼」是我們使用杜威十進位過程創建的數值，例如一本解析幾何編碼得到了 516.3 的「哈希碼」，自然科學是 500、數學是 510、幾何是 516、解析幾何是 516.3。在這種方式下，杜威十進位系統可以被視為書籍的哈希函數，然後這些書將被放在與其哈希值對應的一組書架上，並按作者的字母順序排列在書架內。

我們的比喻不是特別地完美，與杜威十進位數字不同，哈希表中用於索引的哈希值通常不會提供信息——在完美的比喻中，圖書館目錄將包含每本書基於某一條相關信息的確切位置（可能是其標題，也許是作者的姓氏，也許是它的 ISBN 號碼......），但除非所有具有相同鍵的書籍被放在同一個書架上，並且我們可以使用鍵在庫目錄中查找到書架編號，否則書籍的分組或排序就是沒有意義的。

從根本上來說，這個簡單的過程全都是由哈希表來完成的。然而，為了確保哈希索引的正確性和效率，我們又在此基礎上構建了許多複雜的部分。

基於哈希索引的性能考量

哈希表中複雜性和優化的主要來源是哈希衝突（hash collisions）問題。當兩個或更多個鍵產生相同的哈希碼時會發生衝突。考慮如下的一個簡單的哈希函數，我們假定其中的鍵為整數：

function hashFunction(key) { return (key * 13) % sizeOfArray; }

雖然任何唯一的整數在乘以 13 時會產生唯一的結果，但由於鴿巢原理（Pigeonhole principle），我們無法在每個桶只放一個物品的情況下將 6 個物品放入 5 個桶中，最終的哈希碼仍然會重複出現。因為我們的存儲量是有限的，所以我們不得不使用哈希值來對數組的大小取模，因此我們總會遇到衝突。

我們馬上會討論處理這些不可避免的衝突時所採用的常用策略，但首先應該注意的是，哈希函數的選擇可以增加或減少衝突的幾率。想像一下，我們總共有 16 個存儲位置，且必須從如下兩個函數中選擇一個作為哈希函數：

function hash_a(key) { return (13 * key) % 16;}function hash_b(key){ return (4 * key) % 16;}

在這種情況下，如果我們要對數字 0-32 進行哈希，hash_b 會產生 28 個衝突或重疊。7 個衝突分別產生於哈希值 0、4、8 和 12（前四個插入不發生衝突，但是後面的每個插入都會發生衝突）。然而，hash_a 會平均分散衝突，每個索引衝突 1 次，總共碰撞 16 次。這是因為在 hash_b 中，4 是哈希表大小 16 的一個因子，因為我們在 hash_a 中選擇了一個素數，除非我們的表大小是 13 的倍數，我們不會遇到選擇 hash_b 時的分組問題。

我們可以運行下面的腳本來觀察這一過程：

function hash_a(key) { return (13 * key) % 16;}function hash_b(key){ return (4 * key) % 16;}let table_a = Array(16).fill(0);let table_b = Array(16).fill(0);for(let i = 0; i < 32; i++) { let hash_code_a = hash_a(i); let hash_code_b = hash_b(i); table_a[hash_code_a] += 1; table_b[hash_code_b] += 1;}console.log(table_a); // [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]console.log(table_b); // [8,0,0,0,8,0,0,0,8,0,0,0,8,0,0,0]

好的哈希函數可以在表中更均勻地分布哈希碼間的衝突。

這種哈希策略，將輸入的鍵乘以素數是一種非常常見的做法。質數減少了輸出哈希碼與數組大小共有一個公因式的可能性，從而減少了碰撞發生的可能。由於哈希表已經存在了相當長的一段時間，因此有很多不同種類的優秀哈希函數可供選擇。

乘法移位哈希（Multiply-shift hashing）與 素數取模策略類似，但避免了相對昂貴的模運算，有利於快速進行移位操作。MurmurHash 和 Tabulation Hashing 是乘法移位哈希函數家族的強力替代品。對這些哈希函數進行的基準測試包括檢查它們的計算速度，生成的哈希碼的分布以及它們處理不同類型數據（例如除整數以外的字元串和浮點數）的靈活性。

如果我們選擇一個好的哈希函數，我們可以降低衝突率並且仍然保持較高的計算速度。不幸的是，無論我們選擇什麼哈希函數，衝突總是難以避免的，決定如何處理衝突將對我們哈希表的整體性能產生重大影響。碰撞處理的兩個常用策略是鏈接（Chaining）和線性探測（Linear Probing）。

鏈接簡單易用，我們不是在哈希表的每個索引處存儲每個條目，而是存儲鏈表的頭部指針。當一個條目通過我們的哈希函數與一個已經填充的索引相衝突時，我們將它添加為鏈表中的最後一個元素。查找不再是嚴格的「常數項時間」，因為我們必須遍歷鏈表來查找特定項目。如果我們的哈希函數存在很多衝突，我們將會有很長的鏈。此外，由於對於長鏈的查找，哈希表的性能會隨著時間的推移而降低。

線性探測在概念上很簡單，但實現起來還是很麻煩的。在線性探測中，我們仍然為每個元素在哈希表保留一個索引。當索引 i 發生衝突時，我們檢查索引 i + 1 是否為空，如果是，我們將數據存儲在那裡，如果 i + 1 也有一個元素，我們檢查 i + 2，然後 i + 3 等，直到找到一個空插槽。只要我們找到一個空插槽，我們就將該值插入。相似地，我們可能無法實現常數級時間複雜度的查找，並且如果在一個索引中遇到多個衝突，那麼我們最終將不得不搜索一系列長序列，然後才能找到要查找的條目。更重要的是，每當衝突發生時，後續發生衝突的幾率都會增加。因為與鏈接不同，每個傳入的項目最終會都佔據一個新的索引。

可能聽起來鏈接是更好的選擇，但線性探測往往被認為具有更好的性能特徵。大多數情況下，這是由於鏈表的緩存利用率較差以及使用數組有利於提高緩存利用率。簡答來說，檢查鏈表中的所有鏈接比檢查相同大小數組的所有索引要慢得多。這是因為每個數組中的索引在物理上相鄰，而在鏈表中，每個新節點在創建時都會被賦予一個位置。這個新節點不一定與鏈表中的相鄰節點在物理上相鄰。其結果是，在鏈表中，列表順序中「彼此相鄰」的節點在 RAM 晶元內的物理位置上並不實際相鄰。由於 CPU 高速緩存的工作原理，訪問相鄰內存位置的速度很快，而隨機訪問內存位置的速度則要慢得多。

機器學習基礎

為了理解機器學習是如何重建哈希表（和其他索引）的關鍵特徵的，有必要快速重新審視一下統計模型的主要思想。在統計學中，模型是可以接受一些向量為輸入並返回標籤（分類模型）或數據值（回歸模型）的函數。輸入向量包含所有數據點的相關信息，輸出的標籤或數據是模型的預測值。

在預測高校學生能否進入哈佛學習的模型中，輸入向量可能包含學生的 GPA、SAT 成績、參加的課外俱樂部的數量以及其他與學術成就相關的值；輸出的標籤可以是 True 或 False（可以進入哈佛或不可以進入哈佛）。

在預測抵押貸款違約率的模型中，輸入向量可能包含信用值、信用卡賬戶數量、逾期付款頻率、年收入以及與申請抵押人財務狀況相關的其他值，該模型會返回一個 0 到 1 範圍內的數字代表違約的可能性。

一般而言，可以用機器學習建立統計學模型。機器學習從業者將大量數據和機器學習演算法相結合，在數據集上運行演算法得到的結果是訓練好的模型。機器學習的核心在於創造可以自動從原始數據中建立準確模型的演算法，該演算法無需人工幫助機器「理解」這些數據實際上表示什麼。這與其他形式的人工智慧，如人類廣泛考察數據、告訴計算機這些數據的意義（如定義啟發式）以及定義計算機如何使用這些數據（如使用極小極大演算法或 A* 尋路演算法）是不同的。儘管在實踐中，機器學習常常和經典的非學習技術相結合；AI 智能體一般會同時使用學習和非學習策略以完成目標。

以著名的 AI 象棋棋手「深藍」和最近廣受關注的 AI 圍棋棋手「AlphaGo」為例。深藍是完全的非學習 AI；程序員和象棋專家合作為深藍創建了一個函數，該函數以棋局狀態為輸入（所有棋子的位置以及棋手的回合），返回的值與該位置有多「好」相關。深藍從不「學習」任何東西——人類棋手編寫了機器的評估函數。深藍的主要特徵是樹搜索演算法，該演算法計算了所有可能的落子處、以及對手對這些落子方法可能做出的回應以及未來可能會產生的移動。

AlphaGo 執行的也是樹搜索。與深藍的相似之處在於，AlphaGo 預測了可能的每一步之後的好幾步，而不同點在於 AlphaGo 在沒有圍棋專家明確指導的情況下建立了其自己的評估函數。在這種情況中，評估函數是一個訓練好的模型。AlphaGo 的機器學習演算法將棋盤狀態（每一個位置是黑子、白子還是沒有棋子）作為輸入向量，標籤表示了哪一方的棋手（白棋或黑棋）會贏。使用這些信息，機器學習演算法在數十萬種遊戲中都可以確定該如何評估當前狀態。AlphaGo 通過觀察數以百萬的例子教會自己在哪落子贏得遊戲的可能性更高。

將模型作為索引，背離 ML 範式

谷歌的研究人員首先在他們的文章中提出索引是模型的前提，或者說至少可以將機器學習模型當索引用。理由是：模型是接受一些輸入，然後返回一個標籤的機器；如果輸入是關鍵詞，而標籤是模型對內存地址的判斷，模型就可以當索引用。儘管聽起來很清晰明了，但是索引的問題似乎不能完美契合於機器學習。在一些領域中，谷歌團隊已經離開了機器學習範式以實現他們自己的目標。

一般情況下，機器學習模型是在已知數據上訓練，目標是評估沒見到的數據。若我們對數據進行索引，就沒法接受評估值。索引唯一的用處在於得到內存中一些數據的確切定位。一個箱子外的神經網路（或其他機器學習器）無法精確到這種程度。谷歌通過在訓練過程中追蹤最大（正）和最小（負）誤差以解決這個問題。將這些值作為邊界，ML 索引可以在界限內進行搜索，找到元素的確切位置。

另一個出發點是機器學習從業者一般都要小心避免他們的模型對訓練數據「過擬合」；一個「過擬合」模型會在訓練數據上產生很高的預測準確率，但在訓練集以外的數據上表現得很糟糕。另一方面，從定義上講，索引是過度擬合的。訓練集是被索引過的數據，這也使其成為測試集。由於查找必須發生在索引的實際數據上，在這種機器學習的應用上更容易遇到過擬合的問題。同時，如果模型已經對現有數據過擬合了，再向索引添加項目可能會在預測時造成可怕的錯誤；正如文章中所述：

「在這個模型的普遍性和『最後一英里』的表現間發生了有趣的取捨；可以這麼說，『最後一英里』的預測結果越好，模型的過擬合就越嚴重，就越不適用於新的數據項目。」

最後，一般而言，模型的訓練過程是整個過程中最昂貴的部分。不幸的是，在廣泛的資料庫應用程序（和其他索引應用程序）中，將數據添加到索引中是很常見的。該團隊坦言這方面的限制：

「迄今為止，我們的結果都將注意力集中在只讀存儲區資料庫系統的索引結構上。正如我們已經指出的那樣，目前的設計，即使沒有任何重大的修改，也已經可以替換現在的資料庫中的索引結構了——前者的索引結構可能每天只更新一次，而後者則需要在合併 SSTable 的過程中批量創建 B-樹。」——（SSTable 是谷歌的「BigTable」的重要元件）

學習哈希

本文研究了使用機器學習模型代替標準哈希函數的可能性。研究人員們想要了解的問題之一是：了解數據的分布可以幫助我們更好地創建索引嗎？用我們之前討論過的傳統的策略（移位乘法、Murmur Hash、素數乘法……），完全忽略了數據的分布。每一個傳入的項目都被視為獨立的值，而非作為具有數值屬性的較大數據集的一部分考慮的。結果是，即使在很多先進的哈希表中，也存在大量空間浪費的問題。

實現哈希表的內存利用率只有約 50%，這意味著哈希表佔用了數據存儲實際所需空間的兩倍。也就是說，當我們存儲與數組中存儲數量一樣多的項時，有一半的地址是空的。用機器學習模型替換標準哈希表中的哈希函數，研究人員發現浪費的空間顯著減少了。

這並非特別令人意外的結果：通過在輸入數據上進行訓練，學習到的哈希函數可以在一些空間更均勻地分布數值，因為 ML 模型已經知道了數據的分布！這是一種強有力的、可以顯著減少基於哈希的索引所需存儲量的方式。相應的也有一些限制：ML 模型比我們上面所述的標準哈希函數計算得要慢一些，而且需要訓練，但標準哈希函數不需要。

也許可以將基於哈希函數的 ML 用於關鍵在於有效的內存使用的情況，但是在這些情況中計算能力不再是瓶頸。谷歌和麻省理工的研究團隊認為資料庫就是一個很好的例子，因為索引在很昂貴的過程中每天重建一次；使用更多的計算時間以達到顯著的節省內存的目的，這對許多資料庫環境而言都是一場勝利。

但在此還是要有一個超展開，接下來進入布谷鳥哈希。

布谷鳥哈希（Cuckoo Hashing）

布谷鳥哈希發明於 2001 年，以布谷鳥類的名字命名。布谷鳥哈希是用鏈接技術和線性探測處理哈希衝突的替代（而非哈希函數的替代）。該策略一如其名，因為某些布谷鳥種類中，準備產卵的雌鳥會找到一個有主的巢，並將巢里的蛋挪出去，然後把自己的蛋下在裡面。在布谷鳥哈希中，傳入的數據會竊取舊數據的地址，就像布谷鳥會竊取別的鳥類的巢一樣。

工作原理如下：當創建哈希表時將表分為兩個空間，將這兩個空間分別稱為主地址空間和次地址空間。之後，分別初始化兩個哈希函數，每一個函數分配給一個地址空間。這些哈希函數有可能非常相似——例如它們可能都屬於「素數乘法」，其中每個哈希函數都會使用不同的素數。將這兩個函數稱為主哈希函數和次哈希函數。

最初，插入布谷鳥哈希只會利用主哈希函數和主地址空間。當哈希衝突發生時，新數據會驅逐舊數據，然後用次哈希函數對舊數據進行哈希，並將其放入次地址空間中。

如果該次要地址已經被佔用，則會再一次進行驅逐，在次要空間的數據會被發送回主要地址空間。因為有可能造成無限循環的驅逐，一般而言會設置一個每次插入驅逐的閾值；如果驅逐次數到達閾值，就會重建哈希表，重建過程可能包括為該表分配更多空間或是選擇新的哈希函數。

眾所周知，這種策略在內存受限的情況下是非常有效的。所謂「二次冪（power of two choices）」就允許布谷鳥哈希即便在高利用率的情況下也有很穩定的表現（這在鏈接技術或線性探索中是不會出現的）。

Bails 和他在斯坦福的研究團隊發現，只要進行適當優化，布谷鳥哈希可以非常快，即使在利用率高達 99% 的情況下，也能有不錯的表現（http://dawn.cs.stanford.edu/2018/01/11/index-baselines/）。從本質上講，布谷鳥哈希通過利用二次冪可以在無需昂貴訓練階段的情況下實現「機器學習」的高度利用。

索引的下一步是什麼？

最終，每個人都對學習索引結構的潛力感到興奮。隨著更多 ML 工具的廣泛應用，以及像 TPU 這樣硬體的進步使得機器學習工作負載更快，索引可以從機器學習策略中受益良多。與此同時，像布谷鳥哈希（cuckoo hashing）這樣漂亮的演算法提醒我們，機器學習並不是萬能的。融合了具有令人難以置信的力量的機器學習技術和像「二次冪」這樣的舊理論的工作將繼續推動計算機效率和能力的界限。

看起來，索引的基本原理不會一夜之間就被機器學習策略替代，但是自微調索引的想法是強大而令人興奮的概念。隨著我們越來越善用機器學習，以及在提升計算機處理機器學習工作負載的效率上做出的不斷的努力，利用這些優勢的新想法肯定會找到其主流用途。下一代 DynamoDB 或 Cassandra 可能也會很好地利用機器學習策略；日後 PostgreSQL 或 MySQL 的應用也會採用這樣的策略。最終，這都取決於未來研究所能取得的成就，這些成就會繼續建立在最先進的非線性策略和「AI 革命」的尖端技術上。

出於必要性的考慮，本文簡化了許多細節。想要了解更多細節的讀者請參閱：

• The Case For Learned Indexes (Google/MIT) (https://www.arxiv-vanity.com/papers/1712.01208/)
• Dont Throw Out Your Algorithms Book Just Yet: Classical Data Structures That Can Outperform Learned Indexes (Stanford) (http://dawn.cs.stanford.edu/2018/01/11/index-baselines/)
• A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing (https://bigdata.uni-saarland.de/publications/p249-richter.pdf) (Saarland University)

原文鏈接：https://blog.bradfieldcs.com/an-introduction-to-hashing-in-the-era-of-machine-learning-6039394549b0

推薦閱讀：