unordered_map哈希映射——像带标签的超级储物柜
较难2哈希映射unordered_map——像随身携带的智能电话本
你有没有遇到过这种情况?你想快速找到某个朋友的电话号码,但整本厚厚的电话本得从第一页翻到最后一页。如果电话本能自动根据名字“嗖”的一下定位到号码,那该多好!在编程世界里,unordered_map 就是这样一个“智能电话本”:你告诉它一个“键”(比如“张三”),它立刻就能返回对应的“值”(比如“13800138000”),而且速度飞快,平均只需要一步。
更神奇的是,它就像一个带标签的超级储物柜:每个柜子外面贴着一个标签(键),打开柜子里面放着对应的物品(值)。你想找“语文书”,系统直接告诉你“在15号柜”,而不是让你把100个柜子一个个打开看。这种结构叫哈希映射,在C++中用 unordered_map 实现,在Python中直接用 dict(字典)。
一、从生活走进代码:为什么需要映射?
先看几个生活中的“映射”例子:
- 字典:通过拼音或部首(键)找到字的解释(值)。
- 课程表:星期几(键)对应课程名称(值)。
- 成绩单:学号(键)对应分数(值)。
- 优惠券:券码(键)对应折扣金额(值)。
在这些场景中,我们总是想根据一个唯一标识快速找到与之相关联的信息。unordered_map 就是专门干这个的。它存储的不是单个元素,而是一组 键值对(key-value pair)。每个键是唯一的(不能有两个相同的键),值可以重复。
二、哈希表的工作原理:为什么能“嗖”一下找到?
unordered_map 底层是一个哈希表,结构有点像一排带编号的抽屉(专业叫“桶”)。
- 当你插入一个键值对(比如
{ "apple", 5 }),哈希函数会计算键"apple"的哈希值,然后根据这个值决定放到哪个抽屉里。 - 当你查找键
"apple"时,相同的哈希函数立刻算出它应该在哪个抽屉,然后直接去那个抽屉里找,不需要和其他抽屉比较。 - 如果两个不同的键恰好被分到同一个抽屉(称为哈希冲突),
unordered_map会用链表或红黑树把它们串起来,查找时还是要在这个小范围内比较,但冲突很少发生,所以平均复杂度仍然是 O(1)。
关键点:哈希函数只对键计算,值是不参与哈希计算的。所以两个键即使有相同的值(比如 { "apple", 5 } 和 { "banana", 5 }),因为键不同,它们会放在不同的抽屉里。
三、unordered_map 常用操作详解
3.1 创建与插入
创建 unordered_map 时需要指定键的类型和值的类型:
unordered_map<string, int> fruit_map; // 键是字符串,值是整数
插入有三种方式:
fruit_map.insert({"apple", 5}); // 方式1:用insert传入花括号初始化的键值对
fruit_map["banana"] = 3; // 方式2:用[]运算符,如果键不存在会先创建默认值,然后赋值
fruit_map.insert(make_pair("orange", 7)); // 方式3:用make_pair构造pair
注意:insert 在键已存在时不会覆盖已有值,而是返回一个 pair<iterator, bool>,其中 bool 表示是否插入成功。而 [] 在键已存在时会覆盖旧值。
3.2 访问与修改
- 使用
[]:m["apple"]返回与键关联的值的引用。如果键不存在,它会自动插入一个默认值(比如 int 为 0)并返回该默认值的引用。这可能会带来隐藏的 bug,后面会讲。 - 使用
at:m.at("apple")返回值的引用,如果键不存在会抛出out_of_range异常,更安全。 - 修改:直接给
[]或at返回的引用赋值,如m["apple"] = 10;或m.at("apple") = 10;。
3.3 查找与判断存在
m.find(key):返回迭代器,指向找到的键值对;如果没找到则返回m.end()。迭代器指向pair<const Key, T>,可用it->first和it->second访问键和值。m.count(key):返回该键出现的次数,对unordered_map来说只能是 0 或 1(因为键唯一)。常用于快速判断是否存在。- 判断是否为空:
m.empty(),返回bool。
3.4 删除与清空
m.erase(key):删除指定键及其值,返回删除的元素个数(0 或 1)。m.clear():清空所有元素。
3.5 遍历(顺序不确定)
unordered_map 不保证元素的顺序,遍历时每次可能得到不同的顺序。使用范围 for 循环:
for (const auto& pair : m) {
// pair.first 是键,pair.second 是值
cout << pair.first << ": " << pair.second << endl;
}
也可以使用迭代器。
下面用一张表总结常用成员函数:
| 函数 | 说明 | 示例 |
|---|---|---|
insert({key, val}) | 插入键值对,如果键已存在则失败。返回 pair<iterator, bool> | m.insert({"apple", 5}); |
erase(key) | 删除指定键及其值,返回删除的元素个数(0或1) | m.erase("apple"); |
find(key) | 查找键,返回迭代器,找不到返回 end()。迭代器指向 pair<const Key, T> | auto it = m.find("apple"); |
count(key) | 返回指定键的个数(0或1) | if (m.count("apple")) |
operator[key] | 访问或修改与键关联的值。如果键不存在,会自动插入默认值并返回引用 | m["apple"] = 10; |
at(key) | 访问与键关联的值,如果键不存在抛出 out_of_range 异常 | int v = m.at("apple"); |
size() | 返回键值对个数 | int n = m.size(); |
empty() | 判断是否为空 | if (m.empty()) ... |
clear() | 清空所有元素 | m.clear(); |
四、新手容易掉进去的坑
4.1 误区一:[] 会偷偷插入不存在的键
unordered_map<string, int> m;
int val = m["pear"]; // pear不存在,这行代码会向m中插入一个{"pear", 0}的键值对!
cout << m.size(); // 输出1,因为m中多了一个pear
如果你只是想检查键是否存在,千万别用 []。应该用 find 或 count。如果你需要读取值且希望键不存在时得到默认值,Python 的 dict.get(key, default) 更安全,C++ 里可以自己写判断:
int val = m.count("pear") ? m["pear"] : 0; // 先判断再读
4.2 误区二:遍历时修改键或删除当前元素导致迭代器失效
在遍历 unordered_map 时,如果删除当前迭代器指向的元素,迭代器会失效。正确做法是先用临时变量保存下一个迭代器,或者用 erase 返回的下一个迭代器(C++11 后支持):
// 错误:删除当前元素后it失效
for (auto it = m.begin(); it != m.end(); ++it) {
if (it->second == 0) m.erase(it); // 危险!
}
// 正确:使用erase返回下一个迭代器
for (auto it = m.begin(); it != m.end(); ) {
if (it->second == 0) it = m.erase(it);
else ++it;
}
4.3 误区三:依赖元素顺序
因为 unordered_map 是无序的,千万不要假设遍历顺序和插入顺序相同。如果需要有序性,请使用 map(底层红黑树,按键排序)或 unordered_map 自己维护一个列表记录插入顺序。
五、完整可运行的代码示例
5.1 学生成绩管理系统(C++)
假设你要管理一个班级的学生成绩,用学号(整数)作为键、分数(双精度)作为值。演示插入、查找、修改、删除和遍历。
#include <iostream>
#include <unordered_map> // 包含unordered_map头文件
#include <string>
using namespace std;
int main() {
// 创建一个从int到double的unordered_map,存储学号和成绩
unordered_map<int, double> score_map; // 键:学号(int),值:成绩(double)
// 插入三个学生的成绩
score_map[1001] = 92.5; // 学号1001,成绩92.5
score_map.insert({1002, 88.0}); // 学号1002,成绩88.0
score_map.insert(make_pair(1003, 76.3)); // 学号1003,成绩76.3
// 尝试插入已存在的学号(1001),不会覆盖
auto result = score_map.insert({1001, 99.0}); // 返回pair,second=false
if (!result.second) {
cout << "学号1001已存在,当前成绩为 " << result.first->second << endl;
}
// 查找学号1002的成绩
int id = 1002;
auto it = score_map.find(id);
if (it != score_map.end()) {
cout << "学号 " << it->first << " 的成绩是 " << it->second << endl;
}
// 修改成绩:把1001的成绩改为95.0
score_map[1001] = 95.0; // 使用[]直接修改
score_map.at(1003) = 80.0; // 使用at修改,如果1003不存在会抛异常
// 使用count判断学号1004是否存在
if (score_map.count(1004) == 0) {
cout << "学号1004不存在" << endl;
}
// 遍历所有键值对
cout << "当前成绩表:" << endl;
for (const auto& pair : score_map) {
cout << "学号: " << pair.first << " 成绩: " << pair.second << endl;
}
// 删除学号1003
int erased = score_map.erase(1003); // 返回1(成功删除)
cout << "删除了 " << erased << " 个学生" << endl;
// 检查大小
cout << "现在有 " << score_map.size() << " 个学生" << endl;
// 清空
score_map.clear();
cout << "清空后是否为空?" << (score_map.empty() ? "是" : "否") << endl;
return 0;
}
5.2 Python等价实现(字典)
Python 的字典(dict)和 C++ 的 unordered_map 行为几乎一样,但有一些细微差别(比如 [] 不会自动插入,不存在的键会报 KeyError)。
# 创建字典,存储学号和成绩
score_map = {} # 空字典
# 插入键值对
score_map[1001] = 92.5 # 直接赋值
score_map[1002] = 88.0
score_map[1003] = 76.3
# 重复赋值会覆盖原有值
score_map[1001] = 95.0 # 改为95.0
# 查找:用in判断是否存在
id_to_find = 1002
if id_to_find in score_map:
print(f"学号 {id_to_find} 的成绩是 {score_map[id_to_find]}")
# 使用get方法安全获取,如果不存在返回None或指定默认值
val = score_map.get(1004, 0) # 学号1004不存在,返回0,不会插入新键
print(f"学号1004的成绩(若不存在返回0): {val}")
# 使用setdefault可以插入默认值(如果不存在)
score_map.setdefault(1004, 60.0) # 1004不存在,插入并返回60.0
score_map.setdefault(1001, 100.0) # 1001已存在,不改变,返回95.0
print(f"学号1004的成绩: {score_map[1004]}")
# 遍历所有键值对
print("当前成绩表:")
for id_, score in score_map.items():
print(f"学号: {id_} 成绩: {score}")
# 删除键
del score_map[1003] # 如果键不存在会报KeyError
print("删除1003后大小:", len(score_map))
# 更安全的删除使用pop
removed = score_map.pop(1004, None) # 存在则删除并返回值,否则返回None
print(f"删除了学号1004,成绩为 {removed}")
5.3 综合应用:统计文章中单词出现次数(C++)
这是一个非常经典的应用:用 unordered_map 统计每个单词出现的次数。键是单词,值是出现次数。
#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream> // 用于分割字符串
using namespace std;
int main() {
string article = "apple banana apple orange banana banana apple grape";
unordered_map<string, int> word_count; // 键:单词,值:出现次数
// 使用字符串流按空格分割单词
istringstream stream(article);
string word;
while (stream >> word) {
// 每次遇到一个单词,将其计数加1
// 如果单词第一次出现,[]会插入默认值0,然后自增变成1
word_count[word]++; // 等价于: word_count[word] = word_count[word] + 1;
}
// 输出统计结果
cout << "单词出现次数统计:" << endl;
for (const auto& pair : word_count) {
cout << pair.first << " : " << pair.second << endl;
}
// 查找"banana"的次数
string target = "banana";
if (word_count.count(target)) {
cout << target << " 出现了 " << word_count[target] << " 次" << endl;
}
return 0;
}
运行结果示例(顺序可能不同):
单词出现次数统计:
apple : 2
banana : 3
orange : 1
grape : 1
banana 出现了 3 次
六、总结与进一步学习方向
- unordered_map 是一种基于哈希表的关联容器,存储键值对,键唯一,平均 O(1) 查找速度。
- 常用操作:
insert、erase、find、count、[]、at、遍历。 - 需要特别注意
[]的自动插入行为,以及遍历时删除元素导致的迭代器失效。 - 如果要求元素按键有序(比如按拼音顺序),请使用
map(底层红黑树,O(log n))。 - 如果只关心键的集合而不需要值,可用
unordered_set。
接下来你可以继续学习:
- 哈希冲突:当两个不同的键映射到同一个桶时,内部如何解决?
- 自定义类型作为键:如何为自己的结构体提供哈希函数和相等比较?
- 性能调优:如何调整桶的数量和负载因子来优化速度?
- Python字典的进阶用法:defaultdict、OrderedDict、Counter等。
掌握了 unordered_map,你就拥有了一把“快速钥匙”,能够瞬间从海量数据中提取出你想要的任何信息。快去试试用它来解决实际问题吧!
例题精讲
关于unordered_map的查找操作,平均时间复杂度是?
以下关于unordered_map和map的区别,说法错误的是?
在C++中使用unordered_map时,若键已存在,使用下标操作符 m[key] = value 会更新该键对应的值。
下面的C++代码使用unordered_map统计字符串出现次数,请在空白处填入正确的语句。
#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;
int main() {
unordered_map<string, int> freq;
string words[] = {"apple", "banana", "apple", "cherry"};
for (auto& w : words) {
___; // 统计每个单词出现次数
}
cout << freq["apple"]; // 输出应为2
return 0;
}下面的C++代码使用unordered_map存储学生姓名与成绩,并删除成绩低于60的学生,请在空白处填入正确的语句。
#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;
int main() {
unordered_map<string, int> scores = {{"Alice", 85}, {"Bob", 55}, {"Carol", 70}};
for (auto it = scores.begin(); it != scores.end(); ) {
if (it->second < 60) {
___; // 删除当前迭代器指向的元素
} else {
++it;
}
}
cout << scores.size(); // 输出应为2
return 0;
}