unordered_map底层原理

c++ › 随笔

unordered_map底层原理

  1. unordered_map 和 map 的底层区别是什么
  2. unordered_map 为什么平均查找是 O(1)，但最坏可能退化成 O(n)
  3. 它底层一般由哪两部分组成
    • bucket 数组
    • 节点/链表（或等价结构）
  4. 插入一个元素时，大致流程是什么
    • 先算 hash
    • 再映射到 bucket
    • 再处理冲突
  5. 哈希冲突一般怎么处理
    • 拉链法
    • 开放寻址你也可以顺带讲一下，但重点说标准库常见实现思路
  6. 什么是负载因子 load_factor
  7. 什么是 max_load_factor
  8. 什么时候会触发 rehash
  9. rehash 时发生了什么，为什么代价大
  10. 哪些操作可能导致迭代器失效

下面开始追问，按真实面试官的方式压你。

追问 1

请你说一下：

1
unordered_map<int, int> mp;

插入第一个元素时，底层大概做了什么？

我想听到这种层次：

  • hash 函数先算出 key 的哈希值
  • 根据 bucket_count 映射到某个桶
  • 桶里没有就挂进去
  • 有冲突就接到链上或放到等价结构里

但你不能只背流程，你要解释为什么这样设计。

追问 2

为什么 unordered_map 需要 rehash？

如果不 rehash 会怎样？

你要把下面几个点说清楚：

  • bucket 太少时，冲突会变多
  • 链会变长
  • 查找效率下降
  • 所以要扩桶并重新分布元素

追问 3

rehash 是不是把元素“重新拷贝一遍”那么简单？

你要回答：

  • 节点本身会不会重新构造
  • 是重新分配节点，还是更多在“重挂链/重分桶”
  • 为什么 rehash 后元素位置变了，迭代器容易失效

追问 4

为什么说 unordered_map 不能保证遍历顺序稳定？

如果插入了一些元素之后又触发 rehash，遍历顺序可能发生什么变化？

追问 5

unordered_map 的 key 为什么要求能比较“相等”？

也就是说，为什么除了哈希函数，还需要相等判断函数 key_equal？

我希望你能讲出这个意思：

  • 哈希相同不代表 key 一定相等
  • 最终还要靠相等比较确认是不是同一个 key

追问 6

最坏复杂度为什么会退化到 O(n)？

什么情况下会出现这种事？

继续往下答：

  • 大量 key 落到同一个桶
  • 哈希函数设计不好
  • 恶意输入攻击

追问 7

工程里怎么降低哈希退化风险？

你可以从这些方向讲：

  • 选择更好的哈希函数
  • 避免用户可控输入直接用脆弱哈希
  • 对字符串等类型使用更稳健的散列
  • 在高安全场景防御碰撞攻击

小追问 1

unordered_map 的元素在内存里是连续的吗？为什么？

小追问 2

为什么 unordered_map 不适合做范围查询，而 map 更适合？

小追问 3

operator[] 和 find() 在 unordered_map 上有什么区别？

我不是要你只答“一个会插入，一个不会”，我要你说清楚：

  • operator[] 对不存在 key 的行为
  • 为什么会要求 mapped type 可默认构造
  • 在工程里什么时候更适合用 find

一、unordered_map 底层一般由哪两部分组成

我会把它理解成两层结构：

1. bucket 数组

你可以把它理解成“桶数组”。
每个桶对应一个槽位，用来表示“哈希到这一类的位置”。

2. 节点结构

真正的元素通常不是直接连续塞在 bucket 数组里的，而是以节点形式存在。
每个节点里通常至少有：

  • key
  • value
  • 节点链接信息，比如 next 指针，或者等价的链式组织方式

标准库常见实现思路一般更接近：

bucket 数组 + 节点链式组织

也就是常说的拉链法。

二、为什么平均查找是 O(1)，最坏可能是 O(n)

平均 O(1) 的原因是：

  • 先对 key 做哈希
  • 再把哈希值映射到某个 bucket
  • 理想情况下，一个桶里元素很少，甚至只有 0 个或 1 个
  • 那查找基本就是常数级

