基礎優化-讓哈希表更公平一些

哈希表性能優化的方法有很多，比如：

• 使用雙 hash 檢索衝突
• 使用開放+封閉混合定址法組織哈希表
• 使用跳錶快速定位衝突
• 使用 LRU 緩存最近訪問過的鍵值，不管表內數據多大，短時內訪問的總是那麼幾個
• 使用更好的分配器來管理 key_value_pair 這個節點對象

上面只要隨便選兩條你都能得到一個比 unordered_map 快不少的哈希表，類似的方法還有很多，比如使用除以質數來歸一化哈希值（x86下性能最好，整數除法非常快，但非x86就不行了，arm還沒有整數除法指令，要靠軟體模擬，代價很大）。

哈希表最大的問題就是過分依賴哈希函數得到一個正態分布的哈希值，特別是開放定址法（內存更小，速度更快，但是更怕哈希衝突），一旦衝突多了，或者 load factor 上去了，性能就急劇下降。

Python 的哈希表就是開放定址的，速度是快了，但是面對哈希碰撞攻擊時，掛的也是最慘的，早先爆出的哈希碰撞漏洞，攻擊者可以通過哈希碰撞來計算成千上萬的鍵值，導致 Python / Php / Java / V8 等一大批語言寫成的服務完全癱瘓。

後續 Python 推出了修正版本，解決方案是增加一個哈希種子，用隨機數來初始化它，這都不徹底，開放定址法對hash函數的好壞仍然高度敏感，碰到特殊的數據，性能下降很厲害。

經過最近幾年的各種事件，讓人們不得不把目光從「如何實現個更快的哈希表」轉移到 「如何實現一個最不壞的哈希表」來，以這個新思路重新思考 hash 表的設計。

哈希表定位主要靠下面一個操作：

index_pos = hash(key) % index_size;n

來決定一個鍵值到底存儲在什麼地方，雖然 hash(key) 返回的數值在 0-0xffffffff 之前，但是索引表是有大小限制的，在 hash 值用 index_size 取模以後，大量不同哈希值取模後可能得到相同的索引位置，所以即使哈希值不一樣最終取模後還是會碰撞。

第一種思路是盡量避免衝突，比如雙哈希，比如讓索引大小 index_size 保持質數式增長，但是他們都太過依賴於哈希函數本身；所以第二種思路是把注意力放在碰撞發生了該怎麼處理上，比如多層哈希，開放+封閉混合定址法，跳錶，封閉定址+平衡二叉樹。

優化方向

今天我們就來實現一下最後一種，也是最徹底的做法：封閉定址+平衡二叉樹，看看最終性能如何？能否達到我們的要求？實現起來有哪些坑？其原理簡單說起來就是，將原來封閉定址的鏈表，改為平衡二叉樹：

傳統的封閉定址哈希表，也是 Linux / STL 等大部分哈希表的實現，碰到碰撞時鏈表一長就掛掉，所謂哈希表+平衡二叉樹就是：

將原來的鏈表（有序或者無序）換成平衡二叉樹，這是複雜度最高的做法，同時也是最可靠的做法。發生碰撞時能將時間複雜度由 O(N) 降低到 O(logN)，10個節點，鏈表的複雜度就是 10，而使用平衡二叉樹的複雜度是 3；100個節點前者的時間是100，後者只有6.6 越往後差距約明顯。

面臨問題

樹表混合結構（哈希表+平衡二叉樹）的方法，Hash table - Wikipedia 上面早有說明，之所以一直沒有進入各大語言/SDK的主流實現主要有四個問題：

1. 比起封閉定址（STL，Java）來講，節點少時，維持平衡（旋轉等）會比有序鏈表更慢。
2. 比起開放定址（python，v8實現）來講，內存不緊湊，緩存不夠友好。
3. 佔用更多內存：一個平衡二叉樹節點需要更多指針。
4. 設計比其他任何哈希表都要複雜。

