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 》， 譯者：虎說八道，審校：袁虎。 文章為簡譯，更為詳細的内容，請檢視 原文