企业官网建设流程全解析

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::FlatMap<std::string, std::string>保存用户自定义字段UserFieldsMap；
• extension.h 用butil::CaseIgnoredFlatMap<T*>管理扩展注册表；
• 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::FlatMap<int, 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::FlatMap<int, 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::FlatMap<int, 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.h）：

template <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：_Multi=true，允许同一个 key 存多个 value，erase返回删除的个数，seek_all返回全部 value 指针，见 flat_map.h；
• FlatSet：把 value 替换为FlatMapVoid的集合实现，见 flat_map.h；
• SparseFlatMap/SparseFlatSet：_Sparse=true，用 bit array（thumbnail）加速空桶跳过，见 flat_map.h。

注意源码中的硬性约束：存进 FlatMap 的对象必须可拷贝（copyable），见 flat_map.h。

3.2 init 与负载因子

int init(size_t nbucket, u_int load_factor = 80);

• nbucket：初始桶个数；
• load_factor：size()*100/nbucket的最大值，即"元素数百分比上限"，默认 80。当达到该值时桶数会翻倍并对所有元素 rehash，这是昂贵操作，因此初始参数选得合适能显著减少扩容成本，见 flat_map.h。

负载因子的判定逻辑在源码中非常直观（flat_map_inl.h）：

static 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]区间、表必须为空且仍在使用默认桶，否则直接返回 0（flat_map_inl.h）。FlatMap 构造后会自动以小表优化（默认 16 个桶）初始化，只有需要大初始桶数或非默认负载因子时才必须调用init，返回 0 表示成功、-1 表示失败（失败后 map 仍可正常使用）。

3.3 桶数与哈希取模

默认桶数DEFAULT_NBUCKET为 16；若编译期定义FLAT_MAP_ROUND_BUCKET_BY_USE_NEXT_PRIME则为 29（flat_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 增删查改的语义与实现

seek的实现最能体现"一次内存跳转"原理：先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 的查找性能和原生数组接近。

这一原理在源码中有直接对应的数据结构——Bucket（flat_map.h）：

struct Bucket { Bucket* next; // 指向桶内链表的下一个节点 // ... private: ManualConstructor<Element> element_space_; // key/value 直接内嵌在桶里 };

关键点在于：桶数组的每个元素本身就是一个"可容纳一对 key/value 的首节点"，element_space_直接内嵌在桶内。因此：

• 无冲突的桶：seek一次哈希计算 + 一次数组访存即返回结果，这就是文档所说的"查找性能和原生数组接近"；
• 有冲突的桶：桶内首元素仍驻留桶内，其余冲突元素挂到next指向的链表上；由于桶彼此独立，一个桶的冲突完全不影响其他桶，平均查找时间稳定；
• 代价：每个桶都要预留内嵌元素空间，当 value 较大、而表内空桶较多时内存浪费明显——这正是"用空间换速度"的权衡，因此文档强调它最适合"小字典"场景。

内存分配层面，冲突节点来自SingleThreadedPool<sizeof(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 插入（格式：顺序 / 随机）

5.2 删除（格式：顺序 / 随机）

5.3 查找 seek（单位 ns/次）

要点解读：

1. 查找是 FlatMap 的最大优势：无冲突时单次访存，8B value 的查找仅需 3～4ns，约为 std::map 的 1/15～1/40；
2. 随机删除对开链容器普遍更友好（随机删除时 std::map 退化为 300ns 级别）；
3. value 越大差异越明显：128B value 下 FlatMap 插入仍比 std::map 快 4～7 倍；
4. 基准也记录了第二次 seek 运行（同一组数据重复一轮，结果一致，均落在 3～21ns 区间），说明结果稳定。

注意：这些是文档记录的历史运行数据，具体数值取决于机器、编译器与哈希函数。当前仓库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 约 51～107ns）。建议在目标机器上自行跑测试验证。

六、哈希表全景：从哈希函数到冲突解决

文档指出：哈希表性能差异的本质，是"把 key 映射到 value"的 O(1) 在不同实现间天差地别。实现包含两大部分。

6.1 计算哈希值（非加密型）

一个好的非加密哈希算法要考虑：

• 结果确定性：同一 key 必须恒得同一哈希值；
• 雪崩效应：输入中一个 bit 的变化应尽量影响输出所有 bit 的变化；
• 均匀分布：输出应尽量在值域中均匀分布；
• 充分利用现代 CPU 特性：成块计算、减少分支、循环展开等。

大部分哈希算法只针对单个 key，本身耗不了太多 CPU，性能差异主要来自整体数据分布。工程上"最简单的办法也许就有很好的效果"，通用选择是 Murmurhash 这类算法。FlatMap 在 flat_map.h 的注释中即建议配合 Murmurhash3 获得更好的分布；默认的DefaultHasher<std::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 内存失效；桶之间独立，单桶冲突不影响其他桶，平均查找时间稳定，也易于高并发。缺点是至少要两次内存跳转：先跳到桶入口，再跳到桶中第一个节点。小表时节点内存接近，问题不明显；表变大后访存越发随机——一次访存约 50ns（2G 左右主频）时，开链查找往往超过 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 时建议：

1. 用前评估 value 大小：value 较小（几十字节内）、查找为主、字典规模不大的场景收益最大；value 很大时注意内存开销，可考虑其他容器；
2. 提前init：根据预估元素数设置初始桶数（bucket_count）与负载因子（默认 80），避免运行期多次扩容 rehash；
3. 查找用seek，插入用insert或operator[]：operator[]会在 key 不存在时默认构造 value，纯查询场景务必用seek；
4. 遍历中删除必须用 PositionHint：先save_iterator，删除后再restore_iterator，并正确处理返回end()的情况；
5. key 类型注意可拷贝约束：存进 FlatMap 的对象必须可拷贝（flat_map.h）；
6. 哈希冲突大时换哈希函数：默认字符串哈希是简单多项式哈希，数据分布不佳时可借助模板参数传入 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