所以雖然早就有人提出，但是一直都是一個邊緣方法，並未進入主流實現。而最近兩年隨著各大語言暴露出來的各種哈希碰撞攻擊，和原有設計基本無力應對壞一些的情況，於是又開始尋求這種樹表混合結構是否還有優化的空間。

先來解決第一個問題，如果二叉樹節點只有3-5個，那還不如使用有序鏈表，這是公認的事實，Java 8 最新實現的樹表混合結構里，引入了一個 TREEIFY_THRESHOLD = 8 的常量，同一個索引內（或者叫同一個桶/slot/bucket內），衝突鍵值小於 8 的，使用鏈表，大於這個閾值時當前 index 內所有節點進行樹化操作（treeify）。

Java 8 靠這個方法有效的解決了第一個問題和第三個問題，最終代替了原有 java4-7 一直在使用的 HashMap 老實現，那麼我們要使用 Java 8 的方法么？

不用，今天我們換種實現，java 8 經過了反覆測試選擇了 TREEIFY_THRESHOLD=8 這個閾值，因為它 treeify 的過程的代價是非常大的：

1. 要為每個節點重新分配一個 TreeNode ，分配內存過本身就是很大的一個開銷。
2. 構造二叉平衡樹，其維護平衡即便不需要再平衡，進去也是要走一堆邏輯判斷。
3. 當節點降低到 UNTREEIFY_THRESHOLD=6這個閾值以內，又要把樹節點全部刪除掉，換回鏈表去，那如果 index 內節點就在 5-9 之間波動，這就傻了，這是第三項成本。
4. 每次插入節點時要判斷這是鏈表還是樹，到閾值沒有，大家知道這些額外增加的分支都是對 CPU的流水線十分不友好的。

如果我們能想辦法不多分配內存（開銷最大），那基本上這個閾值可以降低到 4，再此基礎上使用更緊湊的搜索代碼，在 gcc 那裡可以獲得更好的優化，現代CPU對小型分支預測的處理都比較完善，x86下還有 cmov 指令解決跳轉，樹搜索時多用緊湊的三元式：

node = (key < node->key)? node->left : node->right;n

最終生成 cmov 的代碼是沒有分支的，實測新老 gcc，新版本 gcc 生成 cmov指令性能是沒有用 cmov 的一倍以上，諸如此類的代碼層的優化技巧我們盡量用起來，讓這個閾值降低到 2-3 的時候，也就是說傳統的有序鏈表操作已經沒有優化餘地了，但是通過降低 treeify 過程中再次分配內存的消耗，樹維護的消耗，以及提高樹的性能，可以把閾值從 8 降低到 4，再通過代碼層的優化降低到 2-3，也就是說，最終鏈表只有在 2-3個節點以內才比樹更快，如果做到這一點，那好，我們的故事就變了。

再鏈表/樹的性能對比閾值降低到 2-3個節點後，接下來我們就可以完全拋棄鏈表，index裡面只保留樹結構，然後給平衡二叉樹增加幾條 fast path，讓其性能盡量接近鏈表，比如大部分時候（hash值較為平均），每個 index只有 0-2個節點的時候，我們的這些快速路徑就生效了：

1. 當某 index 下面節點數為 0 時，要增加一個節點，我們直接更改樹的根節點即可，完全跳過後面的各種再平衡邏輯，以及比較邏輯。
2. 如果本來有 1 個節點，要增加一個新節點，那麼也完全不需要再平衡，一次比較後直接設置成左或者右兒子同樣跳過再平衡邏輯。
3. 如果是2個節點變3個節點，那同樣很簡單，把最大和最小節點找出來，放在剩下節點的左右子樹即可，同樣跳過再平衡。

這樣 3個節點以內我們採取一次性直接構造樹的方法免去再平衡邏輯，基本上保證了3個節點以內的樹操作和鏈表代價相同，又因為自始至終只有一種節點，避免了 java8 中同節點可能需要兩次內存分配的問題，又大大縮小了鏈表和樹的性能差距，只使用樹結構，免除了 treeify, untreeify 兩道邏輯和開頭的判斷，最終達到和鏈表性能差不多的樹結構。

