設計高效能的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，請通知我一下好讓我標記原作者。