编程进阶网
杨充
2026-06-06
目录

哈希容器深度剖析

# 36.哈希容器深度剖析

# 目录介绍

# 1. 案例引入

# 1.1 rehash 引发的 P99 延迟风暴

某用户画像系统的标签存储器——用 std::unordered_map<std::string, Profile> 存用户数据。系统启动时批量加载，P99 延迟随机出现 2ms 的尖峰：

// ====== 事故代码 V1：rehash 风暴 ======
std::unordered_map<std::string, Profile> profiles;

void load_batch(const std::vector<Record>& records) {
    for (auto& rec : records) {
        profiles[rec.user_id] = Profile(rec);   // ← 偶发 2ms 延迟
    }
}
// 50 万条记录 → load_factor 从 0 → 1.0 → 触发 rehash → 重新分配 bucket → 重新哈希所有元素
1
2
3
4
5
6
7
8
9

perf 分析：insert 里 85% 的时间花在 _M_rehash 上——不是哈希查找慢，是扩容时要把所有已有元素重新哈希到新 bucket 数组。

量化——50 万条记录，默认最大 load_factor = 1.0，bucket_count 从 0 开始按 ×2 增长。共触发 19 次 rehash。第 19 次 rehash 时 bucket 已有 262144 个元素——全部需要重新计算哈希并搬移到新 bucket → ~1.8ms。

一行修复：