指針優化

再看 TreeNode 內容，大家猜猜一個 java.util.HashMap.TreeNode 對象有多少個成員變數？不說不知道，一說嚇一跳，整整 9個變數（HashMap.Node 本身有4個對象，其派生類 HashMap.TreeNode 又增加了5個新變數）。還有每次分配一斷內存其實都有一個 overhead ，表明這個內存是從哪裡分配出來的，釋放的時候好找到歸還的位置，全部加在一起有 10個變數，變數越多緩存越不集中，每次操作的成本也越大，我沒研究過 java 的對象內存布局，就以 C語言為例 10個變數 32位下要佔用 40位元組的空間，64位下佔用更多。

其中關鍵的一處冗餘是 Java 8 下面為每個節點維護了 next, prev 指針，這兩個指針何用？遍歷哈希表的時候用。大家知道如果節點不維護 next, prev 而遍歷哈希表的話，傳統遍曆法要遍歷所有 index，即便一個 index 為空也要走一圈，python就是這麼乾的，那麼在 load factor 比較高的時候，這麼做沒問題；而 load factor 很低時，也就是說 index 表很大，但是整個 hash表裡的節點卻很少時，遍歷就會跑很多空的 index，效率很低。

所以 java8 里一個 treeify 過後的索引里，所有節點不當放在樹里，還同時放到了鏈表裡了，雖然搜索不搜索鏈表而是直接搜索樹，但是每次插入和刪除需要同時操作樹和鏈表，來保證遍歷的時候可以不跑空節點，這又是一件肯爹的事情。

那麼我們可以把 next, prev 省掉么？當然可以，既然我們已經全部都使用平衡二叉樹了，本身平衡二叉樹就可以方便的遍歷而不需要額外的存儲，只是這個 index 里的二叉樹遍歷完了怎麼尋找下一個有效節點？很簡單，我們把 next, prev 指針加到 index上，讓有數據的 index 連在一起，這個 index 內的所有樹節點遍歷完了後直接跳到下一個有數據的 index 里的節點上去。這樣我們把每個節點都有的 next/prev 拿了出來，放到了 index 上面，插入和刪除節點都不需要再同時維護樹和鏈表兩個結構，僅僅再節點數 0->1, 1->0時需要把 index 移進/移除鏈表，保證了遍歷時不會跑空的 index，同時為每個節點都省掉了兩個指針。

內存優化

開放定址的 hash 表的優勢是：省內存+不需要額外分配內存+緩存友好，使用樹表混合結構後，內存顯然我們是省不了多少了，但是後兩個目的卻可以想辦法達到，在哈希表內按照 load factor 和初始索引大小計算出 rehash 前最多會有多少個節點，然後一次性分配一整塊內存，按照 node 的大小切割後放入哈希表內部的 freelist 中，rehash的時候再重新計算分配另外一塊整塊內存，這樣做有三個明顯的好處：

1. 內存分配/釋放，基本是O(1)極速了，消耗基本可以忽略。
2. 表內所有節點再內存上都是連續的，緩存十分友好。
3. 免去了為每個節點單獨分配內存的頭部佔用（overhead），相當於又省掉了一個指針。

使用該方法進行內存優化過的樹表結構，性能得以再次提升。

其他優化

設計一個數據結構，本身就是再做選擇，做權衡，選擇了樹表混合結構，看重的是它的終極平衡特性，而上面所有工作，其實都是在死磕它的短處，各處可以優化的細節還很多：

比如 rehash 刪除原有二叉平衡樹時，不需要用標準 rbtree/avl 刪除一個節點每次再平衡的傳統方法，可以使用一種類似「摘葉子」的方法解構二叉樹，每次選擇最近的葉子節點刪除，沒有就往上回溯父節點，比標準方法老老實實刪除快很多。