但最坏会退化到 O(n)，因为如果很多 key 都落到同一个桶里，那你虽然表面上有很多 bucket，但实际某个桶里的链会特别长。
这时候查找就变成了沿着一条长链逐个比较，复杂度接近线性。

所以 unordered_map 的 O(1) 是平均复杂度，不是严格最坏复杂度保证。

三、插入一个元素时，大致流程是什么

如果我写：

1
2
unordered_map<int, int> mp;
mp[10] = 20;

底层大致可以理解成这样：

第一步，先对 key，也就是 10，调用哈希函数算出一个哈希值。
比如 std::hash<int>{}(10)。

第二步，把这个哈希值映射到某个 bucket。
常见理解方式就是：

1
bucket_index = hash % bucket_count

实际实现可能不一定逐字这么写，但你可以这么理解它的本质。

第三步，去这个 bucket 对应的位置看有没有元素。
如果没有，那就直接把新节点挂进去。
如果有元素，就说明可能发生了哈希冲突，这时会在这个桶对应的链上继续找：

  • 如果发现已经有相同 key，就更新 value 或插入失败，取决于接口
  • 如果没有相同 key，就把新节点接到这个桶对应的链式结构里

为什么这样设计？因为 bucket 数组本身只是一个“分类入口”，不可能无限大，也不可能保证每个不同 key 都独占一个位置，所以冲突是常态。拉链法的好处是实现简单，插入删除局部代价也比较自然。

四、哈希冲突一般怎么处理

最常见、最适合回答标准库实现思路的是：

拉链法

也就是一个 bucket 里挂一串节点。
哈希到同一个桶的元素，都放到这一桶对应的链或等价结构中。

比如：

1
bucket[3] -> node1 -> node2 -> node3

查找时就先定位桶，再在桶内顺着链找。

开放寻址

这个也可以顺带提一句。它不是每个桶挂链，而是如果当前位置冲突，就继续探测别的位置，比如线性探测、二次探测、双重哈希。
不过标准库 unordered_map 常见实现思路更接近节点 + bucket + 拉链/链式组织这一套，所以面试重点说拉链法更稳。

五、什么是 load_factor 和 max_load_factor

load_factor

负载因子，本质上就是：

1
size / bucket_count

也就是平均每个桶里大概装了多少个元素。

如果负载因子太高，说明桶太少、元素太多，冲突会明显变多。

max_load_factor

最大负载因子阈值。
它表示你允许平均每个桶最多装到什么程度。

一旦实际负载因子超过这个阈值，容器通常就会考虑扩桶，也就是触发 rehash。

六、什么时候会触发 rehash

通常是当元素越来越多，导致：

1
load_factor() > max_load_factor()

这时候如果还不扩桶，冲突会越来越严重，桶内链越来越长，平均查找效率就会下降。

所以 unordered_map 需要 rehash，本质上就是为了：

通过增加 bucket 数量，把已有元素重新分散开，降低冲突。

七、rehash 时发生了什么，为什么代价大

rehash 不是简单“桶数组长度改个数”就完了。
它通常要做的是：

  1. 申请新的、更大的 bucket 数组
  2. 遍历原来所有元素
  3. 对每个元素根据新的 bucket_count 重新计算映射桶位置
  4. 把节点重新挂到新的 bucket 体系里

为什么代价大？因为它要把所有元素都重新分布一遍，时间复杂度接近 O(n)。
而且如果元素很多，这一步会比较重，所以 rehash 往往是平时平均 O(1) 背后偶尔出现的一次“大动作”。

八、哪些操作可能导致迭代器失效

最典型的是：

  • rehash
  • reserve
  • 某些插入操作如果触发了 rehash

因为一旦重分桶，元素在哈希表内部的组织位置会发生明显变化，所以迭代器通常容易失效。

删除某个元素时，通常至少指向被删元素的那个迭代器会失效。
但大范围失效最值得强调的就是 rehash 导致的失效。

追问 1：插入第一个元素时，底层大概做了什么？

如果面试官追这个，我会这样说：

1
unordered_map<int, int> mp;

