这篇文章要回答什么你大概写过这样的代码#include unordered_map #include string #include iostream int main() { std::unordered_mapstd::string, int scores; // 学生姓名 - 分数 scores[Alice] 90; // 插入 scores[Bob] 85; std::cout scores[Alice] std::endl; // 查找 return 0; }问题来了为什么 unordered_map 的查找、插入平均是O(1)而 map 是 O(log n)它内部到底长什么样哈希桶是什么rehash又是什么为什么说它是unordered无序的网上说的开放寻址和标准库用的链地址法有什么区别这篇文章带你一层层拆开它的内脏。全程小白可操作每个术语第一次出现都配通俗类比每段代码都有中文注释易错处都有 ⚠️ 预警。1. 先从哈希说起一个储物柜的故事1.1 通俗类比想象一个大型快递储物柜柜子有 100 个格子每个格子编号 0~99。你想存一个快递快递单号是 A12345。收件员不会傻乎乎地从 0 号格挨个找空位而是用一个固定规则把单号换算成格子号格号 单号 对 100 取余比如 A12345 的数字部分 12345 % 100 45于是直接放进45 号格。取件时同样算一次12345 % 100 45直奔 45 号格一步到位。这个把任意数据换算成格子号的规则就是哈希函数hash function格子号叫做哈希值hash value或桶号整个储物柜就是桶数组bucket array。✅ 优点存和取都只做一次计算所以是O(1)。⚠️ 痛点如果两个单号算出来同一个格子号比如 12345 % 100 45 和 22345 % 100 45就冲突了——这叫哈希冲突hash collision。1.2 术语速记术语人话解释哈希函数把键变成格子号的规则桶bucket一个格子通常是一个链表头哈希冲突两个键算出了同一个格子号负载因子已存元素数 ÷ 格子总数后面细讲2. 总览std::unordered_map 的底层结构2.1 一句话总结std::unordered_map 底层是哈希表hash table标准库实现采用链地址法separate chaining一个桶数组bucket array 每个桶上挂一条单向链表。结构示意bucket 数组vectornode* ┌──────┐ │ [0] │ → 空 │ [1] │ → (keyAlice, val90) → (keyBob, val85) → nullptr ← 1号桶的链表 │ [2] │ → 空 │ [3] │ → (keyCat, val7) → nullptr │ ... │ │ [N-1]│ → 空 └──────┘每个元素是一个节点node节点里存 {key, value, 指向下一个节点的指针}。插入时先算 hash(key) % bucket_count 得到桶号然后把新节点头插到该桶的链表上。查找时同样算桶号然后在链表里线性扫描找 key。2.2 为什么叫 unordered因为元素存到哪个桶、桶内链表的顺序取决于哈希值而哈希值是看起来随机的。所以遍历 unordered_map 时元素的顺序不保证与插入顺序一致也不能保证排序。这就是无序unordered的含义——它牺牲顺序换取 O(1) 查找。对比一下容器底层结构查找复杂度是否有序std::map红黑树O(log n)✅ 按键排序std::unordered_map哈希表O(1) 平均❌ 无序3. 关键成员桶数组、节点、负载因子3.1 节点长什么样简化版GCC libstdc 里的节点大致是// 每个节点一个键值对 一个指向下一个节点的指针 template typename Key, typename Value struct _Hash_node { // 存储的键值对 std::pairconst Key, Value _M_v; // 指向同一桶中下一个节点的指针 _Hash_node* _M_next; // 哈希值也会缓存一份避免 rehash 时重新计算 std::size_t _M_hash_code; };⚠️注意GCC 里每个节点还会缓存哈希值_M_hash_code。好处是 rehash扩容时不用重新调用哈希函数直接拿缓存的哈希值重新对桶数取余即可能省大量计算。3.2 桶数组长什么样桶数组是一个指针数组每个元素是指向链表第一个节点的指针// 简化_M_buckets 就是 node* 数组 std::vectornode* buckets; // buckets[i] 指向第 i 个桶的链表头3.3 负载因子load factor—— 哈希表的拥挤度负载因子 已存储元素个数 / 桶的数量负载因子小 → 桶多元素少 → 链表短 → 查找快但浪费内存。负载因子大 → 链表长 → 查找慢。std::unordered_map 默认 max_load_factor 1.0即平均每个桶最多 1 个元素一旦超过就触发 rehash 扩容。// 查看 / 设置负载因子上限 std::unordered_mapint, int m; std::cout m.max_load_factor() std::endl; // 默认 1.0 m.max_load_factor(0.7); // 可以调小更宽敞4. 插入流程分步骤拆解以 m[Alice] 90 为例底层干的事第 1 步调用哈希函数计算 key 的哈希值 hash_code std::hashstd::string{}(Alice) 第 2 步对桶数取余得到桶号 bucket_index hash_code % buckets.size() 第 3 步在该桶的链表里查找是否已存在 Alice —— 存在更新 value —— 不存在创建新节点头插到链表 第 4 步检查是否需要 rehash元素数 桶数 × max_load_factor —— 需要扩容桶数组把所有节点重新分配到新桶4.1 一个完整的可运行示例演示桶的分布#include iostream #include unordered_map #include string int main() { std::unordered_mapstd::string, int m; m[apple] 1; m[banana] 2; m[cherry] 3; m[date] 4; // bucket_count()当前桶的数量 std::cout 桶的数量: m.bucket_count() std::endl; // 遍历每个键看它落在哪个桶 for (const auto [key, val] : m) { std::cout key - 桶 m.bucket(key) 该桶元素数 m.bucket_size(m.bucket(key)) std::endl; } return 0; }输出大致长这样不同编译器/库实现结果不同因为哈希函数实现不同⚠️易错点 1bucket_count() 不是元素个数size() 才是元素个数。别搞混。5. 查找流程auto it m.find(banana);第 1 步hash_code hash(banana) 第 2 步bucket_index hash_code % buckets.size() 第 3 步在 buckets[bucket_index] 的链表里逐个比较 key —— 找到返回迭代器 —— 没找到返回 end()平均 O(1)哈希计算 取余 链表扫描。最坏 O(n)所有键都撞到同一个桶灾难见第 8 节。5.1 三种查找方式对比方式行为适用场景m[key]key 不存在时会插入默认值需要取不到就补默认时m.at(key)不存在时抛 std::out_of_range确定 key 必须存在m.find(key)不存在时返回 end()只查不改最常用⚠️易错点 2m[key] 在 key 不存在时会插入一个默认构造的值这是一个写操作在只读场景用它会导致不必要的插入甚至改变 size()。// 错误示范只想查一下结果把 (unknown, 0) 插进去了 if (m[unknown] 0) { /* 每次都会插一个键 */ } // 正确示范 if (m.find(unknown) m.end()) { /* 真的不存在 */ }6. 删除流程m.erase(apple);第 1 步计算 hash_code 和 bucket_index 第 2 步在链表中找到节点并删除把前后指针接好 第 3 步size() 减 1⚠️易错点 3遍历时删除元素迭代器会失效。要用先取下一个再删当前的写法// 遍历并删除 value 为 0 的元素 for (auto it m.begin(); it ! m.end(); ) { if (it-second 0) { it m.erase(it); // C11 起 erase 返回下一个迭代器 } else { it; } }7. rehash哈希表的搬家扩容7.1 为什么需要 rehash桶是有限的。元素越插越多桶上的链表越来越长查找越来越慢——负载因子逼近上限哈希表退化成一堆链表。解决办法扩大桶数组让每个桶重新分房子链表变短。7.2 rehash 的时机标准规定当 size() bucket_count() * max_load_factor() 时容器自动rehash。默认 max_load_factor 1.0所以元素数超过桶数时就会触发。新桶数量标准只要求至少满足负载因子GCC 通常按近似 2 倍实际是 13、29、53、97……这样一组素数扩容。为什么用素数因为 hash % bucket_count 对素数取余的分布更均匀减少冲突。7.3 rehash 过程三步走第 1 步申请一块更大的桶数组比如 13 → 29 个桶 第 2 步遍历旧桶数组的所有链表 第 3 步把每个节点按 缓存哈希值 % 新桶数 重新挂到新桶7.4 rehash 的代价时间复杂度O(n)需要把所有元素重新分配。迭代器/指针/引用全部失效因为节点搬了家。频繁 rehash 会带来性能抖动所以可以提前预留// 提前告诉容器我大概要存 10000 个元素避免反复扩容 std::unordered_mapint, int m; m.reserve(10000); // 等价于 m.rehash(10000 / m.max_load_factor());⚠️易错点 4持有 unordered_map 的迭代器或元素指针后如果又插入元素导致 rehash迭代器/指针/引用全部失效元素地址变了。而 std::map 插入不会使已有迭代器失效。这是哈希表容器的经典坑。8. 哈希冲突与两种解决思路8.1 链地址法separate chaining—— 标准库的选择冲突的元素挂同一条链表上。桶 3: (a1) → (c3) → (e5) → nullptr优点实现简单元素数量可以超过桶数删除容易。缺点链表指针有额外内存开销最坏情况下全挤一个桶就退化成链表 O(n)。8.2 开放寻址法open addressing—— 常见于自研哈希表冲突时不挂链表而是往后找下一个空桶放进去。桶 3: (a1) 桶 4: (c3) ← a 冲突后线性探测放这里 桶 5: (e5) ← c 冲突后继续探测放这里常用探测方式探测方式规则特点线性探测依次看下一个桶简单但容易聚集一堆连续占用二次探测偏移按 1,4,9,16... 递增缓解聚集双重哈希用第二个哈希函数算步长分布更均匀实现最复杂优点无指针内存紧凑、缓存友好元素全在连续数组里。缺点删除麻烦不能直接置空要打墓碑标记负载因子必须远小于 1通常 0.5~0.7否则探测链变长、性能暴跌元素不能超过桶数。8.3 两种方案对比表格对比维度链地址法std 采用开放寻址冲突处理链表挂节点探测下一个空桶额外内存每个节点一个指针无指针更紧凑缓存友好性差链表跳来跳去好数组连续允许负载因子可 1必须 1通常 0.5~0.7删除实现直接摘节点需打墓碑标记较麻烦退化风险全部撞一桶 → O(n)负载因子过高 → 探测链爆炸典型实现libstdc / MSVC STL自研高性能表、Java 8 后 HashMap树化前⚠️易错点 5网上很多文章拿开放寻址讲 unordered_map那是讲错了——C 标准库 std::unordered_map 用的是链地址法。开放寻址是另一种实现思路不是标准库的实现。9. 手写一个极简版哈希表可运行理解了原理我们亲手实现一个迷你 unordered_map支持插入、查找、删除、rehash。这是验证理解的最好方式。#include iostream #include vector #include list #include string #include functional // 极简哈希表链地址法键为 string值为 int class MiniHashMap { private: // 桶的数量初始 8 static constexpr size_t kInitBuckets 8; // 负载因子上限超过就扩容 static constexpr float kMaxLoadFactor 0.75f; // 每个桶是一条链表链表中每个元素是 {key, value} // 这里用 std::list 省去手写链表节点原理一致 using Bucket std::liststd::pairstd::string, int; // 桶数组每个元素是一条链表 std::vectorBucket buckets_; // 已存储元素个数 size_t size_ 0; // 计算 key 的桶号哈希值 % 桶数 size_t hash_bucket(const std::string key) const { return std::hashstd::string{}(key) % buckets_.size(); } // 在某个桶里查找 key找到返回迭代器找不到返回 end() Bucket::iterator find_in_bucket(size_t idx, const std::string key) { for (auto it buckets_[idx].begin(); it ! buckets_[idx].end(); it) { if (it-first key) { return it; // 找到了 } } return buckets_[idx].end(); // 没找到 } // rehash扩容到 new_bucket_count 个桶把所有元素重新分配 void rehash(size_t new_bucket_count) { std::cout [rehash] buckets_.size() 个桶 - new_bucket_count 个桶 std::endl; // 1. 创建新的桶数组 std::vectorBucket new_buckets(new_bucket_count); // 2. 遍历所有旧桶的所有元素 for (auto bucket : buckets_) { for (auto kv : bucket) { // 3. 重新计算桶号搬进新桶 size_t new_idx std::hashstd::string{}(kv.first) % new_bucket_count; new_buckets[new_idx].push_back(kv); } } // 4. 用新数组替换旧数组 buckets_.swap(new_buckets); } // 检查负载因子必要时自动扩容 void maybe_rehash() { float load static_castfloat(size_) / buckets_.size(); if (load kMaxLoadFactor) { // 桶数翻倍真实实现会用素数序列这里简单翻倍 rehash(buckets_.size() * 2); } } public: MiniHashMap() : buckets_(kInitBuckets) {} // 插入或更新key 存在则覆盖不存在则新增 void insert(const std::string key, int value) { size_t idx hash_bucket(key); // 1. 算桶号 auto it find_in_bucket(idx, key); // 2. 桶内查找 if (it ! buckets_[idx].end()) { it-second value; // 已存在更新值 } else { buckets_[idx].push_back({key, value}); // 不存在插入链表 size_; // 元素数 1 maybe_rehash(); // 检查是否需要扩容 } } // 查找找到返回 true 并带出值 bool find(const std::string key, int out_value) const { size_t idx hash_bucket(key); for (const auto kv : buckets_[idx]) { if (kv.first key) { out_value kv.second; // 找到了 return true; } } return false; // 没找到 } // 删除删除成功返回 true bool erase(const std::string key) { size_t idx hash_bucket(key); auto it find_in_bucket(idx, key); if (it buckets_[idx].end()) { return false; // 不存在 } buckets_[idx].erase(it); // 从链表摘掉 --size_; return true; } // 当前元素个数 size_t size() const { return size_; } // 桶的数量 size_t bucket_count() const { return buckets_.size(); } }; int main() { MiniHashMap m; // 插入一些元素 m.insert(Alice, 90); m.insert(Bob, 85); m.insert(Cat, 60); m.insert(Dog, 70); m.insert(Eve, 95); // 插入到这里时 size/buckets 超过 0.75会触发 rehash std::cout 元素个数: m.size() std::endl; std::cout 桶的数量: m.bucket_count() std::endl; // 查找 int v 0; if (m.find(Alice, v)) { std::cout Alice 的分数: v std::endl; } if (!m.find(Nobody, v)) { std::cout Nobody 不存在 std::endl; } // 删除 m.erase(Cat); std::cout 删除 Cat 后元素个数: m.size() std::endl; return 0; }运行输出示例这个迷你版就是 std::unordered_map 的灵魂简化版核心四步算桶号、桶内找、链表插、超载扩容一模一样。10. 性能、最佳实践与易错点汇总10.1 复杂度总结操作平均最坏插入O(1)O(n)查找O(1)O(n)删除O(1)O(n)rehashO(n)O(n)最坏情况出现在哈希函数设计极差所有 key 撞一桶或有人故意构造冲突哈希碰撞攻击 / Hash DoS。10.2 为什么自定义类型要提供哈希函数std::unordered_map 要求 key 类型有相等比较和哈希函数std::hash。基础类型和 std::string 都自带自定义类型必须自己提供否则编译报错。#include iostream #include unordered_map #include string struct Person { std::string name; int age; // 1. 必须提供相等比较供桶内查找使用 bool operator(const Person other) const { return name other.name age other.age; } }; // 2. 必须提供哈希函数为 Person 特化 std::hash namespace std { template struct hashPerson { size_t operator()(const Person p) const { // 常见做法把多个字段的哈希值混合 size_t h1 hashstring{}(p.name); size_t h2 hashint{}(p.age); return h1 ^ (h2 1); // 简单混合实际库会用更复杂的混合算法 } }; } int main() { std::unordered_mapPerson, std::string m; m[{ Tom, 18 }] student; std::cout m[{ Tom, 18 }] std::endl; // 输出 student return 0; }⚠️易错点 6自定义类型的哈希函数与 operator 必须一致——相等的对象哈希值必须相同否则查找会失败同一把钥匙开不同的锁。⚠️易错点 7不要修改已插入元素的 key比如 auto k it-first; k new;。key 变了它却还待在旧桶里之后再也查不到它——哈希表会丢元素。这也是为什么标准库把 key 声明为 const。10.3 性能调优口诀知道大概容量 → reserve() 提前扩容避免多次 rehash。读多写少 → 用 find() 而不是 operator[]避免误插入。key 是字符串且频繁构造 → 考虑 std::string_viewC17或透明哈希减少拷贝。追求极致性能 → 可换 absl::flat_hash_map、robin_hood 等开放寻址实现内存更紧凑。10.4 何时不要用 unordered_map场景推荐容器原因需要按键有序遍历std::map红黑树天然有序元素很少 20std::vector 线性扫描哈希计算开销 线性扫描开销需要稳定迭代器std::mapunordered_map rehash 会失效11. FAQ 速查表问题一句话答案unordered_map 底层是什么哈希表采用链地址法桶数组 每条桶挂链表为什么查找是 O(1)先哈希取余定位桶再在短链表上找平均一步到位rehash 是什么桶不够用时扩大桶数组、把元素重新分配O(n)什么时候触发 rehashsize bucket_count × max_load_factor默认 1.0时自动触发max_load_factor 能改吗能调小更省查找时间但更费内存调大相反迭代器为什么会失效rehash 会移动所有节点地址旧迭代器全部失效开放寻址和链地址法啥区别链地址法冲突挂链表标准库用开放寻址冲突探测空位自研常用为什么遍历是无序的元素位置由哈希值决定哈希值是伪随机的自定义类型能当 key 吗能但必须提供 operator 和 std::hash 特化且相等对象哈希必须相同插入后能改 key 吗不能key 是 const改了会丢元素reserve() 有什么用提前分配桶避免多次 rehash 的性能抖动m[key] 和 m.at(key) 区别m[key] 不存在会插入默认值at 不存在抛异常unordered_map 和 map 怎么选要 O(1) 查找且不要求有序 → unordered_map要有序 → map12. 延伸阅读方向哈希函数的进化std::hash、SipHash、MurmurHash哈希碰撞攻击Hash DoS与安全哈希absl::flat_hash_map 的开放寻址 控制字节control bytes设计Java HashMap 的链表转红黑树树化机制对比 C 标准库不树化