比如傳統二叉樹的增刪改查都是要比較鍵值的，而比較鍵值是個很費時間的操作（比如用字元串做鍵值時），但是既然我們有哈希值，節點又是 unordered 的，那麼在操作二叉樹時，我們線比較哈希值，先用哈希值的大小進行比較，哈希值相同了再實際比較鍵值，這樣可以大大避免頻繁的鍵值比較，最終每個節點大部分只有1次鍵值比較，少部分有2次以上比較。

。。。。

基準測試

引入一個新技術再大部分情況下如果比老技術更慢就別玩了，不能光說不練嘛，我們測試一下上面說的這些方法最終效果如何。首先看看正常情況下，即 hash 值均勻分布的情況下它的表現，對比的是幾個主流編譯器自帶的 STL 里的 unordered_map，為了避免額外因素干擾，兩邊都用 int 值做主鍵，使用了相同的哈希函數：hash(x) = x，這也是大部分 STL 實現默認的 hash函數：

上面的 avl-hash 是我們上面實現的樹表混合結構，二叉平衡樹我用的是 AVL，這是個人習慣問題了，關於 avl / rbtree 的性能其實是差不多的，我以前討論過，這裡不展開了：

韋易笑：AVL樹，紅黑樹，B樹，B+樹，Trie樹都分別應用在哪些現實場景中？

你也可以用 rbtree 代替，這裡純粹一個個人口味問題，下面比較了 Windows / Linux 下面vc和 gcc 自帶的 std::unordered_map ，從查詢時間看，兩個差不多，avl-hash 略微領先一些，後面插入時間和刪除時間 std::unordered_map 很吃虧，因為我們的樹表混合結構里自己管理了節點內存分配，而 unordered_map 卻使用了默認內存分配器（會用系統默認的內存分配），所以排除內存分配開銷，二者差距應該沒上面那麼大，比如 ubuntu 下面 libc 內存分配器對於 128 位元組以內的對象分配直接使用 fastbin (一種freelist），性能比windows下的好很多，接近 avl-hash 內部自己管理內存的速度，因此性能差距會比 windows 小不少。

衝突測試

大部分哈希表都讓用戶 「選擇一個合適的哈希函數」，而什麼哈希函數才最合適？才分布最好？誰他媽都說不清，特別時對於未知鍵值到底會是怎樣的情況下，你完全沒根據去選擇一個「好」的哈希函數，比如你給 python 重新設計一遍字典，你能預知成千上萬用戶會用它存什麼嗎？比如你實現一個 redis / mq 之類的服務，你知道用戶會發送什麼鍵值上來？而這類服務，同一個哈希表裡 hold 住百萬級別的鍵值是很常見的事情。

未來鍵值不確定時，必須把希望寄托在一個「先驗」的好的 hash函數上么？不需要了，這回我們可以靠哈希表自己了。前面實現了那麼多，究竟我們實現的 「最不壞的哈希表」，不壞到什麼程度？當發生碰撞時，或者 load-factor 比較高的情況下，性能是否能達到預期？

激動人心的時刻終於到了，第一項，搜索測試：

可以看出搜索對比，橫軸表示衝突節點數量，縱軸表示測試耗時，可以看出隨著碰撞的增加，樹表混合結構的查詢時間基本只是從 0毫秒增加到了 1-2毫秒，而 unordered_map 的搜索時間卻是拋物線上升到1.4秒了。

插入和刪除耗時類似

刪除操作都比較費時，unordered_map 在三萬個節點時基本接近1.6秒，而我們的樹表混合結構耗時只有少許增加。

通過上面的工作，我們得到了這個最不壞的哈希表，我們用它做一個類似 redis / mq 的服務，存儲百萬級別的鍵值不用太過在意數據哈希值分布不均勻所帶來的問題了，也不用擔心碰撞攻擊會讓其性能跌落到深淵。

我們沒法完全依賴哈希函數，當哈希函數靠不住時，還得靠哈希表本身，這叫打鐵還需自身硬嘛，最終測試基本符合我們的初衷和預期。

（完）

好吧，大家要的代碼：

skywind3000/avlmini