拓冰网站定制 
brpc 高性能哈希表 FlatMap 深度解析接近原生数组查找速度的 C 实现原理与实战【免费下载链接】brpcbrpc is an Industrial-grade RPC framework using C Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recommendation etc. brpc means better RPC.项目地址: https://gitcode.com/GitHub_Trending/brpc/brpc本文以 Apache brpc 的 docs/cn/flatmap.md 为核心骨架结合src/butil/containers/flat_map.h、flat_map_inl.h源码与 test/flat_map_unittest.cpp 测试验证深入剖析 FlatMap 的开链桶首节点内联设计如何把查找耗时压到接近原生数组并给出完整的初始化、增删查、迭代时删除PositionHint等实战用法同时系统梳理哈希函数选择与冲突解决策略帮助你在检索、广告、推荐等高频查找场景中做出正确的容器选型。FlatMap 是 brpc 内置在butil基础库中的高性能 key/value 容器专为小字典 极快查找设计。它以空间换时间把开链哈希桶中第一个节点直接放进桶数组使大部分查找只需一次内存跳转在检索链路中被广泛用于热点字典、路由表、Header 表等需要纳秒级查找的场合。读完本文你将掌握 FlatMap 的完整 API、参数调优方法、迭代安全删除技巧以及它相对其他哈希表在内存与性能上的取舍。一、FlatMap 是什么用空间换来的极致查找速度1.1 一句话概括FlatMap 是可能最快的哈希表它把开链桶中第一个节点的内容直接放在桶数组内部。由于实践中大部分桶没有冲突或冲突很少绝大多数操作只需要一次内存跳转——通过哈希值直接访问到桶内元素桶内两个及以上的元素仍存放在链表中但桶之间彼此独立一个桶的冲突不会波及其他桶性能非常稳定。在很多场景下FlatMap 的查找性能与原生数组相当。这段话对应源码中开头的注释声明// This closed addressing hash-map puts first linked node in bucket array // directly to save an extra memory indirection. As a result, this map yields // close performance to raw array on nearly all operations, probably being the // fastest hashmap for small-sized key/value ever.即闭寻址开链哈希但把链表首节点内联进桶数组省去一次额外的内存间接跳转。1.2 适用场景与代价最适合检索过程中需要极快查找的小字典元素规模可控、value 相对较小。代价当 value 较大时它比普通开链哈希更耗内存因为每个桶数组槽位都要容纳一份完整的元素key value而不是一个指针。brpc 官方文档与源码注释一致强调small-sized key/value这一前提这也是后续基准测试中 value 取 8/32/128 字节的原因。二、快速上手完整示例代码与逐行讲解以下示例完整取自 docs/cn/flatmap.md并针对 API 语义补充了说明。头文件位于src/butil/containers/flat_map.h使用时只需包含它#include string #include butil/logging.h #include butil/containers/flat_map.h void flatmap_example() { butil::FlatMapint, std::string map; // bucket_count: 初始桶数量足够大以避免 resize。 // load_factor: 元素个数 * 100 / 桶数量 的阈值默认 80。 int bucket_count 1000; int load_factor 80; map.init(bucket_count, load_factor); map.insert(10, hello); // 插入 key10, valuehello返回 value 地址失败返回 nullptr map[20] world; // operator[]不存在则默认构造并插入 std::string* value map.seek(20); // 查找返回 value 指针不存在返回 nullptr CHECK(value ! nullptr); CHECK_EQ(2UL, map.size()); CHECK_EQ(0UL, map.erase(30)); // 删除不存在的 key返回 0 CHECK_EQ(1UL, map.erase(10)); // 删除存在的 key返回 1 LOG(INFO) All elements of the map:; for (butil::FlatMapint, std::string::const_iterator it map.begin(); it ! map.end(); it) { LOG(INFO) it-first : it-second; } map.clear(); // 清空元素内存不归还系统 CHECK_EQ(0UL, map.size()); }要点init(bucket_count, load_factor)返回 0 表示成功返回 -1 表示失败但即使失败 FlatMap 仍可正常使用会退化为默认配置。load_factor默认值是80含义是size() * 100 / bucket_count达到该值时触发 resize桶数量翻倍并全量 rehash这正是文档中load_factor: element_count * 100 / bucket_count, 80 as default的出处。源码中对应的判定为is_too_crowdedstatic bool is_too_crowded(size_t size, size_t nbucket, u_int load_factor) { return size * 100 nbucket * load_factor; }seek返回的是mapped_type*指针而非迭代器未命中返回nullptr适合高频查找路径直接解引用。clear()只清空元素不把已分配空间归还系统如需归还使用clear_and_reset_pool()。2.1 迭代过程中安全删除PositionHint 模式这是文档中第二个示例的核心价值。FlatMap 在erase()之后迭代器可能失败因此必须在erase()之前保存迭代器位置、之后恢复void flatmap_erase_hinted_during_iteration_example() { typedef butil::FlatMapint, int Map; Map map; int bucket_count 1000; int load_factor 80; map.init(bucket_count, load_factor); const int N 10; for (int i 0; i N; i) { map[i] i; } for (Map::const_iterator it map.begin(); it ! map.end(); it) { // erase() 之后 iterator 可能失败 // 所以需要在 erase() 之前保存迭代器erase() 之后恢复。 typename Map::PositionHint hint{}; map.save_iterator(it, hint); if (it-first % 2 0) { CHECK_EQ(1UL, map.erase(it-first)); } it map.restore_iterator(hint); if (it map.end()) { break; } } CHECK_EQ((size_t)(N / 2), map.size()); LOG(INFO) All remaining elements of the map:; for (Map::const_iterator it map.begin(); it ! map.end(); it) { CHECK_EQ(1, it-first % 2); LOG(INFO) it-first : it-second; } map.clear(); CHECK_EQ(0UL, map.size()); }PositionHint在源码中的定义flat_map.hstruct PositionHint { size_t nbucket; // 桶数量 size_t offset; // 桶内偏移 bool at_entry; // 是否位于桶入口首节点位置 key_type key; // 保存的 key };save_iterator/restore_iterator的用途并不局限于单线程循环删除。在 flat_map.h 的注释中给出了多线程分片迭代大表的典型场景在锁内迭代到一定数量如 256 个元素就save_iterator保存位置并解锁业务处理完重新加锁后restore_iterator恢复位置继续遍历如果restore_iterator返回begin()说明期间发生了 resize需要重新开始例如清空已收集的 keys。测试用例do_nothing_during_iteration、erase_insert_visited_during_iteration以及工具函数iteration_with_hinttest/flat_map_unittest.cpp都验证了这套机制。注意这种不一致迭代下迭代期间新增的元素可能被漏掉、部分元素可能被遍历多次、resize 时迭代会从头开始——使用时需根据业务容忍度选择。2.2 从测试看 API 语义test/flat_map_unittest.cpp 中的make_sure_all_methods_compile用例完整覆盖了核心 API 的行为契约insert(1, 100)对已存在的 key 会覆盖valueASSERT_EQ(100, m1[1])insert({3, 30})支持以std::pair形式插入erase(3)返回 1 表示删除成功erase(4)返回 0 表示不存在FlatSetint是对FlatMapint, FlatMapVoid的封装FlatMapVoid用于替换不可构造的void去重语义清晰重复insert不改变 size。三、Benchmark与多种容器的实测对比3.1 对比对象文档中的基准测试将 FlatMap 与三类容器对比AlignHashMap闭链开放寻址中较快的实现CowHashMapsmalltable 中的开链哈希表带 Copy-on-write 逻辑std::map非哈希表通常是红黑树std::map在 C 标准库中普遍为红黑树实现。测试在value 8 / 32 / 128 bytes三种体积、100 / 1000 / 10000三种规模、顺序与随机两种访问模式下分别测量插入inserting、删除erasing和查找seeking的单次平均耗时纳秒。3.2 关键结论数据取自文档中的 TRACE 输出顺序插入Sequentially insertingns/次规模FlatMapAlignHashMapCowHashMapstd::map100value8B1519301021000value8B1028269310000value8B102126130顺序删除Sequentially erasingns/次规模FlatMapAlignHashMapCowHashMapstd::map100value8B711331461000value8B692910010000value8B51030104随机查找Seekingns/次规模FlatMapAlignHashMapCowHashMapstd::map100value8B4712541000value8B37117810000value8B4813172综合全部输出可以看到查找是 FlatMap 的最大优势8 字节 value 时 seek 低至 3~4ns相比 std::map 快一个数量级以上即使在 128 字节 value、10000 规模下FlatMap 的 seek 也仅 9ns而 std::map 需要 166ns。插入/删除同样领先多数组合下 FlatMap 比 AlignHashMap 快约 2~4 倍比 std::map 快约 10 倍以上。value 增大时差距缩小128 字节 value 下 FlatMap 的插入从 10ns 左右升到 28~46ns说明 value 越大拷贝成本占比越高FlatMap 的首节点内联优势相对减弱——这印证了它更适合小 value 的场景。std::map 查找随规模显著劣化100→10000 从 54ns 涨到 172ns符合红黑树 O(log n) 的特性而 FlatMap 的查找几乎不随规模增长体现其接近数组的 O(1) 定位能力。作为佐证flat_map.h 头文件注释中还记录了与std::map、butil::PooledMap、std::unordered_map、std::unordered_multimap、butil::hash_map的对比数据FlatMap 在多数操作上同样处于领先位置。这些基准数据来自文档记录的特定环境约 2GHz 主频下的测试输出绝对数值会随硬件与编译器变化但相对趋势FlatMap 查找接近数组、随规模增长平稳具有普适性。四、源码级原理FlatMap 为何快4.1 数据结构首节点内联的桶数组源码中FlatMap的内部结构flat_map.hstruct Bucket { Bucket() : next((Bucket*)-1UL) {} // -1 表示无效槽位 Bucket(const Bucket other) : next(nullptr) { element_space_.Init(other.element()); } bool is_valid() const { return next ! (const Bucket*)-1UL; } void set_invalid() { next (Bucket*)-1UL; } Element element() { return *element_space_; } void destroy_element() { element_space_.Destroy(); } Bucket* next; // 冲突链表后继 private: ManualConstructorElement element_space_; // 元素直接内联在桶内 };关键设计每个Bucket内通过ManualConstructorElement直接内联一份完整元素FlatMapElementK,T持有K _key与T _value而不是一个指向堆上节点的指针next指针在无元素时为哨兵值(Bucket*)-1UL标记无效有元素且无冲突时为nullptr有冲突时指向链上后续节点桶数组末尾额外多放一个Bucket_default_buckets[DEFAULT_NBUCKET 1]让迭代器知道桶数组的终点。4.2 查找路径一次哈希定位 零/一次链表遍历seek的实现flat_map_inl.h_T* FlatMap_K, _T, _H, _E, _S, _A, _M::seek(const K2 key) const { Bucket first_node _buckets[flatmap_mod(_hashfn(key), _nbucket)]; if (!first_node.is_valid()) { return nullptr; // 空桶直接返回 } if (_eql(first_node.element().first_ref(), key)) { return first_node.element().second_ref(); // 命中首节点一次跳转 } Bucket *p first_node.next; // 否则沿链表查找 while (p) { if (_eql(p-element().first_ref(), key)) { return p-element().second_ref(); } p p-next; } return nullptr; }对照文档的描述大部分桶无冲突或冲突较少于是flatmap_mod(hash(key), nbucket)定位后要么发现桶无效直接返回要么首节点即目标全程只有一次数组访存只有当桶内冲突时才沿next链表多走几步由于桶之间彼此独立冲突被局部化不会像闭链哈希那样形成全局聚集。这就是在很多时候 FlatMap 的查找性能和原生数组接近的源码依据一次数组下标访问像数组arr[i] 一次 key 比较即完成查找。4.3 内存与并发特性内存O(NumElement * (KeySize ValueSize SomePointers))量级每个元素只需少量指针甚至零指针用于未冲突的桶相比经典开链哈希每对 key/value 都要额外分配节点和指针内联设计减少了指针开销但代价是桶数组槽位要容纳完整元素value 越大浪费越明显。节点内存管理使用SingleThreadedPool见_pool成员复用节点clear()后内存不归还系统避免频繁 malloc/free。并发桶相互独立天然适合细粒度锁或无锁读save_iterator/restore_iterator为多线程分片迭代提供了官方支持见 flat_map.h 注释中的多线程拷贝 keys 示例。4.4 初始化、resize 与哈希/比较器定制小表优化FlatMap 构造后即已初始化内部使用_default_buckets[DEFAULT_NBUCKET 1]作为默认桶数组DEFAULT_NBUCKET默认 16可通过宏BRPC_FLATMAP_DEFAULT_NBUCKET覆盖。因此init()只在你需要更大初始桶数或非默认 load_factor时才必须调用。测试copy_flat_map验证了init(8)小于默认值时仍沿用默认桶数组init(DEFAULT_NBUCKET 1)才会真正分配新桶。resize 触发条件insert/operator[]前检查size * 100 nbucket * load_factor达到则桶数量翻倍并全量 rehashresize实现见 flat_map_inl.h。文档强调bucket_count 初始值要足够大以避免 resize因为 rehash 成本高昂。模板参数定制flat_map.htemplate typename _K, typename _T, typename _Hash DefaultHasher_K, // 哈希函数 typename _Equal DefaultEqualTo_K, // key 等价判定 bool _Sparse false, // 是否稀疏模式SparseFlatMap typename _Alloc PtAllocator, // 分配器 bool _Multi false // 是否允许多值MultiFlatMap class FlatMap { ... };默认DefaultHasher继承butil::hash对std::string特化为result result * 101 c的滚动哈希支持const char*、StringPiece免拷贝查找_Multitrue时得到MultiFlatMap允许一个 key 关联多个 valueerase返回删除的数量、seek_all返回所有 value 指针_Sparsetrue时得到SparseFlatMap/SparseFlatSet使用 bit array_thumbnail标记非空桶以加速遍历FlatSet/SparseFlatSet则以FlatMapVoid作为 value提供去重集合语义此外还有CaseIgnoredFlatMap见 case_ignored_flat_map.h用于 HTTP Header 等大小写不敏感 key 的场景测试case_ignored_map验证了Content-Type与content-Type视为同一 key。五、哈希表全景FlatMap 在冲突解决谱系中的位置文档的 Overview of hashmaps 部分系统回顾了哈希表的两大构成要素理解这些是正确使用 FlatMap 的前提。5.1 计算哈希值非加密型哈希表通过计算哈希值把不同 key 分散到不同区间查找时用哈希值快速缩小范围参数恰当时大部分时候能 O(1) 完成 key→value 映射。但O(1)在不同实现间差异巨大。一个好的非加密型哈希算法要考虑结果确定性同一 key 多次计算必须一致雪崩效应输入中一个 bit 的变化应尽量影响输出所有 bit 的变化均匀分布输出尽量在值域中均匀分布减少冲突利用现代 CPU 特性成块计算、减少分支、循环展开等。文档指出大部分哈希算法针对单个 key 不会耗太多 CPU影响主要来自哈希表的整体数据分布选用何种算法要依据实践效果一些最简单的方法可能就有很好效果通用算法可选MurmurHashbrpc 的三方库中也包含 murmurhash3 供选用源码注释明确建议Use murmurhash3 to make better distributions。5.2 解决冲突四种主流方案对比1开链哈希open hashing / closed addressing链表的数组链表即桶。冲突时在桶内做链表插入。优点内存为O(NumElement * (KeySize ValueSize SomePointers))resize 不会使既有 key/value 内存失效桶之间独立一个桶的冲突不影响其他桶平均查找时间稳定独立的桶易于高并发。缺点至少要两次内存跳转先到桶入口再到桶中首节点。小表时节点内存接近问题不明显表变大后访存愈发随机。文档估算一次访存约 50ns2GHz 主频开链哈希查找往往在 100ns 以上。在检索端层层 ranking 中对热点字典的查找 1 秒内可能有几百万次以上开链哈希可能成为热点且每对 key/value 需要额外指针可能被诟病内存开销。2闭链哈希closed hashing / open addressing初衷是减少内存跳转桶不再只是链表入口而是直接记录一对 key/value 与标记桶被占时按探查方法找空桶线性探查找下一个桶、二次探查按 1,2,4,9... 平方数位移查找。优点表很空或冲突少时查找只需一次访存无需管理节点内存池。缺点更多桶个数必须大于元素个数resize 后旧内存全部失效难以并发聚集效应区域内元素超过约 70% 时大量元素的实际桶相对应有桶产生较大位移主要操作要扫过一大片内存性能不稳定、难预测。文档强调闭链哈希在复杂应用中往往不如开链甚至可能数量级地慢。衍生方案如 Hopscotch hashing 试图缓解。3混合开链与闭链典型如 Coalesced hashing把桶数组的一部分拿出来容纳冲突元素。但没有解决开链的内存跳转问题结构比闭链复杂得多工程效果不好。4多次哈希用多个哈希表代替一个冲突时用另一个哈希值尝试另一张表典型如 Cuckoo hashing。同样没有解决内存跳转问题。FlatMap 的定位属于开链闭寻址的改良——通过首节点内联把开链最常见的两次内存跳转降为一次从而在保留开链桶独立、并发友好、resize 安全、性能稳定等全部优点的同时把查找性能提升到接近原生数组。这正是它区别于闭链哈希与普通开链哈希的核心竞争力。六、工程建议什么时候用 FlatMap综合文档、源码与基准数据给出如下选型建议均以当前仓库实现为事实依据热点小字典高频查找如检索 ranking 过程中的特征字典、路由表、限额表key 规模可控、value 较小8~32 字节为佳优先选择butil::FlatMap可显著降低单次查找耗时。明确预估元素规模调用init(bucket_count, load_factor)时把bucket_count设为足够大例如预期元素数的 1.25 倍以上配合默认 load_factor 80避免触发翻倍 rehash 的昂贵操作。value 较大时权衡128 字节及以上 value 时 FlatMap 的内存代价与拷贝成本上升、相对优势收窄需要结合实际访问频率评估是否仍值得。大小写不敏感 keyHTTP Header 等场景用CaseIgnoredFlatMap需要去重集合用FlatSet一个 key 多个 value用MultiFlatMap需要加速遍历的稀疏场景用SparseFlatMap。需要有序遍历FlatMap 不保证 key 有序此时应改用std::map红黑树或自行排序。多线程分片迭代大表在锁内分批处理时使用save_iterator/restore_iterator分割临界区并处理 resize 后重新开始的语义。延伸阅读核心实现src/butil/containers/flat_map.h类定义、Bucket 结构、FlatSet/SparseFlatMap/FlatMapElement/DefaultHasher内联实现src/butil/containers/flat_map_inl.hinit/seek/insert/operator[]/resize 等单元测试test/flat_map_unittest.cppAPI 语义、PositionHint 迭代、copy/swap、性能对比用例大小写不敏感变体src/butil/containers/case_ignored_flat_map.h相关容器src/butil/containers/pooled_map.hPooledMap、src/butil/containers/hash_tables.hbutil::hash_map / hash 特化【免费下载链接】brpcbrpc is an Industrial-grade RPC framework using C Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recommendation etc. brpc means better RPC.项目地址: https://gitcode.com/GitHub_Trending/brpc/brpc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 brpc 高性能哈希表 FlatMap 深度解析：接近原生数组查找速度的 C++ 实现原理与实战
brpc 高性能哈希表 FlatMap 深度解析接近原生数组查找速度的 C 实现原理与实战【免费下载链接】brpcbrpc is an Industrial-grade RPC framework using C Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recommendation etc. brpc means better RPC.项目地址: https://gitcode.com/GitHub_Trending/brpc/brpc本文以 Apache brpc 的 docs/cn/flatmap.md 为核心骨架结合src/butil/containers/flat_map.h、flat_map_inl.h源码与 test/flat_map_unittest.cpp 测试验证深入剖析 FlatMap 的开链桶首节点内联设计如何把查找耗时压到接近原生数组并给出完整的初始化、增删查、迭代时删除PositionHint等实战用法同时系统梳理哈希函数选择与冲突解决策略帮助你在检索、广告、推荐等高频查找场景中做出正确的容器选型。FlatMap 是 brpc 内置在butil基础库中的高性能 key/value 容器专为小字典 极快查找设计。它以空间换时间把开链哈希桶中第一个节点直接放进桶数组使大部分查找只需一次内存跳转在检索链路中被广泛用于热点字典、路由表、Header 表等需要纳秒级查找的场合。读完本文你将掌握 FlatMap 的完整 API、参数调优方法、迭代安全删除技巧以及它相对其他哈希表在内存与性能上的取舍。一、FlatMap 是什么用空间换来的极致查找速度1.1 一句话概括FlatMap 是可能最快的哈希表它把开链桶中第一个节点的内容直接放在桶数组内部。由于实践中大部分桶没有冲突或冲突很少绝大多数操作只需要一次内存跳转——通过哈希值直接访问到桶内元素桶内两个及以上的元素仍存放在链表中但桶之间彼此独立一个桶的冲突不会波及其他桶性能非常稳定。在很多场景下FlatMap 的查找性能与原生数组相当。这段话对应源码中开头的注释声明// This closed addressing hash-map puts first linked node in bucket array // directly to save an extra memory indirection. As a result, this map yields // close performance to raw array on nearly all operations, probably being the // fastest hashmap for small-sized key/value ever.即闭寻址开链哈希但把链表首节点内联进桶数组省去一次额外的内存间接跳转。1.2 适用场景与代价最适合检索过程中需要极快查找的小字典元素规模可控、value 相对较小。代价当 value 较大时它比普通开链哈希更耗内存因为每个桶数组槽位都要容纳一份完整的元素key value而不是一个指针。brpc 官方文档与源码注释一致强调small-sized key/value这一前提这也是后续基准测试中 value 取 8/32/128 字节的原因。二、快速上手完整示例代码与逐行讲解以下示例完整取自 docs/cn/flatmap.md并针对 API 语义补充了说明。头文件位于src/butil/containers/flat_map.h使用时只需包含它#include string #include butil/logging.h #include butil/containers/flat_map.h void flatmap_example() { butil::FlatMapint, std::string map; // bucket_count: 初始桶数量足够大以避免 resize。 // load_factor: 元素个数 * 100 / 桶数量 的阈值默认 80。 int bucket_count 1000; int load_factor 80; map.init(bucket_count, load_factor); map.insert(10, hello); // 插入 key10, valuehello返回 value 地址失败返回 nullptr map[20] world; // operator[]不存在则默认构造并插入 std::string* value map.seek(20); // 查找返回 value 指针不存在返回 nullptr CHECK(value ! nullptr); CHECK_EQ(2UL, map.size()); CHECK_EQ(0UL, map.erase(30)); // 删除不存在的 key返回 0 CHECK_EQ(1UL, map.erase(10)); // 删除存在的 key返回 1 LOG(INFO) All elements of the map:; for (butil::FlatMapint, std::string::const_iterator it map.begin(); it ! map.end(); it) { LOG(INFO) it-first : it-second; } map.clear(); // 清空元素内存不归还系统 CHECK_EQ(0UL, map.size()); }要点init(bucket_count, load_factor)返回 0 表示成功返回 -1 表示失败但即使失败 FlatMap 仍可正常使用会退化为默认配置。load_factor默认值是80含义是size() * 100 / bucket_count达到该值时触发 resize桶数量翻倍并全量 rehash这正是文档中load_factor: element_count * 100 / bucket_count, 80 as default的出处。源码中对应的判定为is_too_crowdedstatic bool is_too_crowded(size_t size, size_t nbucket, u_int load_factor) { return size * 100 nbucket * load_factor; }seek返回的是mapped_type*指针而非迭代器未命中返回nullptr适合高频查找路径直接解引用。clear()只清空元素不把已分配空间归还系统如需归还使用clear_and_reset_pool()。2.1 迭代过程中安全删除PositionHint 模式这是文档中第二个示例的核心价值。FlatMap 在erase()之后迭代器可能失败因此必须在erase()之前保存迭代器位置、之后恢复void flatmap_erase_hinted_during_iteration_example() { typedef butil::FlatMapint, int Map; Map map; int bucket_count 1000; int load_factor 80; map.init(bucket_count, load_factor); const int N 10; for (int i 0; i N; i) { map[i] i; } for (Map::const_iterator it map.begin(); it ! map.end(); it) { // erase() 之后 iterator 可能失败 // 所以需要在 erase() 之前保存迭代器erase() 之后恢复。 typename Map::PositionHint hint{}; map.save_iterator(it, hint); if (it-first % 2 0) { CHECK_EQ(1UL, map.erase(it-first)); } it map.restore_iterator(hint); if (it map.end()) { break; } } CHECK_EQ((size_t)(N / 2), map.size()); LOG(INFO) All remaining elements of the map:; for (Map::const_iterator it map.begin(); it ! map.end(); it) { CHECK_EQ(1, it-first % 2); LOG(INFO) it-first : it-second; } map.clear(); CHECK_EQ(0UL, map.size()); }PositionHint在源码中的定义flat_map.hstruct PositionHint { size_t nbucket; // 桶数量 size_t offset; // 桶内偏移 bool at_entry; // 是否位于桶入口首节点位置 key_type key; // 保存的 key };save_iterator/restore_iterator的用途并不局限于单线程循环删除。在 flat_map.h 的注释中给出了多线程分片迭代大表的典型场景在锁内迭代到一定数量如 256 个元素就save_iterator保存位置并解锁业务处理完重新加锁后restore_iterator恢复位置继续遍历如果restore_iterator返回begin()说明期间发生了 resize需要重新开始例如清空已收集的 keys。测试用例do_nothing_during_iteration、erase_insert_visited_during_iteration以及工具函数iteration_with_hinttest/flat_map_unittest.cpp都验证了这套机制。注意这种不一致迭代下迭代期间新增的元素可能被漏掉、部分元素可能被遍历多次、resize 时迭代会从头开始——使用时需根据业务容忍度选择。2.2 从测试看 API 语义test/flat_map_unittest.cpp 中的make_sure_all_methods_compile用例完整覆盖了核心 API 的行为契约insert(1, 100)对已存在的 key 会覆盖valueASSERT_EQ(100, m1[1])insert({3, 30})支持以std::pair形式插入erase(3)返回 1 表示删除成功erase(4)返回 0 表示不存在FlatSetint是对FlatMapint, FlatMapVoid的封装FlatMapVoid用于替换不可构造的void去重语义清晰重复insert不改变 size。三、Benchmark与多种容器的实测对比3.1 对比对象文档中的基准测试将 FlatMap 与三类容器对比AlignHashMap闭链开放寻址中较快的实现CowHashMapsmalltable 中的开链哈希表带 Copy-on-write 逻辑std::map非哈希表通常是红黑树std::map在 C 标准库中普遍为红黑树实现。测试在value 8 / 32 / 128 bytes三种体积、100 / 1000 / 10000三种规模、顺序与随机两种访问模式下分别测量插入inserting、删除erasing和查找seeking的单次平均耗时纳秒。3.2 关键结论数据取自文档中的 TRACE 输出顺序插入Sequentially insertingns/次规模FlatMapAlignHashMapCowHashMapstd::map100value8B1519301021000value8B1028269310000value8B102126130顺序删除Sequentially erasingns/次规模FlatMapAlignHashMapCowHashMapstd::map100value8B711331461000value8B692910010000value8B51030104随机查找Seekingns/次规模FlatMapAlignHashMapCowHashMapstd::map100value8B4712541000value8B37117810000value8B4813172综合全部输出可以看到查找是 FlatMap 的最大优势8 字节 value 时 seek 低至 3~4ns相比 std::map 快一个数量级以上即使在 128 字节 value、10000 规模下FlatMap 的 seek 也仅 9ns而 std::map 需要 166ns。插入/删除同样领先多数组合下 FlatMap 比 AlignHashMap 快约 2~4 倍比 std::map 快约 10 倍以上。value 增大时差距缩小128 字节 value 下 FlatMap 的插入从 10ns 左右升到 28~46ns说明 value 越大拷贝成本占比越高FlatMap 的首节点内联优势相对减弱——这印证了它更适合小 value 的场景。std::map 查找随规模显著劣化100→10000 从 54ns 涨到 172ns符合红黑树 O(log n) 的特性而 FlatMap 的查找几乎不随规模增长体现其接近数组的 O(1) 定位能力。作为佐证flat_map.h 头文件注释中还记录了与std::map、butil::PooledMap、std::unordered_map、std::unordered_multimap、butil::hash_map的对比数据FlatMap 在多数操作上同样处于领先位置。这些基准数据来自文档记录的特定环境约 2GHz 主频下的测试输出绝对数值会随硬件与编译器变化但相对趋势FlatMap 查找接近数组、随规模增长平稳具有普适性。四、源码级原理FlatMap 为何快4.1 数据结构首节点内联的桶数组源码中FlatMap的内部结构flat_map.hstruct Bucket { Bucket() : next((Bucket*)-1UL) {} // -1 表示无效槽位 Bucket(const Bucket other) : next(nullptr) { element_space_.Init(other.element()); } bool is_valid() const { return next ! (const Bucket*)-1UL; } void set_invalid() { next (Bucket*)-1UL; } Element element() { return *element_space_; } void destroy_element() { element_space_.Destroy(); } Bucket* next; // 冲突链表后继 private: ManualConstructorElement element_space_; // 元素直接内联在桶内 };关键设计每个Bucket内通过ManualConstructorElement直接内联一份完整元素FlatMapElementK,T持有K _key与T _value而不是一个指向堆上节点的指针next指针在无元素时为哨兵值(Bucket*)-1UL标记无效有元素且无冲突时为nullptr有冲突时指向链上后续节点桶数组末尾额外多放一个Bucket_default_buckets[DEFAULT_NBUCKET 1]让迭代器知道桶数组的终点。4.2 查找路径一次哈希定位 零/一次链表遍历seek的实现flat_map_inl.h_T* FlatMap_K, _T, _H, _E, _S, _A, _M::seek(const K2 key) const { Bucket first_node _buckets[flatmap_mod(_hashfn(key), _nbucket)]; if (!first_node.is_valid()) { return nullptr; // 空桶直接返回 } if (_eql(first_node.element().first_ref(), key)) { return first_node.element().second_ref(); // 命中首节点一次跳转 } Bucket *p first_node.next; // 否则沿链表查找 while (p) { if (_eql(p-element().first_ref(), key)) { return p-element().second_ref(); } p p-next; } return nullptr; }对照文档的描述大部分桶无冲突或冲突较少于是flatmap_mod(hash(key), nbucket)定位后要么发现桶无效直接返回要么首节点即目标全程只有一次数组访存只有当桶内冲突时才沿next链表多走几步由于桶之间彼此独立冲突被局部化不会像闭链哈希那样形成全局聚集。这就是在很多时候 FlatMap 的查找性能和原生数组接近的源码依据一次数组下标访问像数组arr[i] 一次 key 比较即完成查找。4.3 内存与并发特性内存O(NumElement * (KeySize ValueSize SomePointers))量级每个元素只需少量指针甚至零指针用于未冲突的桶相比经典开链哈希每对 key/value 都要额外分配节点和指针内联设计减少了指针开销但代价是桶数组槽位要容纳完整元素value 越大浪费越明显。节点内存管理使用SingleThreadedPool见_pool成员复用节点clear()后内存不归还系统避免频繁 malloc/free。并发桶相互独立天然适合细粒度锁或无锁读save_iterator/restore_iterator为多线程分片迭代提供了官方支持见 flat_map.h 注释中的多线程拷贝 keys 示例。4.4 初始化、resize 与哈希/比较器定制小表优化FlatMap 构造后即已初始化内部使用_default_buckets[DEFAULT_NBUCKET 1]作为默认桶数组DEFAULT_NBUCKET默认 16可通过宏BRPC_FLATMAP_DEFAULT_NBUCKET覆盖。因此init()只在你需要更大初始桶数或非默认 load_factor时才必须调用。测试copy_flat_map验证了init(8)小于默认值时仍沿用默认桶数组init(DEFAULT_NBUCKET 1)才会真正分配新桶。resize 触发条件insert/operator[]前检查size * 100 nbucket * load_factor达到则桶数量翻倍并全量 rehashresize实现见 flat_map_inl.h。文档强调bucket_count 初始值要足够大以避免 resize因为 rehash 成本高昂。模板参数定制flat_map.htemplate typename _K, typename _T, typename _Hash DefaultHasher_K, // 哈希函数 typename _Equal DefaultEqualTo_K, // key 等价判定 bool _Sparse false, // 是否稀疏模式SparseFlatMap typename _Alloc PtAllocator, // 分配器 bool _Multi false // 是否允许多值MultiFlatMap class FlatMap { ... };默认DefaultHasher继承butil::hash对std::string特化为result result * 101 c的滚动哈希支持const char*、StringPiece免拷贝查找_Multitrue时得到MultiFlatMap允许一个 key 关联多个 valueerase返回删除的数量、seek_all返回所有 value 指针_Sparsetrue时得到SparseFlatMap/SparseFlatSet使用 bit array_thumbnail标记非空桶以加速遍历FlatSet/SparseFlatSet则以FlatMapVoid作为 value提供去重集合语义此外还有CaseIgnoredFlatMap见 case_ignored_flat_map.h用于 HTTP Header 等大小写不敏感 key 的场景测试case_ignored_map验证了Content-Type与content-Type视为同一 key。五、哈希表全景FlatMap 在冲突解决谱系中的位置文档的 Overview of hashmaps 部分系统回顾了哈希表的两大构成要素理解这些是正确使用 FlatMap 的前提。5.1 计算哈希值非加密型哈希表通过计算哈希值把不同 key 分散到不同区间查找时用哈希值快速缩小范围参数恰当时大部分时候能 O(1) 完成 key→value 映射。但O(1)在不同实现间差异巨大。一个好的非加密型哈希算法要考虑结果确定性同一 key 多次计算必须一致雪崩效应输入中一个 bit 的变化应尽量影响输出所有 bit 的变化均匀分布输出尽量在值域中均匀分布减少冲突利用现代 CPU 特性成块计算、减少分支、循环展开等。文档指出大部分哈希算法针对单个 key 不会耗太多 CPU影响主要来自哈希表的整体数据分布选用何种算法要依据实践效果一些最简单的方法可能就有很好效果通用算法可选MurmurHashbrpc 的三方库中也包含 murmurhash3 供选用源码注释明确建议Use murmurhash3 to make better distributions。5.2 解决冲突四种主流方案对比1开链哈希open hashing / closed addressing链表的数组链表即桶。冲突时在桶内做链表插入。优点内存为O(NumElement * (KeySize ValueSize SomePointers))resize 不会使既有 key/value 内存失效桶之间独立一个桶的冲突不影响其他桶平均查找时间稳定独立的桶易于高并发。缺点至少要两次内存跳转先到桶入口再到桶中首节点。小表时节点内存接近问题不明显表变大后访存愈发随机。文档估算一次访存约 50ns2GHz 主频开链哈希查找往往在 100ns 以上。在检索端层层 ranking 中对热点字典的查找 1 秒内可能有几百万次以上开链哈希可能成为热点且每对 key/value 需要额外指针可能被诟病内存开销。2闭链哈希closed hashing / open addressing初衷是减少内存跳转桶不再只是链表入口而是直接记录一对 key/value 与标记桶被占时按探查方法找空桶线性探查找下一个桶、二次探查按 1,2,4,9... 平方数位移查找。优点表很空或冲突少时查找只需一次访存无需管理节点内存池。缺点更多桶个数必须大于元素个数resize 后旧内存全部失效难以并发聚集效应区域内元素超过约 70% 时大量元素的实际桶相对应有桶产生较大位移主要操作要扫过一大片内存性能不稳定、难预测。文档强调闭链哈希在复杂应用中往往不如开链甚至可能数量级地慢。衍生方案如 Hopscotch hashing 试图缓解。3混合开链与闭链典型如 Coalesced hashing把桶数组的一部分拿出来容纳冲突元素。但没有解决开链的内存跳转问题结构比闭链复杂得多工程效果不好。4多次哈希用多个哈希表代替一个冲突时用另一个哈希值尝试另一张表典型如 Cuckoo hashing。同样没有解决内存跳转问题。FlatMap 的定位属于开链闭寻址的改良——通过首节点内联把开链最常见的两次内存跳转降为一次从而在保留开链桶独立、并发友好、resize 安全、性能稳定等全部优点的同时把查找性能提升到接近原生数组。这正是它区别于闭链哈希与普通开链哈希的核心竞争力。六、工程建议什么时候用 FlatMap综合文档、源码与基准数据给出如下选型建议均以当前仓库实现为事实依据热点小字典高频查找如检索 ranking 过程中的特征字典、路由表、限额表key 规模可控、value 较小8~32 字节为佳优先选择butil::FlatMap可显著降低单次查找耗时。明确预估元素规模调用init(bucket_count, load_factor)时把bucket_count设为足够大例如预期元素数的 1.25 倍以上配合默认 load_factor 80避免触发翻倍 rehash 的昂贵操作。value 较大时权衡128 字节及以上 value 时 FlatMap 的内存代价与拷贝成本上升、相对优势收窄需要结合实际访问频率评估是否仍值得。大小写不敏感 keyHTTP Header 等场景用CaseIgnoredFlatMap需要去重集合用FlatSet一个 key 多个 value用MultiFlatMap需要加速遍历的稀疏场景用SparseFlatMap。需要有序遍历FlatMap 不保证 key 有序此时应改用std::map红黑树或自行排序。多线程分片迭代大表在锁内分批处理时使用save_iterator/restore_iterator分割临界区并处理 resize 后重新开始的语义。延伸阅读核心实现src/butil/containers/flat_map.h类定义、Bucket 结构、FlatSet/SparseFlatMap/FlatMapElement/DefaultHasher内联实现src/butil/containers/flat_map_inl.hinit/seek/insert/operator[]/resize 等单元测试test/flat_map_unittest.cppAPI 语义、PositionHint 迭代、copy/swap、性能对比用例大小写不敏感变体src/butil/containers/case_ignored_flat_map.h相关容器src/butil/containers/pooled_map.hPooledMap、src/butil/containers/hash_tables.hbutil::hash_map / hash 特化【免费下载链接】brpcbrpc is an Industrial-grade RPC framework using C Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recommendation etc. brpc means better RPC.项目地址: https://gitcode.com/GitHub_Trending/brpc/brpc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考