刚创建出来时，它内部会有一套初始 bucket 结构，具体 bucket 数量和实现有关，可能是 0，也可能是一个初始桶数，标准不强制写死。

当你插入第一个元素时，底层大致会做：

第一，调用哈希函数，把 key 算出哈希值。
第二，根据当前 bucket_count 把哈希值映射到某个桶。
第三，如果这个桶里还没有元素，那就新建一个节点，把它挂进去。
第四，如果桶里已有元素，那就在该桶对应链上看是否 key 相等，有冲突就继续处理。

为什么这么设计？因为哈希表的核心思想不是“直接按 key 存”，而是先把 key 映射到一个有限桶空间里。这样查找时不需要全表扫描，只需要先定位到某一类，再在这一类里局部查找，平均效率就很高。

追问 2：为什么需要 rehash？如果不 rehash 会怎样？

这个我会直接说：

rehash 的根本原因是桶数量是有限的，而元素会持续增多。
如果 bucket 太少，越来越多元素会落到同一个桶里，于是：

  • 哈希冲突变多
  • 链变长
  • 桶内查找变慢
  • 平均 O(1) 会越来越接近线性

所以必须通过扩桶，让元素重新分布得更均匀。
也就是：

桶太少 -> 冲突变多 -> 链变长 -> 查找变慢 -> 需要 rehash

追问 3：rehash 是不是把元素“重新拷贝一遍”那么简单？

我会说，不要把它粗暴理解成“把 value 全重新构造一遍”。

更准确地说，标准库常见实现思路里，unordered_map 的元素通常本来就是一个个独立节点。
所以 rehash 更像是：

重新分桶、重挂链

也就是：

  • 新建一套 bucket 数组
  • 原来的节点根据新 bucket_count 重新找到该去哪个桶
  • 再把这些节点重新链接到新桶体系里

很多实现里，重点不在“把每个节点对象重新构造一遍”，而在于节点组织关系改变了。
所以它更像“节点迁移/重挂接”，而不是简单值拷贝。

为什么迭代器容易失效？因为迭代器往往依赖当前内部组织方式。一旦元素被重新分布到新的 bucket，节点间的链接关系、桶入口关系都变了，所以原有迭代器语义就很容易失效。

追问 4：为什么说 unordered_map 不能保证遍历顺序稳定？

因为它本来就不是有序结构。
遍历顺序通常取决于：

  • bucket 的顺序
  • 每个 bucket 里节点的组织顺序
  • 当前是否发生过 rehash

所以你插入一些元素以后，如果又触发了 rehash，元素可能被重新分到完全不同的桶里，桶内顺序也可能变化。
这样整体遍历顺序就可能和之前完全不一样。

也就是说：

unordered_map 的遍历顺序是实现相关且不稳定的，特别是 rehash 之后更不能依赖之前顺序。

追问 5：为什么除了哈希函数，还需要 key_equal？

这个点很关键。

因为：

哈希相同，不代表 key 一定相等。

哈希函数只是把 key 映射到某个整数空间里，它本质上是压缩映射。
只要是压缩映射，就一定可能出现不同 key 得到相同哈希值，这就是哈希冲突。

所以查找时流程通常是：

  1. 先算 hash
  2. 定位到某个 bucket
  3. 在这个桶里逐个看候选节点
  4. 对候选节点，最终还要调用 key_equal 判断“是不是真的同一个 key”

所以哈希函数是为了快速缩小范围，
而相等比较函数才是为了最终确认身份。

追问 6：最坏复杂度为什么会退化到 O(n)？

因为如果大量 key 都落到同一个桶里，那哈希表就退化得很像一条长链表。

这可能发生在：

  • 哈希函数设计不好，分布很差
  • 数据分布本身很特殊
  • 恶意输入故意制造大量碰撞

这时查找一个 key 的流程就变成：

  • 先定位到某个桶
  • 然后在这个桶里一个一个比较

如果这个桶里挂了接近全部元素，那就是 O(n)。

追问 7：工程里怎么降低哈希退化风险？

我会从这几个方向答：

