最近在做行情接收和处理相关的工作，其中一个关键步骤是根据行情数据的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是我所知最快的定长字元串查找解决方案，如果你知道更快的请告诉我。

推荐阅读：

相关文章