哈希是一种key value的存储结构
当哈希表的key越来越多的时候,则避免不了要rehashing来保证新的key能插进来或者来达到更高的性能
然后rehash会导致让当前哈希表的操作停顿,知道rehashing完成为止
借鉴redis分布式的架构,可以使用二级哈希来维护一个hash结构
二级hash高效数据结构
第一级hash
使用一个动态的一致性hash表来维护,他有若干个slot,每个slot是一个hash node
第二级hash
使用unordered_map
分裂
当二级map的key达到一定阈值,则分裂次map,在一致性hash表中,分裂出下一个node,来分担此node的数据
预期效果
性能:
- 在每次获取key时,需要进行二次hash。这可以通过位运算来解决hash带来的性能问题
- 使用分裂来代替整体的rehash,可以大大减少停顿时间,使系统的更加稳定