profiles.reserve(500'000);  // 预先分配——一次 rehash 搞定
1

# 1.2 自定义哈希的全部碰撞事故

同一个代码库的自定义类型 OrderKey，作者写了一个哈希函数——但返回值永远是 size_t(0)：

// ====== 事故代码 V2：哈希函数全碰撞 ======
struct OrderKey {
    std::string symbol;
    int         order_id;
};

struct BadHash {
    size_t operator()(const OrderKey& key) const {
        return std::hash<std::string>{}(key.symbol);  // ← 只哈希了 symbol！
        // order_id 被忽略了 → 所有相同 symbol 的订单全冲突
    }
};

std::unordered_map<OrderKey, Order, BadHash> orders;
// 同一 symbol 的 10000 个订单全在同一个 bucket → O(N) 链表遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

performance——10000 次 find：正常哈希 ~12ns → 坏哈希 ~420ns（35× worse）。

# 1.3 七个待解疑问

① 拉链法和开放寻址法是什么? 标准库用哪种? Abseil 用哪种?            → 第 2 / 第 6 章
② std::hash 的默认实现对各种类型安全吗? 怎么自定义哈希?               → 第 4 章
③ load_factor 是什么? rehash 怎么触发? reserve 怎么避免?              → 第 5 章
④ rehash 期间迭代器会失效吗? 和红黑树的迭代器稳定性对比?               → 第 5.4 章
⑤ flat_hash_map 比 unordered_map 快在哪? 什么时候该换?                → 第 6 章
⑥ 异构查找在哈希容器上怎么用? C++20 有什么新能力?                      → 第 7 章
⑦ unordered_map 和 map 到底怎么选? 有没有 benchmark?                   → 第 8 / 第 9 章
1
2
3
4
5
6
7

# 2. 架构概览

# 2.1 哈希表的两大流派

┌─────────────────────────────────────────────────────┐
│              哈希表的两大流派                          │
├──────────────────────────┬──────────────────────────┤
│  ① 拉链法               │  ② 开放寻址法             │
│  (std::unordered_map)   │  (Abseil flat_hash_map)  │
├──────────────────────────┼──────────────────────────┤
│  bucket 数组 + 链表      │  所有元素在一个数组中      │
│  冲突 → 追加到链表头     │  冲突 → 探测下一个位置     │
│  每个节点独立堆分配      │  元数据在连续内存          │
│                          │                          │
│  优点：删除简单           │  优点：缓存极度友好        │
│  缺点：指针追逐+cache差  │  缺点：删除需要 tombstone  │
└──────────────────────────┴──────────────────────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13

# 2.2 为何这么切

疑惑：标准库为什么选拉链法而不是开放寻址？

论证：

  1. 拉链法的迭代器稳定性更好——删除一个元素不会影响其他元素的迭代器（第 5.4 节）。开放寻址删除需要前移元素或留 tombstone。
  2. 拉链法对低质量哈希更宽容——如果哈希函数质量差，拉链法只影响某个桶的遍历长度；开放寻址会导致一连串的探测失败（主聚类）。
  3. 标准库需要通用性——拉链法被证明是「对不同负载和哈希质量都尚可」的方法。开放寻址对哈希分布高度敏感。
  4. 反向验证：Abseil 用开放寻址 + SIMD 探测取得 3× 加速——但加上了严格的约束（需要高质量的哈希+需要重新插入来整理碎片）。

结论：标准库选拉链法是为了「普适性」，Abseil 选开放寻址是为了「极限性能」。两者不是替代关系——是不同场景的优化倾向。

# 3. 拉链法的内部结构

# 3.1 bucket 数组 + 单向链表

std::unordered_map 的内存布局（拉链法）：

bucket 数组 (连续堆内存)
┌──────┬──────┬──────┬──────┬──────┬──────┐
│  *   │  *   │  *   │  *   │  *   │  *   │  ← 每个槽是指向链表头的指针
└──┬───┴──┬───┴──────┴──┬───┴──────┴──────┘
   │      │             │
   ▼      ▼             ▼
┌──────┐┌──────┐     ┌──────┐
│next→││next→│     │next→│
│{k,v}││{k,v}│     │{k,v}│
└──────┘└──────┘     └──────┘
  bucket 0           bucket 3
  (冲突链)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

每个插入的元素是一个独立的堆节点。冲突的元素通过单向链表连接在同一 bucket 下。

# 3.2 libstdc++ 的节点布局

// libstdc++ 的哈希表节点
template <typename T>
struct _Hash_node {
    _Hash_node* _M_next;       // ① 下一节点——8 字节
    T           _M_data;       // ② pair<const K,V> 或 K(set)
};

// unordered_map<int,int>：
//   sizeof(_Hash_node) = 8 + 8(pair<int,int>) = 16 字节
//   加上 allocator metadata(~16B) → 每节点约 32B
1
2
3
4
5
6
7
8
9
10

# 3.3 单节点 vs 红黑树节点的 sizeof 对比

节点 指针数 sizeof(node<int,int>) 说明
unordered_map 1 (next) 16B + meta 单链表
map (红黑树) 3 (parent+left+right) 40B + color 二分搜索树
list 2 (prev+next) 24B 双向链表

哈希表节点最小——只有一个 next 指针。

# 3.4 迭代器与遍历性能

std::unordered_map<int, int> m;
for (auto& [k,v] : m) { ... }
1
2

遍历 = 扫描 bucket 数组 → 遇到非空槽 → 遍历该槽的冲突链 → 继续下一个槽。遍历不是 O(N)——是 O(bucket_count + N)。 如果 bucket 很多空槽（load_factor 低）——遍历的常数因子很大。

# 4. 哈希函数的设计与陷阱

# 4.1 std::hash 的默认实现与弱点

// std::hash 对常见类型的默认实现
std::hash<int>    → return val;          // 恒等——完美分布
std::hash<string> → MurmurHash / city hash 变体——分布良好
std::hash<void*>  → return uintptr_t(val); // 恒等——依赖地址分布

// ⚠️ 没有默认实现的类型：
std::hash<pair<int,int>>    // ❌ C++14 之前——没有
std::hash<vector<int>>      // ❌ 永远没有
1
2
3
4
5
6
7
8

# 4.2 自定义哈希的正确姿势

struct Point { int x, y; };

struct PointHash {
    size_t operator()(const Point& p) const noexcept {
        // ① 用两个 int 组合一个 hash——避免碰撞
        size_t h1 = std::hash<int>{}(p.x);
        size_t h2 = std::hash<int>{}(p.y);
        // ② 黄金比例的混合
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

struct PointEqual {
    bool operator()(const Point& a, const Point& b) const noexcept {
        return a.x == b.x && a.y == b.y;
    }
};

std::unordered_map<Point, int, PointHash, PointEqual> grid;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

关键原则：

  1. hash(x) != hash(y) 必须推出 x != y（反之不必）
  2. 同等键必须哈希相同——(a==b) → hash(a)==hash(b)
  3. hash 和 equal 的函数签名必须一致

# 4.3 几个常见哈希的分布质量实测

哈希方式 10000 int 随机分布 string 分布 说明
std::hash<int> 均匀 — int 恒等就是完美哈希
std::hash<string> — 良好 MurmurHash 变体
return x % 1024 差 — 忽略高位——碰撞多
return 0 全碰撞 全碰撞 灾难——退化为链表 O(N)

# 4.4 哈希冲突的退化与 hash flooding 攻击

// 恶意输入——构造 N 个碰撞键
std::vector<std::string> keys = {"Aa", "BB", "C#", ...};  // 保证 hash 相同
for (auto& k : keys) m[k] = 0;
// N 个键全在同一个 bucket → 插入/查找变成 O(N)
1
2
3
4

这是网络安全领域真实存在的攻击向量。C++ 标准库在 C++14 之后引入了随机种子（per-process salt）缓解此攻击——但自定义哈希函数需自己关注。

# 4.5 为什么自定义哈希是「正确性+性能」的双重入口

疑惑：哈希函数不好——反正还有 equal 函数兜底，最多慢一点？

论证——三个层次的影响：

层次 1：性能退化
  哈希碰撞 → 冲突链变长 → find 从 O(1) 退化为 O(L)（L=链长）

层次 2：hash flooding
  攻击者刻意构造碰撞 → 单个 bucket 堆积 10000+ 元素
  → find 从 ~12ns 退化为 ~5000ns（400× worse）
  → 一个请求就能打爆服务

层次 3：语义错误
  hash(a) != hash(b) 但 equal(a,b) == true
  → 两个键被放到不同 bucket
  → find(b) 在 bucket(hash(b)) 找不到已存在的 a
  → insert(b) 作为新元素插入 → 出现重复键！
  → unordered_set 不再是「集合」——语义崩塌
1
2
3
4
5
6
7
8
9
10
11
12
13
14

所以自定义哈希必须遵守铁律：equal(a,b) == true → hash(a) == hash(b)。 这是哈希函数正确性的充要条件——不是性能指南，是逻辑必需。

# 5. load_factor 与 rehash 的全过程

# 5.1 load_factor 的含义与默认值

load_factor = size() / bucket_count()

// 默认 max_load_factor = 1.0（GCC/Clang/MSVC 均如此）
// 当 load_factor > max_load_factor → 触发 rehash
1
2
3
4

# 5.2 rehash 的完整步骤拆解

rehash 的完整流程：

① 计算 new_bucket_count = max(old × 2, size/max_load_factor)
   → GCC: new_bucket_count = 下一个质数（为了减少哈希取模的碰撞）

② 分配新 bucket 数组

③ 遍历旧 bucket 数组的每个槽：
   遍历该槽的冲突链上的每个节点：
     计算 hash(node.key) % new_bucket_count → 新槽位
     头插到新槽位的链表

④ 释放旧 bucket 数组

⑤ 更新内部成员：_M_buckets, _M_bucket_count

总代价：对已有所有元素重新哈希 + O(bucket_count) 的分配和释放
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第 ③ 步是延迟的来源——N 个已有元素全部重新计算哈希并搬移。

# 5.3 reserve 与 rehash 的性能对比

std::unordered_map<int, int> m;

// 方式 A：依赖 rehash——19 次自动扩容
for (int i = 0; i < 500'000; ++i) m[i] = i;  // 总时间 ~48 ms

// 方式 B：一次 reserve
m.reserve(500'000);
for (int i = 0; i < 500'000; ++i) m[i] = i;  // 总时间 ~12 ms
                                              // → 4× 加速
1
2
3
4
5
6
7
8
9

reserve(n) 保证 bucket_count >= n / max_load_factor + 1——只做一次分配，消除所有中间 rehash。

# 5.4 rehash 期间的迭代器失效规则

操作 unordered_map map
insert（不触发 rehash） ✅ ✅
insert（触发 rehash） ❌ 全部失效 ✅
erase(it) 仅 it 失效 仅 it 失效

这是哈希表 vs 红黑树的最严重差距——rehash 让所有迭代器、引用、指针全部作废。

# 6. 开放寻址与 flat_hash_map

# 6.1 开放寻址的原理

拉链法 (std::unordered_map)：
  bucket[hash % N] → node1 → node2 → node3 (链表)

开放寻址 (Abseil flat_hash_map)：
  所有元素存储在连续数组中
  查找 slot = hash % N
  如果 slot 被占 → 探测 slot+1 → slot+2 → ...
  直到找到 key 或 遇到空槽
1
2
3
4
5
6
7
8

开放寻址的致命问题——删除不能留空洞：

数组：[A] [B] [ ] [C] (被删除的 B 留下空洞)
查找 C：hash(C) → slot 1 → 被占且 ≠ C → 探测 slot 2 → 空槽 → 停止！
但 C 在 slot 3！→ 因为 slot 2 是空槽，终止了探测 → 找不到 C！

解决方案：tombstone（墓碑标记）
  slot 2 标为 TOMBSTONE → 查找跳过墓碑继续探测
  → 但墓碑积累 → 数组越来越多空洞 → 定期 rehash 清除
1
2
3
4
5
6
7

# 6.2 Abseil SwissTable 设计——为什么快 3×

SwissTable 的四大优化支柱：

① 元数据分离 (metadata separation)
  ctrl 字节数组和 slots 数组分离存储
  → 在探测阶段只访问 ctrl（每 slot 1 字节）——不碰 8/16 字节的 key+value
  → 探测带宽从 ~64B/步 降到 ~16B/步

② SIMD 并行探测
  一次 load 16 字节 = 16 个 slot 的 ctrl
  一次 cmp = 16 路并行比较
  一次 movemask = 提取所有命中位置
  → 16 个 slot 用 3 条指令完成——而不是 16 条

③ 7 位哈希指纹 (h2)
  key 的哈希分两段：h1(57位)→选组, h2(7位)→存 ctrl 用于快速过滤
  找到匹配 h2 的 slot 后，才读出 key 做完整比较
  → 99% 的 probe 命中和 miss 都不需要读 key+value

④ 墓碑延迟清理
  删除不标记 tombstone——标记为空槽
  然后从邻域「借用」元素过来填充空位
  → 避免墓碑积累——但增加了删除复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SwissTable 的 ctrl 字节编码：

每个 slot 有一个 ctrl 字节：
  0xxxxxxx → 被占用，存储 h2（哈希的 7 位指纹）
  10000000 → EMPTY（从未被占用）
  11111110 → DELETED（墓碑——被删过）
  11111111 → SENTINEL（组末尾哨兵——终止探测）

find 流程：
  ① h1 = hash >> 7 → 选组
  ② h2 = hash &amp; 0x7F → 7 位指纹
  ③ 在组内 SIMD 查找所有 ctrl == h2 的 slot
  ④ 对匹配的 slot，读出 key 做完整比较
  ⑤ 如果遇到 EMPTY → 未找到（无需比较 key）
1
2
3
4
5
6
7
8
9
10
11
12

# 6.3 与 std::unordered_map 的性能对决

操作 unordered_map flat_hash_map 加速比
insert 100K (int) 8 ms 3.2 ms 2.5×
find 100K (int) 2.1 ms 0.9 ms 2.3×
find 100K (string) 21 ms 8 ms 2.6×
erase 100K 5 ms 2.8 ms 1.8×
遍历 100K 3.8 ms 0.6 ms 6.3×

遍历的 6× 加速是开放寻址的绝对优势——所有元素在连续内存中，cache line 利用率接近 100%。

# 6.4 什么时候应该换用 flat_hash_map

场景 推荐
高频率 find + 高频率遍历 flat_hash_map
需要迭代器稳定性（erase 不影响其他迭代器） unordered_map
需要 C++14 兼容 unordered_map
元素很大 (>64B) flat_hash_map（连续存储更友好）
需要 extract/node_type unordered_map

# 7. 自定义哈希容器的高级技巧

# 7.1 自定义 hash + equal_to 的正确配法

// 五个模板参数——完整的哈希容器定制
std::unordered_map<
    Key, T,
    Hash,        // ③ 哈希函数
    KeyEqual,    // ④ 相等比较
    Allocator    // ⑤ 分配器
> m;
1
2
3
4
5
6
7

必须同时定制 hash 和 equal——如果只改 hash 而不改 equal，默认的 std::equal_to<Key> 用 operator==——和你的 hash 逻辑可能不匹配。

# 7.2 异构查找的哈希版(C++20)

// C++20：哈希容器也支持异构查找了
struct StringHash {
    using is_transparent = int;  // ← 启用异构

    size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
    size_t operator()(const std::string& s) const noexcept {
        return std::hash<std::string>{}(s);
    }
};

struct StringEqual {
    using is_transparent = int;  // ← 启用异构
    bool operator()(std::string_view a, std::string_view b) const noexcept {
        return a == b;
    }
};

std::unordered_map<std::string, int, StringHash, StringEqual> m;
auto it = m.find("literal");  // ✅ C++20——零临时对象！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

注意：hash 函数和 equal 函数都必须有 is_transparent 标签。

# 7.3 内存池 + 哈希表的组合优化

// 用 PMR 避免反复 new/delete 节点
std::array<std::byte, 1'000'000> buffer;
std::pmr::monotonic_buffer_resource pool(buffer.data(), buffer.size());
std::pmr::unordered_map<int, std::pmr::string> m(&pool);

// 所有节点分配都在 pool 的连续内存中——零系统调用
for (int i = 0; i < 100'000; ++i) m[i] = std::to_string(i);
// → 一次 delete（pool 析构）释放所有节点
1
2
3
4
5
6
7
8

# 8. 与红黑树的完整对决

# 8.1 时间复杂度对比

操作 unordered_map map
find O(1) 平均, O(N) 最坏 O(log N)
insert O(1) 平均, O(N) 最坏 O(log N)
erase O(1) 平均 O(log N)
遍历 O(bucket_count+N) O(N)——中序天然有序

# 8.2 缓存与内存占用对比

容器 per-node 大小(int→int) 内存连续性 遍历速度
unordered_map ~32B ❌ 散落 ~4 ms/100K
map ~56B ❌ 散落 ~4 ms/100K
flat_hash_map ~12B ✅ 连续 ~0.6 ms/100K

# 8.3 选型决策树

需要有序遍历?
├─ 是 → map（唯一选择）
└─ 否 → 需要 O(1) 平均查找?
         ├─ 是 → key 的哈希便宜?
         │        ├─ 是 → unordered_map / flat_hash_map
         │        └─ 否 → 考虑 map（哈希开销可能 > O(log N) 比较）
         └─ 否 → map
1
2
3
4
5
6
7

# 9. 汇编全景与 benchmark

# 9.1 find 的哈希+链查找指令序列

auto it = m.find(42);
1

GCC 13.2 -O2 (unordered_map<int,int>)：

; ① 计算 hash（int → 恒等）
    mov   ecx, 42

; ② 取模：bucket_idx = hash % bucket_count
    xor   edx, edx
    div   r8d                      ; edx = 42 % bucket_count

; ③ 读 bucket[idx]
    mov   rax, [rdi + rdx*8]       ; bucket[idx] → 链表头指针

; ④ 遍历链表
.Lchain_loop:
    test  rax, rax
    je    .Lnot_found
    cmp   DWORD [rax+8], 42        ; node->key == 42? (偏移 8=跳过 next 指针)
    je    .Lfound
    mov   rax, [rax]               ; node = node->_M_next
    jmp   .Lchain_loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

和 map 的 find 对比（55 行→5 行；vs 红黑树的 4-5 条指令循环）——链表的链查找是指令级更简单的，但 O(1) bucket 定位是哈希表的关键优势。

# 9.2 rehash 的指令序列

; rehash——分配新 bucket + 遍历所有节点重新哈希
    ; ① 分配 new_bucket 数组
    call  operator new[]

    ; ② 遍历旧 bucket（循环）
.Lrehash_loop:
    ;   取旧 bucket[i] → 遍历链表 → 对每个节点：
    ;     计算 hash(key) % new_bucket_count
    ;     头插到新 bucket
    ;   循环所有旧 bucket

    ; ③ 释放旧 bucket
    call  operator delete[]
1
2
3
4
5
6
7
8
9
10
11
12
13

# 9.3 五场景 benchmark

100K 元素，GCC 13.2 -O2：

操作 unordered_map map flat_hash_map
insert 8 ms 12 ms 3.2 ms
find 命中 2.1 ms 3.2 ms 0.9 ms
find 未命中 1.8 ms 5.1 ms 0.7 ms
erase 5 ms 9 ms 2.8 ms
遍历 3.8 ms 4.2 ms 0.6 ms

# 10. 综合案例串讲

# 10.1 案例真相揭晓

# 疑问 答案
① 拉链法 vs 开放寻址? 第 2/6 章：标准库用拉链法（普适性），Abseil 用开放寻址（极限性能）
② 自定义哈希? 第 4 章：std::hash 覆盖基础类型；自定义需 hash+equal 配对
③ load_factor / rehash? 第 5 章：>1.0 触发 rehash——重新分配+重新哈希全部元素
④ rehash 迭代器? 第 5.4：rehash→全部失效；erase→仅被删者失效
⑤ flat_hash_map 快在哪? 第 6 章：SIMD 探测 + 连续存储——遍历 6×、find 2.3×
⑥ 哈希异构查找? 第 7 章：C++20 hash+equal 都需 is_transparent
⑦ unordered vs map 选? 第 8/9 章：需有序→map；键哈希贵且 N<1000→考虑 map

案例①修复（rehash 风暴）：reserve(500'000)——总时间从 48ms→12ms。

案例②修复（全碰撞）：hash 函数混合两个字段——order_id 参与计算。

# 10.2 一次 unordered_map::find 的完整旅程

auto it = m.find(42);

① hash(42) → 42（int 恒等）
② bucket_idx = 42 % 13 = 3
③ bucket[3] → 链表头节点
④ 沿链表遍历，比较每个 node->key == 42
⑤ 找到 → 返回迭代器；找不到 → end()

总指令：① 1 条 mov，② 2 条 (div)，③ 1 条 mov，④ 循环 1-2 次 cmp+jmp
1
2
3
4
5
6
7
8
9

# 10.3 设计哲学回扣

哲学 1：O(1) 不等于快——哈希函数的常数因子会逆转复杂度优势

std::hash<string> 不是免费的——它需要遍历字符串的每个字符。对于短键和中型 N，红黑树的 O(log N) 廉价字符串比较可能比 O(1) 哈希更快。好的性能分析不只看复杂度首位——也看常数因子。

哲学 2：缓存 > 算法——flat_hash_map 证明了这个真理

Abseil flat_hash_map 和 unordered_map 的算法复杂度完全相同（都是拉链 vs 探测的 O(1) 哈希表）。但 flat_hash_map 快 3×——**只因数据结构布局更友好于 CPU 缓存。 连续内存上的开放寻址 > 散落堆上的指针追逐——在现代 CPU 上，缓存比算法指挥棒更大。

哲学 3：rehash 是哈希表的「vector 扩容」——但搬移的是更贵的对象

vector 扩容搬移元素（连续 memcpy）。unordered_map 扩容搬移节点（每个节点独立计算哈希 + 取模——每条链都要重新链接）。reserve 对哈希表的价值甚至大于对 vector——它省的不仅是分配，还有 N 次哈希重新计算。

哲学 4：哈希函数的正确性是逻辑正确——不是性能优化

如果一个哈希函数对相等的键返回不同哈希——程序可能逻辑正确但性能退化到 O(N)。如果一个哈希函数让 N 个不同键全碰撞——程序可能可运行但消耗百倍时间。哈希是正确性和性能的双重入口——坏哈希没法通过优化弥补。

# 10.4 速查表合集

哈希容器关键 API：

API 含义
reserve(n) 保证 bucket_count >= n/max_load_factor+1
rehash(n) 强制设置 bucket_count = n（至少）
max_load_factor(f) 设置触发 rehash 的阈值
load_factor() 当前 size()/bucket_count()
bucket_count() 当前 bucket 槽数
bucket_size(i) 第 i 个 bucket 的冲突链长度

unordered_map vs flat_hash_map 一句话：

需要迭代器稳定 → unordered_map
需要高性能遍历+查找 → flat_hash_map
C++14 兼容 → unordered_map
元素超大(>64B) → flat_hash_map
1
2
3
4

下一篇：哈希表的内部结构说清了。下一篇进入 37.迭代器五大类别——input/output/forward/bidirectional/random 五种 iterator tag 的分派机制、ranges 视图如何复合迭代器、迭代器失效的完整族谱。

上次更新: 2026/06/10, 11:13:41
关联容器红黑树
迭代器五大类别

← 迭代器五大类别→

最近更新
01
信号崩溃快速排查
06-15
02
CoreDump破案
06-15
03
perf火焰图实战
06-15
更多文章>
Theme by Vdoing | Copyright © 2019-2026 杨充 | MIT License | 桂ICP备2024034950号 | 桂公网安备45142202000030