最近在做行情接收和處理相關的工作，其中一個關鍵步驟是根據行情數據的issue code欄位判斷該數據是否是我們需要的，如果不需要則直接丟棄。issue code是一個定長字元串，這就涉及到了查找字元串的問題，一般來說直接用一個通用的哈希表就好了，比如std::unordered_map。不過從實際數據中我發現issue code欄位存在一些pattern：有些位置的字元是固定不變的，有些會在小範圍內變動，有些會在較大範圍內變動，於是我想如果只根據少數幾個variance較大位置的字元算hash值能否更快呢？也就是使得哈希表能根據表中現有的key自動調整hash演算法

，做到既能快速算出hash值，又讓這些值能較為均勻的分布在表中，以達到快速查找的目的。

最終我把想法實現了出來，發現效果還不錯，並放到了github上：https://github.com/MengRao/str。這個項目里有兩個頭文件：Str.h和StrHash.h，前者是一個char數組的簡單封裝，提供了高效的字元串比較函數；後者就是這個自適應哈希表的實現：StrHash。

實際上StrHash是std::map的子類，所以用戶可以直接使用std::map的介面對哈希表進行增刪改，但在查表前需要調用一次doneModify函數以生成合適的hash參數，接下來就可以通過fastFind函數進行高速查找了。

Benchmark顯示StrHash的查找方法比std::unordered_map快7倍，比其他open addressing哈希表的實現（如tsl::hopscotch_map和tsl::robin_map)快3倍。至此，StrHash是我所知最快的定長字元串查找解決方案，如果你知道更快的請告訴我。

推薦閱讀：

相关文章