多階Hash算法

在分布式系統中，會經常用到K-V存儲，一般實現的方式有紅黑樹或者哈希表，在Redis中還用到了跳表。都是通過一個確定的Key值，來查找Key附帶的Value屬性。本文會介紹一種高效的算法——多階Hash。

1原理

多階Hash的實現原理很簡單，每個Hash桶數組算作一階，如果有20階的多階Hash，那麼就是一個二維數組，第一維是Hash桶的編號，第二維是每個Hash桶的每個槽的位置。實際開發中，可以申請一塊連續的內存，由一維數組構造出二維數組。內存構造如下圖所示，邏輯上是一個階梯狀，實際申請內存，是一塊連續的內存結構，用每次層的階數來標識出不同階的分界。如下圖所示：

通常每階的槽的個數都是質數個，每階的槽的個數依次遞減。由於互質的特性，通常情況下會上面的階數先被填滿，然後再逐步填下面的階數。在實際使用中，內存使用率可以達到90%以上。

查找和修改的時間複雜度都是 O(h) ，h是階數。

與教科書中的開鏈Hash對比，優缺點如下：

2優點

1、查找時間穩定

查找時間和階數成正比，雖然不一定最高效，但是是可控的，最壞要多少次查找是能夠控制的。如果是接鍊表解決衝突，衝突太多就退化成鍊表操作，耗時不可控。

2、實現簡單

實現完全是數組操作，而且存儲內容都是定長。與樹形數據結構相比，實現簡單很多。

3、方便序列化

由於底層是連續內存，能夠通過內存疊代遍歷全部元素，dump到外部文件。再通過dump文件重新插入實現恢複數據。

4、魯棒性強

網際網路業務大都是常駐進程，如果進程重啟會導致棧或堆中的內存銷毀。可以通過共享內存來達到重啟後恢復內存數據。由於多階Hash底層是數組結構，只需要知道起始位置和元素下標，就能夠對內存元素進行操作。進程重啟後重新掛載內存即可恢復操作，不需要重建索引。

3缺點

1、容量有限

由於階數有限，如果最後一階填滿後，會導致Key值沒有地方存儲。不如鍊表的擴展性好。

在實際項目，要做好容量管理和監控。當發現使用率超過70%的時候，就要準備擴容，防止寫滿。

2、存儲定長

存儲的部分是二維數組的Hash桶的塊，是一塊定長的內存。如果存儲的數據是變長的，就需要把內存塊定義為最大Value的長度，會造成內存浪費。常見優化方法是在Hash塊中存儲一個索引，索引指向另外一塊內存鍊表，變長數據被分別存儲在多個內存鍊表中。一般設置每塊內存鍊表的長度也需要計算。

多階Hash適用於讀多寫少的網際網路業務場景，通常是一個進程負責寫操作，多個進程負責讀操作。多個進程來提高整體的讀的並發量，來彌補每次查找都需要 O(h) 的複雜度。

多階Hash是一種在生產實踐中總結的算法，從學術上看它並不完美。因為會出現元素存不下的情況，而且時間複雜度的常數係數比較大。但是在網際網路讀多寫少的業務場景中，讀速度可控，容量管理能監控，這些問題都能夠被解決。同時還帶來容易實現，魯棒性強，內存使用率高的優點。

在實踐中得到的這個算法，雖然不是十分優美，但是真的十分實用。