淺談機器學習時代的哈希演算法（一）

來自專欄 我是程序員

摘要：來，咱們聊聊機器學習時代的哈希演算法～

2017年12月，谷歌和麻省理工學院的研究人員發表了一篇關於他們在「學習型指數結構」中的研究報告。這些研究非常令人興奮，正如作者在摘要中所述：

「我們相信，通過學習模型取代數據管理系統核心組件的想法對未來的系統設計有著深遠的影響，而且這項工作只是提供了可能的一瞥。」

事實上，谷歌和麻省理工學院研究人員提出的研究成果包括表明索引世界中的中堅力量新競爭的結果：B-樹和哈希圖。工程界對機器學習的未來感到不安，因此這篇研究論文已經在Hacker News、Reddit和工程界中進行了深入的探討。

新的研究是重新審視一個領域基礎的絕佳機會，而且作為索引的根本東西往往不是經常性的突破。本文作為哈希表的簡介，簡要介紹了什麼使得它們變得快慢的原因，以及直觀的機器學習概念，同時這些概念是如何應用於索引中的。

（如果你已經熟悉哈希表、碰撞處理策略和哈希函數性能考慮因素；你可以跳過本文閱讀第二部分，以深入了解這些內容主題。）

為了回應谷歌/麻省理工學院合作的結果，Peter Bailis和一個斯坦福研究小組回顧了基礎知識，並警告我們不要扔掉我們的演算法書。Bailis和他所在斯坦福大學的團隊重新創建了學習型索引策略，並且通過使用名為Cuckoo Hashing的經典哈希表策略，能夠在沒有任何機器學習的情況下獲得類似結果。

在回應谷歌/麻省理工學院的研究中，托馬斯·紐曼描述了另一種類似於學習指標策略的性能的方式，而不放棄經過良好測試並且很好理解的B樹。這也是谷歌/麻省理工學院團隊激動不已的原因，在他們寫的論文中：

「重要的是，我們不主張用學習的索引結構來完全取代傳統的索引結構。相反，我們創建了一種建立索引的新方法，它補充了現有的工作，並且可以說為未來幾十年的領域開闢了一個全新的研究方向。」

那麼散列圖和B-tree是否註定要成為老齡化的演算法？計算機是否會重寫演算法教科書？如果機器學習策略真的比我們所知道和喜愛的通用索引更好，那麼它對計算機世界意味著什麼呢？學習指數在什麼情況下會超越舊的備用指數？

為了解決這些問題，我們需要了解索引是什麼，他們解決了什麼問題。

什麼是索引？

索引的核心是讓事物更容易找到。早在計算機發明之前，人類就一直在索引事物。當我們使用組織良好的文件櫃時，我們使用的就是索引系統；全卷百科全書也可被視為一種索引策略；雜貨店裡的標籤過道是一種索引。任何時候我們都有很多東西，我們需要在集合中找到或識別特定的東西，索引可以用來使事情變得更容易。

亞歷山德里亞大圖書館的第一個圖書管理員Zenodotus負責組織圖書館的龐大的收藏。他設計的系統包括按照流派將書籍分組入房間，並按字母順序擱置書本。他的同行Callimachus更先進，引入了一個名為pinakes的中央目錄，它允許圖書管理員查找作者，並確定該作者的每本書在圖書館中的位置。（你可以在這裡閱讀更多關於古代圖書館的信息）。自從1876年發明了杜威十進位系統以來，圖書館索引中創造了很多的創新成果。

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

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

資料庫是索引編製的典型用例。資料庫旨在保存大量信息，並且一般而言，我們希望高效地檢索這些信息。搜索引擎的核心是建立互聯網上可用信息的巨大索引。哈希表、二叉查找樹、森林，B樹和bloom filters都是索引的形式。

很容易想像在亞歷山大這樣大型圖書館的大廳里找到具體的東西的挑戰，而且事實是人類生成的數據的規模正在呈指數級增長。互聯網上可用的數據量遠遠超過任何時代的任何單個圖書館的數量，Google的目標是將所有數據都編入索引。人類為索引創造了許多策略；在這裡，我們研究最多產的數據結構，這恰好是一個索引結構：散列表。

