brpc 的 butil::FlatMap 深度解析把开链哈希优化到接近原生数组的查找性能【免费下载链接】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本文以 brpc 仓库中的 flatmap 文档英文版 docs/en/flatmap.md 目前为未翻译占位页指向中文版为核心结合 flat_map.h、flat_map_inl.h 源码实现与 flat_map_unittest.cpp 测试系统讲解butil::FlatMap的设计原理、完整 API、基准测试结论与哈希表冲突解决全景。读完你将掌握何时该用 FlatMap、如何正确初始化并调用其全部接口、其一次内存跳转原理的源码级依据以及开链/闭链等哈希方案在工程上的取舍。一、FlatMap 是什么butil::FlatMap是 brpc 的底层基础库 butil 提供的高性能 key/value 容器头文件注释对其定位的概括是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.即这是一款闭寻址开链哈希表但把开链桶中第一个节点的内容直接放进桶数组内部从而省掉一次额外的内存间接跳转使几乎所有操作都接近原生数组的性能。它可能是小体积 key/value 场景下最快的哈希表代价是需要更多内存——尤其当 value 较大时。适用场景检索过程中需要极快查找的小字典。在 brpc 内部它被广泛用于这类场景例如controller.h 用butil::FlatMapstd::string, std::string保存用户自定义字段UserFieldsMapextension.h 用butil::CaseIgnoredFlatMapT*管理扩展注册表hpack.cpp 用 FlatMap 与 CaseIgnoredFlatMap 维护 HPACK 头部索引表naming_service_thread.cpp 用 FlatMap 缓存命名服务线程。二、快速上手完整示例文档给出了两个可直接编译运行的示例这里完整保留并逐行注解。2.1 基础增删查改#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); // 插入key 已存在则覆盖 value 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)); // 删除成功返回 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; // 遍历迭代器为 forward iterator } map.clear(); // 清空元素不归还内存 CHECK_EQ(0UL, map.size()); }2.2 遍历中删除PositionHint 方案由于erase()之后iterator可能失效FlatMap 提供了save_iterator/restore_iterator机制在遍历过程中安全删除元素void flatmap_erase_hinted_during_iteration_example() { typedef butil::FlatMapint, int Map; Map map; // bucket_count: 初始桶个数设得足够大以避免 resize。 // load_factor: 元素数 * 100 / 桶数默认 80。 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)); // 删除偶数 key } 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()); }该模式同样被 flat_map_unittest.cpp 中的erase_hinted_during_iteration测试覆盖验证。PositionHint在源码中的定义包含四个字段——nbucket保存时的桶数用于检测 resize、offset当前桶下标、at_entry迭代器是否正指向桶内首节点、key当前 key——见 flat_map.h。restore_iterator的实现逻辑是若hint.nbucket ! _nbucket说明发生了 resize直接从头重新开始若偏移越界则终止迭代否则按at_entry与 key 精确定位恢复见 flat_map_inl.h。三、核心 API 与参数语义源码级3.1 模板参数FlatMap的完整模板签名如下flat_map.htemplate typename _K, typename _T, typename _Hash DefaultHasher_K, // 哈希函数 typename _Equal DefaultEqualTo_K, // 相等比较存储的 key 恒在左侧 bool _Sparse false, // 是否为稀疏模式 typename _Alloc PtAllocator, // 分配器 bool _Multi false // 是否允许重复 key class FlatMap;由此派生出几个便捷别名MultiFlatMap_Multitrue允许同一个 key 存多个 valueerase返回删除的个数seek_all返回全部 value 指针见 flat_map.hFlatSet把 value 替换为FlatMapVoid的集合实现见 flat_map.hSparseFlatMap/SparseFlatSet_Sparsetrue用 bit arraythumbnail加速空桶跳过见 flat_map.h。注意源码中的硬性约束存进 FlatMap 的对象必须可拷贝copyable见 flat_map.h。3.2 init 与负载因子int init(size_t nbucket, u_int load_factor 80);nbucket初始桶个数load_factorsize()*100/nbucket的最大值即元素数百分比上限默认 80。当达到该值时桶数会翻倍并对所有元素 rehash这是昂贵操作因此初始参数选得合适能显著减少扩容成本见 flat_map.h。负载因子的判定逻辑在源码中非常直观flat_map_inl.hstatic bool is_too_crowded(size_t size, size_t nbucket, u_int load_factor) { return size * 100 nbucket * load_factor; }init的合法性检查包括load_factor必须在[10, 100]区间、表必须为空且仍在使用默认桶否则直接返回 0flat_map_inl.h。FlatMap 构造后会自动以小表优化默认 16 个桶初始化只有需要大初始桶数或非默认负载因子时才必须调用init返回 0 表示成功、-1 表示失败失败后 map 仍可正常使用。3.3 桶数与哈希取模默认桶数DEFAULT_NBUCKET为 16若编译期定义FLAT_MAP_ROUND_BUCKET_BY_USE_NEXT_PRIME则为 29flat_map.h。扩容时桶数通过flatmap_round计算默认取 2 的幂下限 8也可以切换到下一个素数模式flat_map_inl.h。取模方式相应地为hash_code (nbucket - 1)2 的幂快速取模或hash_code % nbucket素数取模见 flat_map_inl.h。源码注释说明2 的幂取模平均快约 10ns而%的代价不值得只要哈希质量足够好桶数是否素数并不重要——这也提示使用者冲突显著时应考虑换用更好的哈希算法。3.4 增删查改的语义与实现方法语义返回insert(key, value)/insert(pair)插入键值对触发 resize 条件同operator[]插入后的 value 指针失败返回 nullptrflat_map.hoperator[](key)不存在则用默认值插入并返回引用非 Multi 版见 flat_map_inl.hvalue 引用seek(key)只读查找value 指针未命中为 nullptrflat_map_inl.hseek_all(key)Multi 模式下收集同一 key 的全部 valuestd::vectorT*erase(key)非 Multi 返回 1/0是否删除成功Multi 返回删除个数flat_map.hsize_tclear()清空元素不归还已分配内存voidclear_and_reset_pool()清空元素并归还全部内存voidresize(nbucket)手动扩容插入/operator[]也会自动触发boolseek的实现最能体现一次内存跳转原理先flatmap_mod定位桶若桶内首节点无效直接返回 nullptr若首节点命中直接返回其 value 地址只经过一次数组访存否则才沿着first_node.next链表逐节点比较flat_map_inl.h。erase有个值得注意的实现细节当待删除元素恰好是桶内首节点、且桶中还有后继节点时源码不会简单地对节点做内存拷贝注释解释了num_ptr自引用场景下浅拷贝会导致悬垂指针而是通过operator逐个赋值再回收被删除的堆节点flat_map_inl.h。其余辅助接口size()、empty()、bucket_count()、load_factor()、initialized()以及扫描全部桶统计最长桶长/平均桶长的bucket_info()flat_map.h实现见 flat_map_inl.h可用于评估当前哈希分布质量。3.5 小表优化Small Map Optimization构造时 FlatMap 并不立即堆分配而是使用内嵌的_default_buckets[DEFAULT_NBUCKET 1]额外的一个桶用于让迭代器知道桶数组的终点见 flat_map.h。只有元素增多触发 resize 后才切换到堆上的桶数组。对于频繁创建的小字典这避免了大量小内存分配开销。四、设计原理把第一个链表节点放进桶里文档对原理的概括是把开链桶中第一个节点的内容直接放桶内。由于在实践中大部分桶没有冲突或冲突较少所以大部分操作只需要一次内存跳转通过哈希值访问对应的桶。桶内两个及以上元素仍存放在链表中由于桶之间彼此独立一个桶的冲突不会影响其他桶性能很稳定。在很多时候FlatMap 的查找性能和原生数组接近。这一原理在源码中有直接对应的数据结构——Bucketflat_map.hstruct Bucket { Bucket* next; // 指向桶内链表的下一个节点 // ... private: ManualConstructorElement element_space_; // key/value 直接内嵌在桶里 };关键点在于桶数组的每个元素本身就是一个可容纳一对 key/value 的首节点element_space_直接内嵌在桶内。因此无冲突的桶seek一次哈希计算 一次数组访存即返回结果这就是文档所说的查找性能和原生数组接近有冲突的桶桶内首元素仍驻留桶内其余冲突元素挂到next指向的链表上由于桶彼此独立一个桶的冲突完全不影响其他桶平均查找时间稳定代价每个桶都要预留内嵌元素空间当 value 较大、而表内空桶较多时内存浪费明显——这正是用空间换速度的权衡因此文档强调它最适合小字典场景。内存分配层面冲突节点来自SingleThreadedPoolsizeof(Bucket), 1024, 16, allocator_type节点池flat_map.h避免了频繁的堆分配/释放。五、基准测试与其他容器的对比文档记录了一次典型基准运行TRACE 输出value 8/32/128 bytes元素数 100/1000/10000单位 ns/次对比如下容器AlignHashMap闭链开放寻址中较快的实现CowHashMap带 Copy-on-write 逻辑的开链哈希表std::map非哈希表通常是红黑树故列在这里作为有序容器参照。5.1 插入格式顺序 / 随机value 大小元素数FlatMapAlignHashMapCowHashMapstd::map8B10015 / 1419 / 5630 / 29102 / 1578B100010 / 1128 / 1726 / 2793 / 1568B1000010 / 1321 / 2626 / 27130 / 21232B10023 / 2431 / 3231 / 32130 / 18132B100020 / 2153 / 4628 / 35112 / 16832B1000020 / 2446 / 4628 / 31137 / 240128B10034 / 36109 / 11491 / 93179 / 231128B100028 / 4476 / 9486 / 88169 / 224128B1000028 / 4668 / 9287 / 93201 / 3145.2 删除格式顺序 / 随机value 大小元素数FlatMapAlignHashMapCowHashMapstd::map8B1007 / 911 / 1133 / 31146 / 1818B10006 / 69 / 1029 / 30100 / 2048B100005 / 710 / 1130 / 38104 / 30932B1009 / 1011 / 1272 / 32104 / 18232B10007 / 710 / 1029 / 36101 / 20932B100007 / 810 / 1129 / 40112 / 314128B1008 / 911 / 1233 / 35112 / 190128B10008 / 89 / 1030 / 34110 / 236128B100009 / 129 / 1130 / 42125 / 3625.3 查找 seek单位 ns/次value 大小元素数FlatMapAlignHashMapCowHashMapstd::map8B1004712548B10003711788B10000481317232B10058125532B100048118232B1000061014164128B100791356128B10006101293128B1000091221166要点解读查找是 FlatMap 的最大优势无冲突时单次访存8B value 的查找仅需 34ns约为 std::map 的 1/151/40随机删除对开链容器普遍更友好随机删除时 std::map 退化为 300ns 级别value 越大差异越明显128B value 下 FlatMap 插入仍比 std::map 快 47 倍基准也记录了第二次 seek 运行同一组数据重复一轮结果一致均落在 321ns 区间说明结果稳定。注意这些是文档记录的历史运行数据具体数值取决于机器、编译器与哈希函数。当前仓库flat_map_unittest.cpp 中的基准逻辑Sequentially/Randomly inserting、Seeking输出见 test/flat_map_unittest.cpp 与 test/flat_map_unittest.cpp扩展为对比 FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map 七种容器且 flat_map.h 头部注释也记录了一组相同思路的对比数据Seeking 10000 个 8B value 时 FlatMap 约 13ns而 std::unordered_map 约 51107ns。建议在目标机器上自行跑测试验证。六、哈希表全景从哈希函数到冲突解决文档指出哈希表性能差异的本质是把 key 映射到 value的 O(1) 在不同实现间天差地别。实现包含两大部分。6.1 计算哈希值非加密型一个好的非加密哈希算法要考虑结果确定性同一 key 必须恒得同一哈希值雪崩效应输入中一个 bit 的变化应尽量影响输出所有 bit 的变化均匀分布输出应尽量在值域中均匀分布充分利用现代 CPU 特性成块计算、减少分支、循环展开等。大部分哈希算法只针对单个 key本身耗不了太多 CPU性能差异主要来自整体数据分布。工程上最简单的办法也许就有很好的效果通用选择是 Murmurhash 这类算法。FlatMap 在 flat_map.h 的注释中即建议配合 Murmurhash3 获得更好的分布默认的DefaultHasherstd::string则使用经典的乘 101 多项式哈希result result * 101 *i见 flat_map.h对短字符串足够快。你完全可以通过第三个模板参数传入自定义哈希。6.2 解决冲突哈希值必然可能重合冲突解决方式决定了哈希表的整体行为1. 开链哈希open hashing / closed addressing链表的数组链表即桶。若干 key 落到同一桶时做链表插入。这是最通用的结构优点内存占用为O(NumElement * (KeySize ValueSize SomePointers))resize 不会使已有 key/value 内存失效桶之间独立单桶冲突不影响其他桶平均查找时间稳定也易于高并发。缺点是至少要两次内存跳转先跳到桶入口再跳到桶中第一个节点。小表时节点内存接近问题不明显表变大后访存越发随机——一次访存约 50ns2G 左右主频时开链查找往往超过 100ns。在检索端层层 ranking 过程中热点字典每秒可能被查找几百万次以上开链哈希有时会成为热点每对 key/value 额外指针带来的内存开销也常被诟病。2. 闭链哈希closed hashing / open addressing桶不再是链表入口只记录一对 key/value 与一些标记桶被占时按探查方法找空桶如线性探查找下一个桶、二次探查按 1,2,4,9… 平方数位移查找。优点表很空或冲突少时单次访存即完成查找也无需管理节点内存池。但缺点更多桶个数必须大于元素个数resize 后全部旧内存失效难以并发。更关键的是聚集效应区域内元素超过约 70% 时大量元素的实际桶与应有桶产生较大位移主要操作都要扫过一大片内存性能不稳定、难以预测。文档特别提醒闭链哈希在很多人的印象中很快但在复杂应用中往往不如开链甚至可能慢一个数量级。衍生方案如 Hopscotch hashing 试图缓解但工程上未见根本解决。3. 混合开链和闭链把桶数组的一部分拿出来容纳冲突元素典型如 Coalesced hashing。这类结构没有解决开链的内存跳转问题结构又比闭链复杂得多工程效果并不好。4. 多次哈希用多个哈希表代替一个发生冲突时换一个哈希值尝试另一张表典型如 Cuckoo hashing。同样没有解决内存跳转问题。对比之下FlatMap 走的是开链 桶内嵌首节点的路线既保留了开链桶独立、稳定、易并发的优点又用内嵌首节点把最常见的无冲突查找压缩到一次内存跳转从原理上回应了开链哈希最大的短板。七、最佳实践小结综合文档与源码使用 FlatMap 时建议用前评估 value 大小value 较小几十字节内、查找为主、字典规模不大的场景收益最大value 很大时注意内存开销可考虑其他容器提前init根据预估元素数设置初始桶数bucket_count与负载因子默认 80避免运行期多次扩容 rehash查找用seek插入用insert或operator[]operator[]会在 key 不存在时默认构造 value纯查询场景务必用seek遍历中删除必须用 PositionHint先save_iterator删除后再restore_iterator并正确处理返回end()的情况key 类型注意可拷贝约束存进 FlatMap 的对象必须可拷贝flat_map.h哈希冲突大时换哈希函数默认字符串哈希是简单多项式哈希数据分布不佳时可借助模板参数传入 Murmurhash3 等质量更好的哈希并用bucket_info()检查桶长分布。若需查看更完整的接口与使用方式可继续阅读 flat_map.h接口声明与注释、flat_map_inl.h全部实现与 flat_map_unittest.cpp功能与性能测试。【免费下载链接】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 的 butil::FlatMap 深度解析：把开链哈希优化到接近原生数组的查找性能
brpc 的 butil::FlatMap 深度解析把开链哈希优化到接近原生数组的查找性能【免费下载链接】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本文以 brpc 仓库中的 flatmap 文档英文版 docs/en/flatmap.md 目前为未翻译占位页指向中文版为核心结合 flat_map.h、flat_map_inl.h 源码实现与 flat_map_unittest.cpp 测试系统讲解butil::FlatMap的设计原理、完整 API、基准测试结论与哈希表冲突解决全景。读完你将掌握何时该用 FlatMap、如何正确初始化并调用其全部接口、其一次内存跳转原理的源码级依据以及开链/闭链等哈希方案在工程上的取舍。一、FlatMap 是什么butil::FlatMap是 brpc 的底层基础库 butil 提供的高性能 key/value 容器头文件注释对其定位的概括是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.即这是一款闭寻址开链哈希表但把开链桶中第一个节点的内容直接放进桶数组内部从而省掉一次额外的内存间接跳转使几乎所有操作都接近原生数组的性能。它可能是小体积 key/value 场景下最快的哈希表代价是需要更多内存——尤其当 value 较大时。适用场景检索过程中需要极快查找的小字典。在 brpc 内部它被广泛用于这类场景例如controller.h 用butil::FlatMapstd::string, std::string保存用户自定义字段UserFieldsMapextension.h 用butil::CaseIgnoredFlatMapT*管理扩展注册表hpack.cpp 用 FlatMap 与 CaseIgnoredFlatMap 维护 HPACK 头部索引表naming_service_thread.cpp 用 FlatMap 缓存命名服务线程。二、快速上手完整示例文档给出了两个可直接编译运行的示例这里完整保留并逐行注解。2.1 基础增删查改#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); // 插入key 已存在则覆盖 value 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)); // 删除成功返回 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; // 遍历迭代器为 forward iterator } map.clear(); // 清空元素不归还内存 CHECK_EQ(0UL, map.size()); }2.2 遍历中删除PositionHint 方案由于erase()之后iterator可能失效FlatMap 提供了save_iterator/restore_iterator机制在遍历过程中安全删除元素void flatmap_erase_hinted_during_iteration_example() { typedef butil::FlatMapint, int Map; Map map; // bucket_count: 初始桶个数设得足够大以避免 resize。 // load_factor: 元素数 * 100 / 桶数默认 80。 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)); // 删除偶数 key } 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()); }该模式同样被 flat_map_unittest.cpp 中的erase_hinted_during_iteration测试覆盖验证。PositionHint在源码中的定义包含四个字段——nbucket保存时的桶数用于检测 resize、offset当前桶下标、at_entry迭代器是否正指向桶内首节点、key当前 key——见 flat_map.h。restore_iterator的实现逻辑是若hint.nbucket ! _nbucket说明发生了 resize直接从头重新开始若偏移越界则终止迭代否则按at_entry与 key 精确定位恢复见 flat_map_inl.h。三、核心 API 与参数语义源码级3.1 模板参数FlatMap的完整模板签名如下flat_map.htemplate typename _K, typename _T, typename _Hash DefaultHasher_K, // 哈希函数 typename _Equal DefaultEqualTo_K, // 相等比较存储的 key 恒在左侧 bool _Sparse false, // 是否为稀疏模式 typename _Alloc PtAllocator, // 分配器 bool _Multi false // 是否允许重复 key class FlatMap;由此派生出几个便捷别名MultiFlatMap_Multitrue允许同一个 key 存多个 valueerase返回删除的个数seek_all返回全部 value 指针见 flat_map.hFlatSet把 value 替换为FlatMapVoid的集合实现见 flat_map.hSparseFlatMap/SparseFlatSet_Sparsetrue用 bit arraythumbnail加速空桶跳过见 flat_map.h。注意源码中的硬性约束存进 FlatMap 的对象必须可拷贝copyable见 flat_map.h。3.2 init 与负载因子int init(size_t nbucket, u_int load_factor 80);nbucket初始桶个数load_factorsize()*100/nbucket的最大值即元素数百分比上限默认 80。当达到该值时桶数会翻倍并对所有元素 rehash这是昂贵操作因此初始参数选得合适能显著减少扩容成本见 flat_map.h。负载因子的判定逻辑在源码中非常直观flat_map_inl.hstatic bool is_too_crowded(size_t size, size_t nbucket, u_int load_factor) { return size * 100 nbucket * load_factor; }init的合法性检查包括load_factor必须在[10, 100]区间、表必须为空且仍在使用默认桶否则直接返回 0flat_map_inl.h。FlatMap 构造后会自动以小表优化默认 16 个桶初始化只有需要大初始桶数或非默认负载因子时才必须调用init返回 0 表示成功、-1 表示失败失败后 map 仍可正常使用。3.3 桶数与哈希取模默认桶数DEFAULT_NBUCKET为 16若编译期定义FLAT_MAP_ROUND_BUCKET_BY_USE_NEXT_PRIME则为 29flat_map.h。扩容时桶数通过flatmap_round计算默认取 2 的幂下限 8也可以切换到下一个素数模式flat_map_inl.h。取模方式相应地为hash_code (nbucket - 1)2 的幂快速取模或hash_code % nbucket素数取模见 flat_map_inl.h。源码注释说明2 的幂取模平均快约 10ns而%的代价不值得只要哈希质量足够好桶数是否素数并不重要——这也提示使用者冲突显著时应考虑换用更好的哈希算法。3.4 增删查改的语义与实现方法语义返回insert(key, value)/insert(pair)插入键值对触发 resize 条件同operator[]插入后的 value 指针失败返回 nullptrflat_map.hoperator[](key)不存在则用默认值插入并返回引用非 Multi 版见 flat_map_inl.hvalue 引用seek(key)只读查找value 指针未命中为 nullptrflat_map_inl.hseek_all(key)Multi 模式下收集同一 key 的全部 valuestd::vectorT*erase(key)非 Multi 返回 1/0是否删除成功Multi 返回删除个数flat_map.hsize_tclear()清空元素不归还已分配内存voidclear_and_reset_pool()清空元素并归还全部内存voidresize(nbucket)手动扩容插入/operator[]也会自动触发boolseek的实现最能体现一次内存跳转原理先flatmap_mod定位桶若桶内首节点无效直接返回 nullptr若首节点命中直接返回其 value 地址只经过一次数组访存否则才沿着first_node.next链表逐节点比较flat_map_inl.h。erase有个值得注意的实现细节当待删除元素恰好是桶内首节点、且桶中还有后继节点时源码不会简单地对节点做内存拷贝注释解释了num_ptr自引用场景下浅拷贝会导致悬垂指针而是通过operator逐个赋值再回收被删除的堆节点flat_map_inl.h。其余辅助接口size()、empty()、bucket_count()、load_factor()、initialized()以及扫描全部桶统计最长桶长/平均桶长的bucket_info()flat_map.h实现见 flat_map_inl.h可用于评估当前哈希分布质量。3.5 小表优化Small Map Optimization构造时 FlatMap 并不立即堆分配而是使用内嵌的_default_buckets[DEFAULT_NBUCKET 1]额外的一个桶用于让迭代器知道桶数组的终点见 flat_map.h。只有元素增多触发 resize 后才切换到堆上的桶数组。对于频繁创建的小字典这避免了大量小内存分配开销。四、设计原理把第一个链表节点放进桶里文档对原理的概括是把开链桶中第一个节点的内容直接放桶内。由于在实践中大部分桶没有冲突或冲突较少所以大部分操作只需要一次内存跳转通过哈希值访问对应的桶。桶内两个及以上元素仍存放在链表中由于桶之间彼此独立一个桶的冲突不会影响其他桶性能很稳定。在很多时候FlatMap 的查找性能和原生数组接近。这一原理在源码中有直接对应的数据结构——Bucketflat_map.hstruct Bucket { Bucket* next; // 指向桶内链表的下一个节点 // ... private: ManualConstructorElement element_space_; // key/value 直接内嵌在桶里 };关键点在于桶数组的每个元素本身就是一个可容纳一对 key/value 的首节点element_space_直接内嵌在桶内。因此无冲突的桶seek一次哈希计算 一次数组访存即返回结果这就是文档所说的查找性能和原生数组接近有冲突的桶桶内首元素仍驻留桶内其余冲突元素挂到next指向的链表上由于桶彼此独立一个桶的冲突完全不影响其他桶平均查找时间稳定代价每个桶都要预留内嵌元素空间当 value 较大、而表内空桶较多时内存浪费明显——这正是用空间换速度的权衡因此文档强调它最适合小字典场景。内存分配层面冲突节点来自SingleThreadedPoolsizeof(Bucket), 1024, 16, allocator_type节点池flat_map.h避免了频繁的堆分配/释放。五、基准测试与其他容器的对比文档记录了一次典型基准运行TRACE 输出value 8/32/128 bytes元素数 100/1000/10000单位 ns/次对比如下容器AlignHashMap闭链开放寻址中较快的实现CowHashMap带 Copy-on-write 逻辑的开链哈希表std::map非哈希表通常是红黑树故列在这里作为有序容器参照。5.1 插入格式顺序 / 随机value 大小元素数FlatMapAlignHashMapCowHashMapstd::map8B10015 / 1419 / 5630 / 29102 / 1578B100010 / 1128 / 1726 / 2793 / 1568B1000010 / 1321 / 2626 / 27130 / 21232B10023 / 2431 / 3231 / 32130 / 18132B100020 / 2153 / 4628 / 35112 / 16832B1000020 / 2446 / 4628 / 31137 / 240128B10034 / 36109 / 11491 / 93179 / 231128B100028 / 4476 / 9486 / 88169 / 224128B1000028 / 4668 / 9287 / 93201 / 3145.2 删除格式顺序 / 随机value 大小元素数FlatMapAlignHashMapCowHashMapstd::map8B1007 / 911 / 1133 / 31146 / 1818B10006 / 69 / 1029 / 30100 / 2048B100005 / 710 / 1130 / 38104 / 30932B1009 / 1011 / 1272 / 32104 / 18232B10007 / 710 / 1029 / 36101 / 20932B100007 / 810 / 1129 / 40112 / 314128B1008 / 911 / 1233 / 35112 / 190128B10008 / 89 / 1030 / 34110 / 236128B100009 / 129 / 1130 / 42125 / 3625.3 查找 seek单位 ns/次value 大小元素数FlatMapAlignHashMapCowHashMapstd::map8B1004712548B10003711788B10000481317232B10058125532B100048118232B1000061014164128B100791356128B10006101293128B1000091221166要点解读查找是 FlatMap 的最大优势无冲突时单次访存8B value 的查找仅需 34ns约为 std::map 的 1/151/40随机删除对开链容器普遍更友好随机删除时 std::map 退化为 300ns 级别value 越大差异越明显128B value 下 FlatMap 插入仍比 std::map 快 47 倍基准也记录了第二次 seek 运行同一组数据重复一轮结果一致均落在 321ns 区间说明结果稳定。注意这些是文档记录的历史运行数据具体数值取决于机器、编译器与哈希函数。当前仓库flat_map_unittest.cpp 中的基准逻辑Sequentially/Randomly inserting、Seeking输出见 test/flat_map_unittest.cpp 与 test/flat_map_unittest.cpp扩展为对比 FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map 七种容器且 flat_map.h 头部注释也记录了一组相同思路的对比数据Seeking 10000 个 8B value 时 FlatMap 约 13ns而 std::unordered_map 约 51107ns。建议在目标机器上自行跑测试验证。六、哈希表全景从哈希函数到冲突解决文档指出哈希表性能差异的本质是把 key 映射到 value的 O(1) 在不同实现间天差地别。实现包含两大部分。6.1 计算哈希值非加密型一个好的非加密哈希算法要考虑结果确定性同一 key 必须恒得同一哈希值雪崩效应输入中一个 bit 的变化应尽量影响输出所有 bit 的变化均匀分布输出应尽量在值域中均匀分布充分利用现代 CPU 特性成块计算、减少分支、循环展开等。大部分哈希算法只针对单个 key本身耗不了太多 CPU性能差异主要来自整体数据分布。工程上最简单的办法也许就有很好的效果通用选择是 Murmurhash 这类算法。FlatMap 在 flat_map.h 的注释中即建议配合 Murmurhash3 获得更好的分布默认的DefaultHasherstd::string则使用经典的乘 101 多项式哈希result result * 101 *i见 flat_map.h对短字符串足够快。你完全可以通过第三个模板参数传入自定义哈希。6.2 解决冲突哈希值必然可能重合冲突解决方式决定了哈希表的整体行为1. 开链哈希open hashing / closed addressing链表的数组链表即桶。若干 key 落到同一桶时做链表插入。这是最通用的结构优点内存占用为O(NumElement * (KeySize ValueSize SomePointers))resize 不会使已有 key/value 内存失效桶之间独立单桶冲突不影响其他桶平均查找时间稳定也易于高并发。缺点是至少要两次内存跳转先跳到桶入口再跳到桶中第一个节点。小表时节点内存接近问题不明显表变大后访存越发随机——一次访存约 50ns2G 左右主频时开链查找往往超过 100ns。在检索端层层 ranking 过程中热点字典每秒可能被查找几百万次以上开链哈希有时会成为热点每对 key/value 额外指针带来的内存开销也常被诟病。2. 闭链哈希closed hashing / open addressing桶不再是链表入口只记录一对 key/value 与一些标记桶被占时按探查方法找空桶如线性探查找下一个桶、二次探查按 1,2,4,9… 平方数位移查找。优点表很空或冲突少时单次访存即完成查找也无需管理节点内存池。但缺点更多桶个数必须大于元素个数resize 后全部旧内存失效难以并发。更关键的是聚集效应区域内元素超过约 70% 时大量元素的实际桶与应有桶产生较大位移主要操作都要扫过一大片内存性能不稳定、难以预测。文档特别提醒闭链哈希在很多人的印象中很快但在复杂应用中往往不如开链甚至可能慢一个数量级。衍生方案如 Hopscotch hashing 试图缓解但工程上未见根本解决。3. 混合开链和闭链把桶数组的一部分拿出来容纳冲突元素典型如 Coalesced hashing。这类结构没有解决开链的内存跳转问题结构又比闭链复杂得多工程效果并不好。4. 多次哈希用多个哈希表代替一个发生冲突时换一个哈希值尝试另一张表典型如 Cuckoo hashing。同样没有解决内存跳转问题。对比之下FlatMap 走的是开链 桶内嵌首节点的路线既保留了开链桶独立、稳定、易并发的优点又用内嵌首节点把最常见的无冲突查找压缩到一次内存跳转从原理上回应了开链哈希最大的短板。七、最佳实践小结综合文档与源码使用 FlatMap 时建议用前评估 value 大小value 较小几十字节内、查找为主、字典规模不大的场景收益最大value 很大时注意内存开销可考虑其他容器提前init根据预估元素数设置初始桶数bucket_count与负载因子默认 80避免运行期多次扩容 rehash查找用seek插入用insert或operator[]operator[]会在 key 不存在时默认构造 value纯查询场景务必用seek遍历中删除必须用 PositionHint先save_iterator删除后再restore_iterator并正确处理返回end()的情况key 类型注意可拷贝约束存进 FlatMap 的对象必须可拷贝flat_map.h哈希冲突大时换哈希函数默认字符串哈希是简单多项式哈希数据分布不佳时可借助模板参数传入 Murmurhash3 等质量更好的哈希并用bucket_info()检查桶长分布。若需查看更完整的接口与使用方式可继续阅读 flat_map.h接口声明与注释、flat_map_inl.h全部实现与 flat_map_unittest.cpp功能与性能测试。【免费下载链接】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），仅供参考