一. 引入哈希表1. 红黑树存在哪些局限性在上一篇中我们学习了基于红黑树的 std::map。它很优雅能让数据始终保持有序查找的时间复杂度是 O(log N)。但在某些极端场景下我们并不在乎元素的顺序比如统计一本书里每个单词出现的次数或者在海量用户 ID 中判断某个 ID 是否存在。此时我们只想要极致的快如果说 std::map 是一本按字母顺序排列的字典你找单词需要一页页翻折半查找那么哈希表Hash Table就像是超市里的储物柜你拿着凭据对应的柜门直接弹开2. 直观理解哈希表Hash Table哈希表的本质是映射想象一个极其简单的场景我们要存 10 个人的电话号码且他们的编号正好是 0 到 9我们只需要开辟一个长度为 10 的数组编号是几就存到数组的第几个位置。查找时复杂度是 O(1) —— 这就是哈希表的理想场景但在现实中我们的 Key键可能是复杂的字符串、巨大的整数甚至是自定义对象。哈希表通过两个核心步骤把这些复杂的 Key 变简单哈希函数 (Hash Function)把任意复杂的 Key 转化成一个数字下标桶 (Bucket)数组中存放数据的位置C 标准库中的 std::unordered_map 和 std::unordered_set 正是这种思想的工业级实现unordered意味着它不保证遍历顺序存进去的顺序和输出的顺序可能完全不同map / set依然保持着键值对映射或唯一集合的功能它保证在平均情况下插入、删除、查找全都是 O(1)二. 本质和对比上一篇我们探讨过std::map 的底层采用红黑树实现就像一支排列有序的队伍每个元素都有明确的位置顺序。相比之下std::unordered_map 更像一个精心设计的仓库系统数据被智能地分配到不同区域桶/Bucket虽然表面看似无序但检索效率却非常高底层逻辑的不同std::map基于红黑树实现通过键值比较进行定位每次查找需要进行 O(log N) 次比较操作std::unordered_map基于哈希表实现通过哈希函数直接计算存储位置在理想情况下可实现常数时间复杂度 O(1) 的快速访问1. 核心差异对照表为了更直观的感受我整理了这张对比表特性map / setunordered_map / set底层实现红黑树(有平衡性的二叉搜索树)哈希表(开链法处理冲突)元素顺序严格有序默认升序无序遍历顺序不可预测查找/增删效率O(log N) (稳定)平均 O(1)极坏情况 O(N)内存开销较低每个节点仅需左右指针较高需维护 Bucket 数组及扩容对 Key 的要求必须定义 operator (比大小)必须有 hash 函数和 operator迭代器双向迭代器可自增/自减前向迭代器仅能自增决策场景什么时候选 std::map需要有序数据比如需要按从小到大的顺序打印成绩单需要范围查找比如查找年龄在 20 到 30 岁之间的所有用户利用 lower_bound对稳定性要求高红黑树的性能非常稳定不会像哈希表那样因为冲突突然变慢什么时候选 std::unordered_map追求极致速度如果只是单纯地想根据 ID 查名字且数据量很大无脑选 unordered 系列不关心顺序只要能存能取谁先谁后无所谓频繁的增删查改在 LeetCode 的大多数算法题中unordered_map 通常是提速的首选这里有个小坑如果使用自定义的结构体比如 Point {int x, y;}做 map 的 Key那么只需要重载 操作符就行但如果你想用它做 unordered_map 的 Key你不仅要重载 还得自己写一个 hash 函数或者告诉编译器怎么算这个结构体的哈希值2. 为什么哈希表对 key 要求严格在使用 std::map 时我们只需要给 Key 提供一个 operator告诉编译器怎么比大小就够了。但换成 std::unordered_map编译器会要求更多它必须支持 Hash 函数 和 operator这是为什么Hash 函数与 operator想象一下我们去健身房存包Hash 函数找柜子当你把钥匙Key交给管理员他通过一个公式Hash Function计算出一个数字。这个数字决定了你的包应该放在哪一排柜子Bucket如果没有 Hash 函数管理员就不知道该把包往哪放operator确认身份由于柜子数量有限偶尔会出现两个不同的 Key 计算出同一个数字哈希冲突。这时同一个柜子里可能会塞进两个包。当你回来取包时管理员需要对比包上的标签确认哪一个才是真正属于你的如果没有 operator即便找到了柜子管理员也没法在冲突的一堆包里认出你的那一个Hash 函数负责确定数据的位置定位桶而 operator 则用于识别数据的唯一性处理冲突3. 为什么只支持前向迭代器这是一个非常经典的问题。std::map 的迭代器是双向的可以 也可以 --但 std::unordered_map 的迭代器通常只能前向只能 这背后的原因藏在它们的底层内存布局里红黑树有序是一个连通的树状结构。每一个节点都知道自己的父节点、左孩子和右孩子。通过这种结构我们可以轻松地找到前一个比我小的或后一个比我大的元素因此支持双向遍历哈希表无序底层本质上是一个数组 链表或其他处理冲突的结构迭代器在遍历时是先遍历完数组的一个桶Bucket 0再跳到下一个桶Bucket 1而为了节省空间和保持效率哈希表中的冲突链表通常是单向链表Single Linked List。在单向链表中节点只知道自己的下一个Next是谁根本不知道上一个是谁如果要支持双向迭代器哈希表就必须把底层的单向链表改成双向链表或者维护一个极其复杂的全局顺序表。为了追求极致的 O(1) 查找速度和较低的内存开销C 标准库选择了放弃后退功能只提供单向迭代器Forward Iterator三. API 使用unordered_map 和 unordered_set 的 API 高度相似。为了简洁下面主要以 unordered_mapstring, int 为例我们可以把 API 分为四个维度初始化、插入、查找、删除1. 初始化unordered_map 提供了非常灵活的构造方式。参考标准库的定义我们可以将初始化归纳为以下几类1. 空构造Empty这是最基础的构造方式。文档中显示它可以接受一个 size_type n 参数// 1. 完全空构造使用默认初始容量 std::unordered_mapstd::string, int map1; // 如果你预知要存 100 个元素可以直接给个初始大小 std::unordered_mapstd::string, int map2(100);2. 区间构造Range Constructor如果已经有一个现成的数据源比如数组、vector 或另一个 map你可以利用迭代器区间直接搬运数据std::vectorstd::pairstd::string, int vec {{Apple, 1}, {Banana, 2}}; // 通过迭代器区间构造 std::unordered_mapstd::string, int map3(vec.begin(), vec.end());常用于将其他容器的数据快速转换为哈希表实现 O(1) 的查找能力3. 拷贝与移动构造Copy Move这是标准容器的常规操作std::unordered_mapstd::string, int original {{Key, 1}}; // 拷贝构造创建一个完全一样的副本 std::unordered_mapstd::string, int copy_map(original); // 移动构造将 original 的资源转移走original 变为空 std::unordered_mapstd::string, int move_map(std::move(original));4. 列表初始化Initializer List这是 C11 引入的语法糖也是目前代码里见得最多的因为它直观得像是在写配置文件std::unordered_mapstd::string, int map4 { {C, 1985}, {Java, 1995}, {Python, 1991} };5. 自定义哈希与比较从上面的截图中可以看到构造函数后面还有 hasher 和 key_equal 等参数虽然 90% 的场景下我们都使用默认值但如果你需要用自定义结构体作为 Key你就需要在这里传入自定义的哈希规则// 伪代码示例传入自定义的哈希对象 auto my_map std::unordered_mapMyStruct, int, MyHasher(10, MyHasher());2. 插入元素标准库主要支持三种数据插入方式insert、emplace 和 operator[]1. operator[]这是 map 特有的功能set 并不支持此特性。如果 Key 存在则修改 Value如果 Key 不存在则直接创建一个新的键值对。如果只是想查询某个 Key 在不在误用了 [] 会导致哈希表莫名其妙多出一个元素Value 为该类型的默认值std::unordered_mapstd::string, int scores; // 1. 插入或修改 scores[Alice] 100; // 2. 危险操作仅仅是访问一个不存在的 Key int temp scores[Unknown]; // 此时 scores 内部已经多了一个 {Unknown, 0}2. insertinsert 接受一个 std::pair 或初始化列表。如果 Key 已存在insert 什么都不做插入失败如果 Key 不存在则插入。它需要先构造好一个 pair 对象然后再拷贝或移动到哈希桶中// 使用 pair 插入 scores.insert(std::pairstd::string, int(Bob, 90)); // 使用初始化列表更常用 scores.insert({Charlie, 85});3. emplace自 C11 起emplace 成了高性能代码的首选。与 insert 一样如果 Key 已存在则插入失败。它利用了模板的可变参数直接在容器内部构造 pair 对象。它避免了先创建一个临时 pair 再拷贝进去的过程注意它不需要大括号 {}// 推荐做法直接传参数不需要构造 pair 对象 scores.emplace(Dave, 92);除了 operator[] 直接返回引用外insert 和 emplace 都会返回一个 pairfirst指向该元素的迭代器second一个 bool 值true 表示插入成功false 表示 Key 已存在auto [it, success] scores.emplace(Alice, 99); if (!success) { std::cout Alice 已经存在分数为 it-second std::endl; }3. 查找元素1. find()find() 是最经典的查找方式。它返回一个迭代器如果找到了迭代器指向对应的键值对如果没找到它会返回 map.end()auto it scores.find(Alice); if (it ! scores.end()) { // 找到了 std::cout Alice 的分数是 it-second std::endl; } else { std::cout 没找到 Alice。 std::endl; }2. count()对于 unordered_map 来说Key 是唯一的所以 count() 的返回值只可能是 0不存在 或 1存在if (scores.count(Bob)) { std::cout Bob 在名单里。; }3. at()at() 是一个只读操作且非常严格。如果 Key 存在返回值的引用。如果 Key 不存在它不会插入新元素而是直接抛出异常 (std::out_of_range)try { int s scores.at(Unknown); } catch (const std::out_of_range e) { std::cout 捕获到异常Key 不存在 std::endl; }4. 删除元素unordered_map 的删除主要依靠 erase()它非常灵活支持三种不同的删除方式按 Key 删除最常用。返回删除的元素个数对于 unordered_map 只有 0 或 1按迭代器删除当你已经通过 find() 拿到了位置直接删除效率最高清空整个容器使用 clear()std::unordered_mapstd::string, int scores {{Alice, 90}, {Bob, 80}, {Charlie, 70}}; // 1. 直接按 Key 删 scores.erase(Alice); // 2. 配合 find 删除 auto it scores.find(Bob); if (it ! scores.end()) { scores.erase(it); // 此时 scores 里只剩 Charlie } // 3. 一键清空 scores.clear();实战题目 1和为 K 的子数组 (LeetCode 560)题目描述给你一个整数数组 nums 和一个整数 k 请你统计并返回该数组中和为 k 的子数组的个数子数组是数组中元素的连续非空序列示例 1输入nums [1,1,1], k 2输出2示例 2输入nums [1,2,3], k 3输出2核心算法思想前缀和的转化我们定义 pre[i] 为从索引 0 到 i 的所有元素之和。那么任何一个连续子数组 [j, i] 的和可以表示为我们的目标是找到满足以下公式的组合将等式变换一下换句话说当遍历到第i个位置时当前的前缀和为pre[i]。此时只需查询哈希表在之前的所有前缀和中有多少个值恰好等于 pre[i] - k代码实现class Solution { public: int subarraySum(vectorint nums, int k) { // key 为前缀和的值value 为该前缀和出现的次数 std::unordered_mapint, int mp; // 【重要核心】初始化前缀和为 0 默认出现了 1 次 // 代表从开头到当前位置正好和为 k 的情况pre[i] - 0 k mp[0] 1; int count 0; int pre 0; // 记录当前前缀和 for(auto e : nums) { pre e; if(mp.find(pre - k) ! mp.end()) count mp[pre - k]; // 如果存在则把出现的次数累加进结果中 // 将当前前缀和存入map mp[pre]; } return count; } };注意mp[0] 1 的作用这是很多人会漏掉的一行。 为什么要加它如果数组第一个元素正好就是 k。此时 pre k我们需要查找 pre - k 0 是否存在。如果没有 mp[0] 1这个符合条件的子数组就会被漏掉。它代表从数组下标 0 开始的子数组这种特殊情况复杂度分析1. 时间复杂度O(N)这里的 N 是数组 nums 的长度我们只对数组进行了一次for循环遍历。在每次循环内部我们主要做了以下三件事变量累加pre xO(1)哈希表查找mp.find()哈希表在平均情况下的查找复杂度为 O(1)哈希表插入/更新mp[pre]平均复杂度同样为 O(1)N 次循环 * 单次常数级操作 O(N)2. 空间复杂度O(N)我们定义了一个 std::unordered_map 来存储前缀和及其出现的次数。如果数组中每一个位置计算出的前缀和都是唯一的例如数组元素全是正数哈希表最多会存储 N 1 个键值对包括初始化的 {0, 1}空间开销随数据量线性增长即O(N)实战题目2LRU 缓存 (LeetCode 146)题目描述请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该逐出 最久未使用的关键字核心难点LRU 缓存要求实现两个功能且时间复杂度必须都是O(1)get(key)如果 Key 存在返回其值并将该 Key 标记为最近使用put(key, value)插入或更新值。如果缓存满了删除最久未使用的元素矛盾点在于哈希表虽然查找快 (O(1))但它没有顺序没法知道谁是最久的。双向链表调整顺序快 (O(1))但它查找慢 (O(N))解题思路哈希表 双向链表我们可以将两者结合用双向链表维护使用顺序用哈希表实现快速定位哈希表的 Value 存的不再是简单的整数而是指向链表节点的迭代器 (Iterator)。这样我们就能通过哈希表直接定位到链表中的具体位置从而在 O(1) 内完成删除和移动操作class LRUCache { public: int _capacity; // 双向链表存储 {key, value}最近使用的放在 head最久不用的在 tail listpairint, int _cache; // 哈希表key 指向链表节点的迭代器 unordered_mapint, listpairint, int::iterator _mp; LRUCache(int capacity) :_capacity(capacity) {} int get(int key) { if(_mp.find(key) _mp.end()) return -1; // 将该节点移到链表头部表示最近使用 // splice 可以在 O(1) 内移动节点而不涉及内存拷贝 _cache.splice(_cache.begin(), _cache, _mp[key]); return _mp[key]-second; } void put(int key, int value) { // 情况 1Key 已存在更新值并移到头部 if(_mp.find(key) ! _mp.end()) { _cache.splice(_cache.begin(), _cache, _mp[key]); _mp[key]-second value; return; } // 情况 2Key 不存在检查容量 // 容量满了删除最久未使用的数据 if(_cache.size() _capacity) { int removeKey _cache.back().first; _mp.erase(removeKey); _cache.pop_back(); } // 插入新元素到头部 _cache.emplace_front(key, value); _mp[key] _cache.begin(); } };std::list::splice 是 C 标准库中 list 容器的高效操作接口。该接口通过调整指针指向来实现链表节点的位置移动整个过程不涉及元素拷贝或销毁操作。由于 std::list 的特性只要节点未被删除指向它的迭代器始终保持有效。这一特性确保了我们可以安全地将 list::iterator 存储在 unordered_map 中复杂度分析时间复杂度get 和 put 均为 O(1)哈希表负责 O(1) 查找定位。双向链表负责 O(1) 节点搬运空间复杂度O(capacity)我们需要同时在链表和哈希表中维护最多 capacity 个元素总结总的来说std::unordered_map 是 C 给追求极致性能的开发者的加速器它通过牺牲有序性和额外的内存空间换取了平均 O(1) 的惊人速度。然而在实际工程中必须警惕哈希冲突导致性能退化到 O(N) 的极端情况并习惯为自定义 Key 手动提供 hash 函数和 operator。一个成熟的 C 开发者应当具备这样的直觉在数据量大且无序要求的算法场景如两数之和、LRU中首选 unordered 系列并养成提前使用 reserve() 规避重哈希rehash开销的好习惯而如果需要遍历有序数据或稳定的性能曲线请继续使用红黑树std::map
C++关联容器进阶：unordered_map / set与详解
一. 引入哈希表1. 红黑树存在哪些局限性在上一篇中我们学习了基于红黑树的 std::map。它很优雅能让数据始终保持有序查找的时间复杂度是 O(log N)。但在某些极端场景下我们并不在乎元素的顺序比如统计一本书里每个单词出现的次数或者在海量用户 ID 中判断某个 ID 是否存在。此时我们只想要极致的快如果说 std::map 是一本按字母顺序排列的字典你找单词需要一页页翻折半查找那么哈希表Hash Table就像是超市里的储物柜你拿着凭据对应的柜门直接弹开2. 直观理解哈希表Hash Table哈希表的本质是映射想象一个极其简单的场景我们要存 10 个人的电话号码且他们的编号正好是 0 到 9我们只需要开辟一个长度为 10 的数组编号是几就存到数组的第几个位置。查找时复杂度是 O(1) —— 这就是哈希表的理想场景但在现实中我们的 Key键可能是复杂的字符串、巨大的整数甚至是自定义对象。哈希表通过两个核心步骤把这些复杂的 Key 变简单哈希函数 (Hash Function)把任意复杂的 Key 转化成一个数字下标桶 (Bucket)数组中存放数据的位置C 标准库中的 std::unordered_map 和 std::unordered_set 正是这种思想的工业级实现unordered意味着它不保证遍历顺序存进去的顺序和输出的顺序可能完全不同map / set依然保持着键值对映射或唯一集合的功能它保证在平均情况下插入、删除、查找全都是 O(1)二. 本质和对比上一篇我们探讨过std::map 的底层采用红黑树实现就像一支排列有序的队伍每个元素都有明确的位置顺序。相比之下std::unordered_map 更像一个精心设计的仓库系统数据被智能地分配到不同区域桶/Bucket虽然表面看似无序但检索效率却非常高底层逻辑的不同std::map基于红黑树实现通过键值比较进行定位每次查找需要进行 O(log N) 次比较操作std::unordered_map基于哈希表实现通过哈希函数直接计算存储位置在理想情况下可实现常数时间复杂度 O(1) 的快速访问1. 核心差异对照表为了更直观的感受我整理了这张对比表特性map / setunordered_map / set底层实现红黑树(有平衡性的二叉搜索树)哈希表(开链法处理冲突)元素顺序严格有序默认升序无序遍历顺序不可预测查找/增删效率O(log N) (稳定)平均 O(1)极坏情况 O(N)内存开销较低每个节点仅需左右指针较高需维护 Bucket 数组及扩容对 Key 的要求必须定义 operator (比大小)必须有 hash 函数和 operator迭代器双向迭代器可自增/自减前向迭代器仅能自增决策场景什么时候选 std::map需要有序数据比如需要按从小到大的顺序打印成绩单需要范围查找比如查找年龄在 20 到 30 岁之间的所有用户利用 lower_bound对稳定性要求高红黑树的性能非常稳定不会像哈希表那样因为冲突突然变慢什么时候选 std::unordered_map追求极致速度如果只是单纯地想根据 ID 查名字且数据量很大无脑选 unordered 系列不关心顺序只要能存能取谁先谁后无所谓频繁的增删查改在 LeetCode 的大多数算法题中unordered_map 通常是提速的首选这里有个小坑如果使用自定义的结构体比如 Point {int x, y;}做 map 的 Key那么只需要重载 操作符就行但如果你想用它做 unordered_map 的 Key你不仅要重载 还得自己写一个 hash 函数或者告诉编译器怎么算这个结构体的哈希值2. 为什么哈希表对 key 要求严格在使用 std::map 时我们只需要给 Key 提供一个 operator告诉编译器怎么比大小就够了。但换成 std::unordered_map编译器会要求更多它必须支持 Hash 函数 和 operator这是为什么Hash 函数与 operator想象一下我们去健身房存包Hash 函数找柜子当你把钥匙Key交给管理员他通过一个公式Hash Function计算出一个数字。这个数字决定了你的包应该放在哪一排柜子Bucket如果没有 Hash 函数管理员就不知道该把包往哪放operator确认身份由于柜子数量有限偶尔会出现两个不同的 Key 计算出同一个数字哈希冲突。这时同一个柜子里可能会塞进两个包。当你回来取包时管理员需要对比包上的标签确认哪一个才是真正属于你的如果没有 operator即便找到了柜子管理员也没法在冲突的一堆包里认出你的那一个Hash 函数负责确定数据的位置定位桶而 operator 则用于识别数据的唯一性处理冲突3. 为什么只支持前向迭代器这是一个非常经典的问题。std::map 的迭代器是双向的可以 也可以 --但 std::unordered_map 的迭代器通常只能前向只能 这背后的原因藏在它们的底层内存布局里红黑树有序是一个连通的树状结构。每一个节点都知道自己的父节点、左孩子和右孩子。通过这种结构我们可以轻松地找到前一个比我小的或后一个比我大的元素因此支持双向遍历哈希表无序底层本质上是一个数组 链表或其他处理冲突的结构迭代器在遍历时是先遍历完数组的一个桶Bucket 0再跳到下一个桶Bucket 1而为了节省空间和保持效率哈希表中的冲突链表通常是单向链表Single Linked List。在单向链表中节点只知道自己的下一个Next是谁根本不知道上一个是谁如果要支持双向迭代器哈希表就必须把底层的单向链表改成双向链表或者维护一个极其复杂的全局顺序表。为了追求极致的 O(1) 查找速度和较低的内存开销C 标准库选择了放弃后退功能只提供单向迭代器Forward Iterator三. API 使用unordered_map 和 unordered_set 的 API 高度相似。为了简洁下面主要以 unordered_mapstring, int 为例我们可以把 API 分为四个维度初始化、插入、查找、删除1. 初始化unordered_map 提供了非常灵活的构造方式。参考标准库的定义我们可以将初始化归纳为以下几类1. 空构造Empty这是最基础的构造方式。文档中显示它可以接受一个 size_type n 参数// 1. 完全空构造使用默认初始容量 std::unordered_mapstd::string, int map1; // 如果你预知要存 100 个元素可以直接给个初始大小 std::unordered_mapstd::string, int map2(100);2. 区间构造Range Constructor如果已经有一个现成的数据源比如数组、vector 或另一个 map你可以利用迭代器区间直接搬运数据std::vectorstd::pairstd::string, int vec {{Apple, 1}, {Banana, 2}}; // 通过迭代器区间构造 std::unordered_mapstd::string, int map3(vec.begin(), vec.end());常用于将其他容器的数据快速转换为哈希表实现 O(1) 的查找能力3. 拷贝与移动构造Copy Move这是标准容器的常规操作std::unordered_mapstd::string, int original {{Key, 1}}; // 拷贝构造创建一个完全一样的副本 std::unordered_mapstd::string, int copy_map(original); // 移动构造将 original 的资源转移走original 变为空 std::unordered_mapstd::string, int move_map(std::move(original));4. 列表初始化Initializer List这是 C11 引入的语法糖也是目前代码里见得最多的因为它直观得像是在写配置文件std::unordered_mapstd::string, int map4 { {C, 1985}, {Java, 1995}, {Python, 1991} };5. 自定义哈希与比较从上面的截图中可以看到构造函数后面还有 hasher 和 key_equal 等参数虽然 90% 的场景下我们都使用默认值但如果你需要用自定义结构体作为 Key你就需要在这里传入自定义的哈希规则// 伪代码示例传入自定义的哈希对象 auto my_map std::unordered_mapMyStruct, int, MyHasher(10, MyHasher());2. 插入元素标准库主要支持三种数据插入方式insert、emplace 和 operator[]1. operator[]这是 map 特有的功能set 并不支持此特性。如果 Key 存在则修改 Value如果 Key 不存在则直接创建一个新的键值对。如果只是想查询某个 Key 在不在误用了 [] 会导致哈希表莫名其妙多出一个元素Value 为该类型的默认值std::unordered_mapstd::string, int scores; // 1. 插入或修改 scores[Alice] 100; // 2. 危险操作仅仅是访问一个不存在的 Key int temp scores[Unknown]; // 此时 scores 内部已经多了一个 {Unknown, 0}2. insertinsert 接受一个 std::pair 或初始化列表。如果 Key 已存在insert 什么都不做插入失败如果 Key 不存在则插入。它需要先构造好一个 pair 对象然后再拷贝或移动到哈希桶中// 使用 pair 插入 scores.insert(std::pairstd::string, int(Bob, 90)); // 使用初始化列表更常用 scores.insert({Charlie, 85});3. emplace自 C11 起emplace 成了高性能代码的首选。与 insert 一样如果 Key 已存在则插入失败。它利用了模板的可变参数直接在容器内部构造 pair 对象。它避免了先创建一个临时 pair 再拷贝进去的过程注意它不需要大括号 {}// 推荐做法直接传参数不需要构造 pair 对象 scores.emplace(Dave, 92);除了 operator[] 直接返回引用外insert 和 emplace 都会返回一个 pairfirst指向该元素的迭代器second一个 bool 值true 表示插入成功false 表示 Key 已存在auto [it, success] scores.emplace(Alice, 99); if (!success) { std::cout Alice 已经存在分数为 it-second std::endl; }3. 查找元素1. find()find() 是最经典的查找方式。它返回一个迭代器如果找到了迭代器指向对应的键值对如果没找到它会返回 map.end()auto it scores.find(Alice); if (it ! scores.end()) { // 找到了 std::cout Alice 的分数是 it-second std::endl; } else { std::cout 没找到 Alice。 std::endl; }2. count()对于 unordered_map 来说Key 是唯一的所以 count() 的返回值只可能是 0不存在 或 1存在if (scores.count(Bob)) { std::cout Bob 在名单里。; }3. at()at() 是一个只读操作且非常严格。如果 Key 存在返回值的引用。如果 Key 不存在它不会插入新元素而是直接抛出异常 (std::out_of_range)try { int s scores.at(Unknown); } catch (const std::out_of_range e) { std::cout 捕获到异常Key 不存在 std::endl; }4. 删除元素unordered_map 的删除主要依靠 erase()它非常灵活支持三种不同的删除方式按 Key 删除最常用。返回删除的元素个数对于 unordered_map 只有 0 或 1按迭代器删除当你已经通过 find() 拿到了位置直接删除效率最高清空整个容器使用 clear()std::unordered_mapstd::string, int scores {{Alice, 90}, {Bob, 80}, {Charlie, 70}}; // 1. 直接按 Key 删 scores.erase(Alice); // 2. 配合 find 删除 auto it scores.find(Bob); if (it ! scores.end()) { scores.erase(it); // 此时 scores 里只剩 Charlie } // 3. 一键清空 scores.clear();实战题目 1和为 K 的子数组 (LeetCode 560)题目描述给你一个整数数组 nums 和一个整数 k 请你统计并返回该数组中和为 k 的子数组的个数子数组是数组中元素的连续非空序列示例 1输入nums [1,1,1], k 2输出2示例 2输入nums [1,2,3], k 3输出2核心算法思想前缀和的转化我们定义 pre[i] 为从索引 0 到 i 的所有元素之和。那么任何一个连续子数组 [j, i] 的和可以表示为我们的目标是找到满足以下公式的组合将等式变换一下换句话说当遍历到第i个位置时当前的前缀和为pre[i]。此时只需查询哈希表在之前的所有前缀和中有多少个值恰好等于 pre[i] - k代码实现class Solution { public: int subarraySum(vectorint nums, int k) { // key 为前缀和的值value 为该前缀和出现的次数 std::unordered_mapint, int mp; // 【重要核心】初始化前缀和为 0 默认出现了 1 次 // 代表从开头到当前位置正好和为 k 的情况pre[i] - 0 k mp[0] 1; int count 0; int pre 0; // 记录当前前缀和 for(auto e : nums) { pre e; if(mp.find(pre - k) ! mp.end()) count mp[pre - k]; // 如果存在则把出现的次数累加进结果中 // 将当前前缀和存入map mp[pre]; } return count; } };注意mp[0] 1 的作用这是很多人会漏掉的一行。 为什么要加它如果数组第一个元素正好就是 k。此时 pre k我们需要查找 pre - k 0 是否存在。如果没有 mp[0] 1这个符合条件的子数组就会被漏掉。它代表从数组下标 0 开始的子数组这种特殊情况复杂度分析1. 时间复杂度O(N)这里的 N 是数组 nums 的长度我们只对数组进行了一次for循环遍历。在每次循环内部我们主要做了以下三件事变量累加pre xO(1)哈希表查找mp.find()哈希表在平均情况下的查找复杂度为 O(1)哈希表插入/更新mp[pre]平均复杂度同样为 O(1)N 次循环 * 单次常数级操作 O(N)2. 空间复杂度O(N)我们定义了一个 std::unordered_map 来存储前缀和及其出现的次数。如果数组中每一个位置计算出的前缀和都是唯一的例如数组元素全是正数哈希表最多会存储 N 1 个键值对包括初始化的 {0, 1}空间开销随数据量线性增长即O(N)实战题目2LRU 缓存 (LeetCode 146)题目描述请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该逐出 最久未使用的关键字核心难点LRU 缓存要求实现两个功能且时间复杂度必须都是O(1)get(key)如果 Key 存在返回其值并将该 Key 标记为最近使用put(key, value)插入或更新值。如果缓存满了删除最久未使用的元素矛盾点在于哈希表虽然查找快 (O(1))但它没有顺序没法知道谁是最久的。双向链表调整顺序快 (O(1))但它查找慢 (O(N))解题思路哈希表 双向链表我们可以将两者结合用双向链表维护使用顺序用哈希表实现快速定位哈希表的 Value 存的不再是简单的整数而是指向链表节点的迭代器 (Iterator)。这样我们就能通过哈希表直接定位到链表中的具体位置从而在 O(1) 内完成删除和移动操作class LRUCache { public: int _capacity; // 双向链表存储 {key, value}最近使用的放在 head最久不用的在 tail listpairint, int _cache; // 哈希表key 指向链表节点的迭代器 unordered_mapint, listpairint, int::iterator _mp; LRUCache(int capacity) :_capacity(capacity) {} int get(int key) { if(_mp.find(key) _mp.end()) return -1; // 将该节点移到链表头部表示最近使用 // splice 可以在 O(1) 内移动节点而不涉及内存拷贝 _cache.splice(_cache.begin(), _cache, _mp[key]); return _mp[key]-second; } void put(int key, int value) { // 情况 1Key 已存在更新值并移到头部 if(_mp.find(key) ! _mp.end()) { _cache.splice(_cache.begin(), _cache, _mp[key]); _mp[key]-second value; return; } // 情况 2Key 不存在检查容量 // 容量满了删除最久未使用的数据 if(_cache.size() _capacity) { int removeKey _cache.back().first; _mp.erase(removeKey); _cache.pop_back(); } // 插入新元素到头部 _cache.emplace_front(key, value); _mp[key] _cache.begin(); } };std::list::splice 是 C 标准库中 list 容器的高效操作接口。该接口通过调整指针指向来实现链表节点的位置移动整个过程不涉及元素拷贝或销毁操作。由于 std::list 的特性只要节点未被删除指向它的迭代器始终保持有效。这一特性确保了我们可以安全地将 list::iterator 存储在 unordered_map 中复杂度分析时间复杂度get 和 put 均为 O(1)哈希表负责 O(1) 查找定位。双向链表负责 O(1) 节点搬运空间复杂度O(capacity)我们需要同时在链表和哈希表中维护最多 capacity 个元素总结总的来说std::unordered_map 是 C 给追求极致性能的开发者的加速器它通过牺牲有序性和额外的内存空间换取了平均 O(1) 的惊人速度。然而在实际工程中必须警惕哈希冲突导致性能退化到 O(N) 的极端情况并习惯为自定义 Key 手动提供 hash 函数和 operator。一个成熟的 C 开发者应当具备这样的直觉在数据量大且无序要求的算法场景如两数之和、LRU中首选 unordered 系列并养成提前使用 reserve() 规避重哈希rehash开销的好习惯而如果需要遍历有序数据或稳定的性能曲线请继续使用红黑树std::map
