設計高效能的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除了比較速度外,還有幾個重要的特性可以評量。

  1. Universality: For all x, y in key space, Pr{h(x) = h(y)} ≤ 1/m。m是hash table size。以白話文來說,就是任意兩個鍵衝突的機率小於1/m。
  2. 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又太過複雜笨重不適合拿出來用。
  3. Minimal Perfect Hashing: 將N個鍵映射到M個整數且不產生衝突,如果N=M,我們稱之為最小完美Hash。

對以上主題有興趣,可參閱MIT Advanced Data Structure課程。我下篇文章會寫課程中沒有涵蓋到的一些演算法。

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.