江苏龙网

  1. 主页 > 生活百科 > >

C++中的HashTable性能优化

C++

作者：leomryang ， 腾讯 PCG 后台开发工程师
 

HashTable是开发中常用的数据结构 。本文从C++ STL中的HashTable讲起 ， 分析其存在的性能问题 ， 对比业界改进的实现方式 。通过基准测试对比其实际性能表现 ， 总结更优的实现版本 。
STL HashTable的问题 
STL中的HashTable实现为std::unordered_map ， 采用链接法(chaining)解决hash碰撞 ， hash值相同的多个pair组织为链表 ， 如图1所示 。
C++中的HashTable性能优化

文章插图
 
图1 std::unordered_map内存布局
查找key值时 ， 需要遍历对应的链表 ， 寻找值相同的key 。链表中节点内存分布不连续 ， 相邻节点处于同一cache line的概率很小 ， 因此会产生较多的cpu cache miss ， 降低查询效率 。
改进版HashTable
google absl::flat_hash_map采用开放寻址法(open addressing)解决hash碰撞 ， 并使用二次探测(quadratic probing)方式 。absl::flat_hash_map改进了内存布局 ， 将所有pair放在一段连续内存中 ， 将hash值相同的多个pair放在相邻位置 ， 如图2所示 。
C++中的HashTable性能优化

文章插图
 
图2 absl::flat_hash_map内存布局
查找key时 ， 以二次探测方式遍历hash值相等的pair ， 寻找值相等的key 。hash值相同的pair存储在相邻内存位置处 ， 内存局部性好 ， 对cpu cache友好 ， 可提高查询效率 。
在内存用量方面 ， absl::flat_hash_map空间复杂度为 *O((sizeof(std::pair) + 1) * bucket_count())* 。最大负载因子被设计为0.875 ， 超过该值后 ， 表大小会增加一倍 。因此absl::flat_hash_map的size()通常介于 0.4375 * bucket_count() 和 0.875 * bucket_count() 之间 。
需要注意 ， absl::flat_hash_map在rehash时 ， 会对pair进行move ， 因此pair的指针会失效 ， 类似下述用法会访问非法内存地址 。
absl::flat_hash_map map;// ... init mapFoo& foo1 = map["f1"];Foo* foo2 = &(map["f2"]);// ... rehash mapfoo1.DoSomething(); // 非法访问 ， foo1引用的对象已被movefoo2->DoSomething(); // 非法访问 ， foo2指向的对象已被move
为了解决上述pair指针失效问题 ， google absl::node_hash_map将pair存储在单独分配的节点中 ， 在连续内存中存放指向这些节点的指针 ， 其他设计与flat_hash_map相同 ， 如图3所示 。
C++中的HashTable性能优化

文章插图
 
图3 absl::node_hash_map内存布局
absl::node_hash_map在rehash时 ， pair本身无需移动 ， 只需将指针拷贝至新的地址 。可保证pair的指针稳定性 。
源码探究
下面对absl两种HashTable的核心逻辑源码进行探索（省略不相关部分的代码）：
 
  1. 分配内存
// flat_hash_map和node_hash_map均以raw_hash_set为父类实现 ， 区别在于policy不同template , class Eq = absl::container_internal::hash_default_eq, class Allocator = std::allocator>>class flat_hash_map : public absl::container_internal::raw_hash_map< absl::container_internal::FlatHashMAppolicy, Hash, Eq, Allocator> {};template , class Eq = absl::container_internal::hash_default_eq, class Alloc = std::allocator>>class node_hash_map : public absl::container_internal::raw_hash_map< absl::container_internal::NodeHashMapPolicy, Hash, Eq, Alloc> {};template class raw_hash_map : public raw_hash_set{};// raw_hash_set分配连续内存的大小取决于 capacity_ 和 slot_typetemplate class raw_hash_set { using slot_type = typename Policy::slot_type; void initialize_slots() { // 分配连续内存的大小为 capacity_ * slot_size 并对齐 slot_align char* mem = static_cast(Allocate( &alloc_ref(), AllocSize(capacity_, sizeof(slot_type), alignof(slot_type)))); ctrl_ = reinterpret_cast(mem); slots_ = reinterpret_cast( mem + SlotOffset(capacity_, alignof(slot_type))); ResetCtrl(capacity_, ctrl_, slots_, sizeof(slot_type)); reset_growth_left(); infoz().RecordStorageChanged(size_, capacity_); } inline size_t AllocSize(size_t capacity, size_t slot_size, size_t slot_align) { return SlotOffset(capacity, slot_align) + capacity * slot_size; }};// flat_hash_map的slot包含pairtemplate struct FlatHashMapPolicy { using slot_type = typename map_slot_type;};template union map_slot_type { using value_type = std::pair; using mutable_value_type = std::pair, absl::remove_const_t>; value_type value; mutable_value_type mutable_value; absl::remove_const_t key;};// node_hash_map的slot为指向pair的指针template class NodeHashMapPolicy : public absl::container_internal::node_slot_policy< std::pair&, NodeHashMapPolicy>{};template struct node_slot_policy { using slot_type = typename std::remove_cv< typename std::remove_reference::type>::type*; // slot为指向pair的指针};


推荐阅读


上一篇：短视频开发，如何正确的使用前后端分离？

下一篇：二胎|迪丽热巴首次回应，恋爱结婚生子，不希望被过度关注