CC++ & Algorithm

unordered_map哈希映射——像带标签的超级储物柜

较难2
语言版本:通用
概述:用字典和电话本比喻哈希映射,讲解unordered_map存储键值对、通过键快速查找值的原理和用法,并给出C++和Python代码示例。

哈希映射unordered_map——像随身携带的智能电话本

你有没有遇到过这种情况?你想快速找到某个朋友的电话号码,但整本厚厚的电话本得从第一页翻到最后一页。如果电话本能自动根据名字“嗖”的一下定位到号码,那该多好!在编程世界里,unordered_map 就是这样一个“智能电话本”:你告诉它一个“键”(比如“张三”),它立刻就能返回对应的“值”(比如“13800138000”),而且速度飞快,平均只需要一步。

更神奇的是,它就像一个带标签的超级储物柜:每个柜子外面贴着一个标签(键),打开柜子里面放着对应的物品(值)。你想找“语文书”,系统直接告诉你“在15号柜”,而不是让你把100个柜子一个个打开看。这种结构叫哈希映射,在C++中用 unordered_map 实现,在Python中直接用 dict(字典)。

一、从生活走进代码:为什么需要映射?

先看几个生活中的“映射”例子:

  • 字典:通过拼音或部首(键)找到字的解释(值)。
  • 课程表:星期几(键)对应课程名称(值)。
  • 成绩单:学号(键)对应分数(值)。
  • 优惠券:券码(键)对应折扣金额(值)。

在这些场景中,我们总是想根据一个唯一标识快速找到与之相关联的信息unordered_map 就是专门干这个的。它存储的不是单个元素,而是一组 键值对(key-value pair)。每个键是唯一的(不能有两个相同的键),值可以重复。

二、哈希表的工作原理:为什么能“嗖”一下找到?

unordered_map 底层是一个哈希表,结构有点像一排带编号的抽屉(专业叫“桶”)。

  1. 当你插入一个键值对(比如 { "apple", 5 }),哈希函数会计算键 "apple" 的哈希值,然后根据这个值决定放到哪个抽屉里。
  2. 当你查找键 "apple" 时,相同的哈希函数立刻算出它应该在哪个抽屉,然后直接去那个抽屉里找,不需要和其他抽屉比较
  3. 如果两个不同的键恰好被分到同一个抽屉(称为哈希冲突),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,后面会讲。
  • 使用 atm.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->firstit->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

如果你只是想检查键是否存在,千万别用 []。应该用 findcount。如果你需要读取值且希望键不存在时得到默认值,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) 查找速度
  • 常用操作:inserterasefindcount[]at、遍历。
  • 需要特别注意 [] 的自动插入行为,以及遍历时删除元素导致的迭代器失效。
  • 如果要求元素按键有序(比如按拼音顺序),请使用 map(底层红黑树,O(log n))。
  • 如果只关心键的集合而不需要值,可用 unordered_set

接下来你可以继续学习:

  • 哈希冲突:当两个不同的键映射到同一个桶时,内部如何解决?
  • 自定义类型作为键:如何为自己的结构体提供哈希函数和相等比较?
  • 性能调优:如何调整桶的数量和负载因子来优化速度?
  • Python字典的进阶用法:defaultdict、OrderedDict、Counter等。

掌握了 unordered_map,你就拥有了一把“快速钥匙”,能够瞬间从海量数据中提取出你想要的任何信息。快去试试用它来解决实际问题吧!

例题精讲

1单选题

关于unordered_map的查找操作,平均时间复杂度是?

AO(1)
BO(log n)
CO(n)
DO(n^2)
2单选题

以下关于unordered_map和map的区别,说法错误的是?

Aunordered_map基于哈希表,map基于红黑树
Bunordered_map中键的顺序是无序的,map中键是按升序排列的
Cunordered_map的查找速度通常比map快
Dunordered_map支持通过自定义比较函数来改变键的排序规则
3判断题

在C++中使用unordered_map时,若键已存在,使用下标操作符 m[key] = value 会更新该键对应的值。

4填空题
下面的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;
}
5填空题
下面的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;
}