設計高效能的Hash Table（一）
好久沒有寫部落格文章了。我今天打算分享自己這三個禮拜在Hash Table上做的一些小實驗以及研究成果。很幸運的我居然可以做出相當好的Hash Table，在許多情境下比第二名好上非常多。這年頭能在非常基本的資料結構上超越前代的巨人真的是無比幸運。這篇文章我只會講大方向，詳細的數據等我整合了更多的benchmark後再發佈。
Hash Table大概是所有資料結構中應用最廣泛的，沒有之一；它同時也是常見的面試問題之一。Hash Table主要可以分作兩大類：Separate Chaining以及Open Addressing。Separate Chaining是一般課堂上會提到的實作：Hash到array之後，如果多個key被映射到同個位置，就使用Linked List來裝衝突的資料。Open Addressing處理衝突時，則是將其中一個key放到別的位置去。根據放的邏輯又分成兩大流派：linear probing及quadratic probing兩種。許多較快的Hash Table會採用Open Addressing這種實作，因為Linked List的指標會對記憶體快取不友善。稍後我們會看到影響效能的關鍵大都與CPU快取有關。
在探討Hash Table資料結構細節的面貌前，我們先來看Hash Function，以及其相關的數學。在我實作Hash Table前，Hash Function對我來說一直是電腦科學中特別神秘的存在。因為大多數的Hash Function裡面都有magic numbers。即使是比較簡單的版本：(v * 2654435761ULL) >> 32在我看來也是像天書一樣。不過這是有道理可循的。
在講解Hash Function的magic number前，先講一下CPU計算的背景知識。CPU做加減乘法很快，但是做除法非常慢。加、減、左右移 (shift)、rotate等都是 1 cycle。乘法稍微多一點，約 3 cycles，至於除法在64 bit整數上要花28–90 cycles！如果在Hash Function當中誤用了除法，那你的比較基準直接輸人數十倍甚至到百倍。那些看起來怪異的magic number就是為了解決除法而發明出來的捷徑。關於CPU可參閱CPU指令的速度的數據。
Magic number說穿了就是Fixed point arithmetic。這篇文章有蠻詳細的說明。例如，你可以把0.1約略寫成二進位的0x1999，小數點位在最右起向左算16個位元的位置。拿0x1999乘上任意的數字，再右移16位，就約等於除十的效果。使用這種方式只需要 4 cycles 就能達到「模擬」的除法。對於要求速度甚於準確度的Hash Function來說，是相當常見的一種技巧。以後看到別人的程式中有magic number，只要把之後右移的bit帶入，並且重寫成二進位模式，就可以知道它是用來當作什麼樣的除數。
說來慚愧，我對Hash Function的研究非常少。剩下的就是找一些現成的有名Hash Function實作來比較速度。榜上有名的實作有Murmurhash3, cityhash, XXHash, siphash, highwayhash等等。我最後選用的是Murmurhash3。我蒐集了以下數種值得參考的Hash Function實作：
- Murmurhash3 Murmurhash2是已經被大量使用的Hash function實作。Murmurhash3是其改進版。我選用這種因為它是public domain，一個檔案就搞定，沒有麻煩的套件相依或系統相依性問題。
- Siphash/highwayhash 這是一個針對長度短的資料進行最佳化的hash function。據作者說還能有效的避免惡意造成的DDOS。它的進化型highwayhash使用AVX2的指令集來加速，相當有意思。
- XXHash 比Murmurhash2/3都還要快的個人實作。是我未來要對hash function做最佳化時的熱門候選人。Facebook RocksDB中有使用到XXHash。
- CityHash 出自Google的另一個快速Hash Function
- FarmHash 同樣出自Google的Hash Function，是CityHash的進化版。針對不同平台使用不同的指令集優化。
Hash function除了比較速度外，還有幾個重要的特性可以評量。
- Universality: For all x, y in key space, Pr{h(x) = h(y)} ≤ 1/m。m是hash table size。以白話文來說，就是任意兩個鍵衝突的機率小於1/m。
- K-wise independence: Pr{h(x_1) = y_1 && h(x_2) = y_2 && … h(x_k) = y_k} = 1/m^k。也就是K個鍵經過hash function映射後都對彼此獨立。這是比Universality還要強得多的性質，可惜的是現有快速Hash function都沒有經過K-wise independence的分析；而經過K-wise independence分析過的Hash function又太過複雜笨重不適合拿出來用。
- Minimal Perfect Hashing: 將N個鍵映射到M個整數且不產生衝突，如果N=M，我們稱之為最小完美Hash。
對以上主題有興趣，可參閱MIT Advanced Data Structure課程。我下篇文章會寫課程中沒有涵蓋到的一些演算法。
