設計高效能的Hash Table(二)

這是Hash Table系列文章第二篇。其實這篇我想講的內容原本預計是寫再上一篇的,但上一篇稍微介紹一點背景知識篇幅就變得有點長了。相較起上篇的概論,這篇我會專注於探討演算法的部分;預計下一篇則是寫實作時如何在記憶體排列上增進最後數趴的效能。順帶一提我在上篇中補充了幾個Hash Function的連結,有興趣的使用者可以回上一篇看。

我這次實作的Hash Table核心演算法,是Robin Hood Hashing。會知道這演算法是因為在Hacker News上看到一篇很騷包的文章 I wrote the fastest hash table 。可惜的是他的實作目標是以POC為主,hash function的選擇也很陽春。但正是因為看到了那篇文章,我才有機會深入研究Hash Table的各種眉角,以及設計出一些別出心裁的演算法。


Robin Hood Hashing是上篇提到 Open Addressing Hash Table 的其中一種。在介紹Robin Hood Hashing的細節前,讓我把 Open Addressing稍微複習一遍:Open Addressing 是當兩個鍵映到同一個槽時,不用 linked list ,而是其中一個鍵要找另一個槽來用。找另一個槽的動作,在 Open Addressing 術語中叫做 probe (渣翻:探查)。直接找隔壁的位子叫做 Linear Probing,但它在處理衝突時很容易擠在一塊。稍微複雜一點的作法是採用probe的平方值來探查下個槽,稱做Quadratic Probing。Quadratic Probing是當前最流行的探查選擇,因為它可以兼顧快取優化以及處理衝突。我在撰寫Hash Table時還實驗了一個暫名為Rotate Probing的方法,它能給我相當好的隨機性,但由於沒有優化快取所以效能不如Quadratic Probing。

Linear Probing (key, probe) = hash(key) + probe
Quadratic Probing (key, probe) = hash(key) + probe²
Rotate Probing (key, probe) = RotateRight(hash(key), probe)

雖然這些探查的技巧可以對付鍵值衝突,但它卻無法解決「貧富不均」的問題。先插入Hash Table者有如先買房子的人,後到者只能換找下個位子;越是後面其探查數量就急遽增高,因為碰到位子先有人佔的機率會愈來愈高。大部分的Hash Table應付此問題的方法是「讓Hash Table不要太滿」。例如google dense hash map 預設的滿度是 25%-50%。但這樣,嗯,真的蠻浪費記憶體空間的。

Robin Hood Hashing 就是為了要解決這個「貧富不均」的問題。探查次數愈少者愈「富」,碰到鍵值衝突時,不是後到者換位子,而是探查次數比較少的那個鍵得換位子。因為這劫富濟貧的邏輯,所以命名為 Robin Hood Hashing。

至於搜尋的方法就跟一般 Linear/Quadratic Probing的方法一樣,先找到鍵對映的槽,然後一路找到紀錄中最長的探查數為止。若超過紀錄中的探查數,則代表查無資料。

這樣的演算法實在是說不上複雜,但很意外的沈睡了三十年還沒有人把它實作成廣泛通用的函示庫…。不過連 std::unordered_map 也是很晚近才加入 C++ STL的,所以還是別太苛求好了。Robin Hood Hashing 那篇論文後面花很多力氣證明探查的數目會收斂,而實際實驗時也符合它的預測。可惜的是刪除資料就無法讓探查的數目收斂了。我設計了一套刪除演算法能讓探查量很緩慢的成長,但就是無法收斂。細節以後有機會再說明。


如果單單實作上述的演算法,不一定能比 dense_hash_map 還快。最大的瓶頸是 Hash Table Size 對 hash function 效能的影響。一般做完 hash 之後,我們需要取補數 (mod) 以映射到 hash table 的槽中。如果使用一般整數的補數,在 x86 系統上需要花 28~90 個 cpu cycle。特例是二的次方,只需一個 mask 就能做完。寫成C的話: hashed_key & ((1UL << n)-1), 約 3 cycles (或更少,因為cpu有pipelining)。也因此幾乎所有的 Hash Table實作都只用二的次方來當作其大小。可是在資料量很大時,最糟情況是一半的記憶體閒置。例如資料4GB,卻佔用了8GB的記憶體,實在是相當的不理想。

有沒有可能兼顧兩邊的好處,找出某些特別的 Hash Table 大小,使得補數計算很快,但大小成長速度不像二的次方這麼劇烈?我很幸運的想出了一個解決方案,命名為 Fast mod and scale ,「取補數再壓縮」。

首先,算出約略的 Hash Table Size ,然後丟掉下面的位元,只取其最上面四個位元作為 Hash Table的大小。只看最上面的位元,它的值就只能是 8, 9, 10, 11, 12, 13, 14, 15。也就是說,Table大小只能是 8 * 2^k, 9 * 2^k, etc.。計算補數時,以最大的位元的更大一個位元作為取補數的基準。由於是最上一個位元的大一號位元,對映起最上四個位元他們的大小差異就會是 8/16, 9/16,…,15/16,因此只需要乘上這份差異即可。寫成公式的話:

ms4b = most significant 4 bits = 8, 9, …, 15
TableSize(ms4b, k) = ms4b * 2^k = ms4b << k;
ModAndScale(hashed_key, ms4b, k) = (hashed_key % 2^(k+4)) * ms4b / 16
= (hashed_key & ((1 << k+4)-1)) * ms4b >> 4;

由於整數乘法在x86上只需要 3 cycle,因此速度遠比算mod快上許多。唯一的缺點是hashed_key最下面的位元經過scale可能會消失。因為最後一步等同擠壓至多到1/2倍的程度。如果照前面寫的 Linear/Quadratic Probing 的公式來寫,有很高的機率是探查了卻原地踏步。探查的公式改成 hash(key) + probe*2, 以及 hash(key) + probe² * 2 就能解決壓縮失去資訊的問題。

取補數再壓縮,雖然說概念很簡單,但我卻沒找到其他類似的作法。如果有人找到相關的Reference,請通知我一下好讓我標記原作者。