第一，选择更好的哈希函数，让 key 分布更均匀。
第二，避免直接把用户可控输入交给过于脆弱的哈希策略，特别是高安全场景。
第三，对字符串等常见高风险 key 类型，选更稳健的散列策略。
第四，在安全敏感系统里，要考虑碰撞攻击防御，因为攻击者可能故意构造大量同桶输入，让哈希表性能退化。

也就是说，工程里不能只看“平均 O(1)”，还得关注：

散列质量 + 输入特征 + 安全风险

小追问 1：元素在内存里是连续的吗？为什么？

不是连续的。

unordered_map 一般不是像 vector 那样把所有元素紧挨着放。
它通常是：

  • 一块 bucket 数组
  • 一堆分散分配的节点

节点为了支持哈希桶组织、冲突链接、稳定存储键值对，本来就更适合以节点形式存在。
所以元素整体在内存中通常不是连续存放的。

小追问 2：为什么 unordered_map 不适合做范围查询，而 map 更适合？

因为 unordered_map 根本不按 key 有序存储。
哈希只负责把 key 打散分桶，不保序。

所以你想查：

  • 某个区间 [l, r]
  • 大于某值的第一个
  • lower_bound / upper_bound

这些对 unordered_map 都没有结构优势，只能近似全扫。

而 map 底层是有序树结构，key 天生有序，所以范围查询、上下界查询都很自然，效率也更可控。

小追问 3：operator[] 和 find() 有什么区别？

这个不能只答“一个会插入，一个不会”，还要讲清楚语义。

operator[]

如果 key 存在，返回对应 value 的引用。
如果 key 不存在，它会先插入一个新元素，key 就是你传的 key，而 mapped_type 会被默认构造，然后再返回这个 value 的引用。

所以这就解释了为什么 mapped_type 通常需要可默认构造。
因为你访问一个不存在的 key 时，容器得先造出一个 value 给你。

比如：

1
2
unordered_map<int, string> mp;
mp[1];

这会插入：

1
{1, ""}

find()

find() 只是查找，不会修改容器。
找到了就返回对应迭代器，找不到就返回 end()。

工程里什么时候更适合用 find

如果你只是想判断有没有、想读取、或者不希望无意中插入新元素，那更适合用 find()。

比如：

1
2
3
4
auto it = mp.find(key);
if (it != mp.end()) {
    // 用 it->second
}

这样不会因为一次“本来只是看看在不在”的访问，意外把 key 插进去。

所以工程里比较稳的习惯是：

  • 需要“查并可能创建”时，用 operator[]
  • 需要“纯查找，不改容器”时，用 find()

unordered_map 底层通常是哈希表，而 map 通常是红黑树，所以前者平均查找插入删除是 O(1)，但不保证有序；后者是 O(log n)，但天然有序。unordered_map 常见实现可以理解成 bucket 数组加节点链式结构：插入时先对 key 计算哈希值，再映射到某个 bucket，如果桶里没有元素就直接挂进去，有冲突就放进该桶对应的链或等价结构里。它之所以平均快，是因为先用哈希把查找范围缩小到一个桶，但最坏情况下如果大量元素落到同一桶，链会很长，复杂度会退化到 O(n)。为了控制冲突，需要关注负载因子 load_factor，当它超过 max_load_factor 时通常会触发 rehash，也就是扩桶并把已有节点重新分布到新的桶中，这一步代价接近 O(n)，也容易导致迭代器失效。unordered_map 不保证遍历顺序稳定，因为元素组织依赖 bucket 布局和 rehash 结果。除了哈希函数，它还需要相等比较函数 key_equal，因为哈希相同并不代表 key 一定相等，最终还要靠相等比较确认是否是同一个 key。元素在内存里通常不是连续的，这也是它不适合范围查询、而 map 更适合做范围查询的重要原因。operator[] 和 find() 的区别不只是一个会插入一个不会，更重要的是 operator[] 对不存在的 key 会插入一个默认构造的 value，因此在纯查找场景下工程里通常更适合使用 find()。

下一题你要是继续这种风格，我也可以继续按“先主答，再逐个追问拆开”来答。