什麼是散列表？

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

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

在構建哈希表時，我們首先為哈希表分配一些空間（在內存或存儲空間中），你可以想像創建一個任意大小的新數組。如果我們有很多數據，我們可能會使用更大的數組；如果我們有更少的數據，我們可以使用更小的數組。任何時候我們想索引一個單獨的數據片段，我們都會創建一個鍵/值對，其中的關鍵字是關於數據的一些標識信息（例如資料庫記錄的主鍵），值是數據本身（整體資料庫記錄）。

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

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

從根本上說，這個簡單的過程全是哈希表。然而，為了確保基於哈希的索引的正確性和效率，在這個簡單的思想的基礎上構建了大量的複雜性。

基於哈希的索引的性能考慮

散列表中複雜性和優化的主要來源是散列衝突問題。當兩個或更多個密鑰產生相同的散列碼時會發生衝突。考慮這個簡單的哈希函數，其中密鑰被假定為一個整數：

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

一個簡單的散列函數

雖然任何唯一的整數在乘以13時都會產生唯一的結果，但由於鴿巢原理，最終得到的哈希碼仍然會重複。鴿巢原理：如果n個物品放入m個容器中，n>m，則至少一個容器必須包含多個物品。

暫時我們將討論處理這些不可避免的碰撞的流行策略，但首先應該注意的是，散列函數的選擇可以增加或減少碰撞的速率。想像一下，我們總共有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會平均分散碰撞，每個索引碰撞一次，總共碰撞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]

更好的散列函數能夠避免衝突。

這種哈希策略，將輸入密鑰乘以素數，實際上是相當常見的。質數減少了輸出哈希碼與數組大小共有一個公因式的可能性，從而減少了碰撞的可能性。由於哈希表已經存在了相當長的一段時間，因此有很多其他競爭性哈希函數可供選擇。

多次移位散列與初始模數策略類似，但是避免了相對昂貴的取模操作，以支持非常快速的移位操作。MurmurHash和Tabulation Hashing是散列函數的多位移系列的強有力替代品。對這些散列函數進行基準測試包括檢查它們的計算速度，生成的散列代碼的分布以及它們處理不同類型數據（例如除整數以外的字元串和浮點數）的靈活性。有關哈希函數的基準測試套件的示例，請查看SMhasher。

如果我們選擇一個好的散列函數，我們可以降低我們的衝突率並且仍然快速計算散列碼。不幸的是，無論我們選擇什麼散列函數，最終我們都會碰撞。決定如何處理衝突將是對我們的哈希表的整體性能產生重大影響。兩種常見的碰撞處理策略是鏈接和線性探測。

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

線性探測在概念上仍然很簡單，但實施起來很麻煩。在線性探測中，散列表中的每個索引仍保留為單個元素。當索引i發生碰撞時，我們檢查索引i + 1是否為空，如果是，我們將數據存儲在那裡；如果i + 1也有元素，我們檢查i + 2，然後i + 3等等，直到找到一個空插槽。只要我們找到一個空插槽，我們插入值。再一次，查找可能不再是嚴格不變的時間；如果我們在一個索引中存在多個碰撞，那麼在我們找到要找的項目之前，我們最終不得不搜索一系列長項目。更重要的是，每當我們發生碰撞時，我們都會增加後續碰撞的機會，因為（與鏈接不同）傳入的項目最終會佔據一個新的索引。

線性探測：給定與上面的鏈接圖像相同的數據和散列函數，我們得到一個新的結果。導致碰撞的元素（紅色）現在駐留在同一個數組中，並從碰撞索引開始按順序佔據索引。

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

數十款阿里雲產品限時折扣中，趕緊點擊領劵開始雲上實踐吧！

以上為譯文，由@阿里云云棲社區組織翻譯。

文章原標題《an-introduction-to-hashing-in-the-era-of-machine-learning》

譯者：虎說八道，審校：袁虎。

文章為簡譯，更為詳細的內容，請查看原文。

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎

本文為雲棲社區原創內容，未經允許不得轉載。