C++哈希表的概念 - 七级 | C++ & Algorithm 编程研习社

超级抽屉——C++哈希表（unordered_map）入门详解

想象一下，你有一个大书包，里面有很多小口袋，每个口袋上贴着一个标签，比如“铅笔”、“橡皮”、“尺子”。当你想找橡皮时，直接看向“橡皮”标签的口袋，一下就拿到了，不需要翻遍整个书包。C++里的哈希表就像这个书包，每个数据都有一个“标签”（叫做键），通过一个神奇的“哈希函数”可以把标签快速转换成一个小抽屉的编号，数据就放在那个抽屉里。

在编程中，我们经常需要快速查找某个东西，比如“小明”的考试成绩、“苹果”的价格。如果数据成千上万，用普通数组挨个找会很慢。哈希表就是专门解决这种“快速查找”问题的工具，它能让查找速度快得像开锁一样：只要钥匙（键）正确，一步到位。

1. 哈希表的核心理念：空间换时间

哈希表先准备一个很大的数组（就像一连排抽屉），然后每次存入数据时，用哈希函数算出键应该放在哪个位置。例如，存储名字“小明”对应的分数95分，哈希函数可能会根据“小明”这两个字算出第3号抽屉，就把95分放进去。以后查找“小明”的分数时，同样计算哈希值，直接去第3号抽屉，一步到位。

生活中的例子：学校图书馆的书架上，每本书都有一个编号（索书号）。图书管理员把书按照编号分类放在不同格子里。你想找《哈利·波特》，只要知道它的索书号（比如 I561.84），直接去那个格子就能找到，不用一本一本翻。哈希函数就相当于把书名转换成索书号的“魔法公式”。

2. 哈希函数：把“钥匙”变成“抽屉号”

哈希函数是一个数学函数，它接受一个“键”（比如字符串、整数），输出一个整数（抽屉的编号）。这个输出叫作哈希值。好的哈希函数能尽量让不同的键得到不同的哈希值，避免冲突。

C++标准库已经为常见的类型（如整数、字符串、浮点数）提供了哈希函数，我们直接用就行。比如 std::hash。

举个例子：假设我们有一个哈希函数，它把字符串中每个字母的ASCII码加起来，再对数组大小取余。比如“apple”的字母和为：97+112+112+108+101=530，如果数组有10个抽屉，530 % 10 = 0，就把“apple”对应的价格放进0号抽屉。当然，真正的哈希函数比这个复杂，但原理类似。

代码片段：手动演示哈希函数计算（仅示意，实际不会这样用）

#include <iostream>
#include <string>
using namespace std;

int simpleHash(const string& key, int tableSize) {
    int sum = 0;
    for (char c : key) {
        sum += (int)c;          // 将字符转成ASCII码累加
    }
    return sum % tableSize;     // 取余得到抽屉编号
}

int main() {
    string fruit = "apple";
    int drawer = simpleHash(fruit, 10);
    cout << "苹果应该放在" << drawer << "号抽屉" << endl;  // 输出0号
    return 0;
}

（注意：这段代码只是演示概念，实际C++哈希表内部会使用更复杂的哈希算法。）

3. 哈希冲突：两个不同的钥匙打开同一个抽屉？

有时候两个不同的键会算出同一个抽屉编号，这就叫哈希冲突。比如“apple”和“banana”可能算出同一个余数，都想去同一个抽屉。怎么办？C++的哈希表（比如unordered_map）会用链表法解决：在同一个抽屉里放一个链表，把所有冲突的数据串起来。查找时先到抽屉，再沿着链表一个一个比对键，直到找到正确的那个。

小朋友不用担心：C++标准库已经帮我们处理好冲突了，你只需要正常使用，性能依然很快（平均情况下冲突很少）。

如果冲突很多会怎样？ 查找速度会变慢，但哈希表会动态扩容（增加抽屉数量）来减少冲突，所以大多数时候速度都很快。

4. C++中的哈希表：`unordered_map`

在C++中，哈希表对应的类型是 unordered_map，它位于头文件 <unordered_map> 中。它的名字里“unordered”表示元素不按顺序排列（不像map那样按键从小到大排序），但换来的是更快的查找速度（平均O(1)）。

常用操作：

插入：fruitPrice["apple"] = 5; 或者 fruitPrice.insert({"apple", 5});
查找：auto it = fruitPrice.find("apple"); 如果找到，it 指向键值对，it->first是键，it->second是值。
判断键是否存在：if (fruitPrice.count("apple") > 0)
遍历：for (auto& p : fruitPrice) { cout << p.first << " : " << p.second; }

注意：用 [] 访问不存在的键时，会自动插入一个键并给值赋默认值（比如整数默认0）。这有时会引起错误，特别是你想判断键是否存在时，应该用 find 或 count。

5. 新手容易犯的错误

忘记包含头文件：必须写 #include <unordered_map>，否则编译报错。
用 [] 误添加了默认值：比如想检查“香蕉”是否在表中，却写了 if (fruitPrice["banana"] == 3)，如果“香蕉”不存在，它会被插入并赋值为0，导致误判。正确做法是先用 find 或 count。
键类型不支持哈希：unordered_map 要求键类型必须能计算哈希值。基本类型（int, string等）没问题，但如果用自定义类（struct/class）做键，需要自己提供哈希函数和相等比较。初学者先别碰自定义类型，用字符串或整数就好。
混淆 map 和 unordered_map：map 是红黑树实现，元素有序（从小到大），但插入查找慢一点（O(log n)）；unordered_map 哈希表，无序但更快。如果不需要顺序，优先用 unordered_map。
忘记 end() 迭代器检查：find 返回的迭代器如果等于 end()，表示没找到，直接访问 it->second 会崩溃。

6. 完整可运行示例：学生成绩管理系统

下面是一个更完整的示例，演示插入、查找、判断是否存在、遍历以及处理错误情况。

#include <iostream>
#include <unordered_map>   // 哈希表的头文件
#include <string>
using namespace std;

int main() {
    // 创建一个哈希表，键是字符串（学生姓名），值是整数（分数）
    unordered_map<string, int> scores;

    // 插入几个学生的成绩
    scores["XiaoMing"] = 95;
    scores["XiaoHong"] = 88;
    scores["XiaoGang"] = 72;
    // 也可以使用 insert 方法
    scores.insert({"XiaoLi", 91});

    // 1. 查找小明成绩
    string name = "XiaoMing";
    auto it = scores.find(name);           // find返回迭代器
    if (it != scores.end()) {
        cout << name << " 的成绩是 " << it->second << " 分" << endl;
    } else {
        cout << "没有找到 " << name << endl;
    }

    // 2. 判断小红是否有成绩（用count）
    if (scores.count("XiaoHong") > 0) {
        cout << "小红的成绩存在，为 " << scores["XiaoHong"] << " 分" << endl;
    }

    // 3. 错误示例：用[]判断会导致插入默认值
    // 假设“小王”不在表中，下面代码会插入“小王”并赋值为0
    if (scores["XiaoWang"] == 0) {        // 这一行会插入“小王”:0
        cout << "小王不存在？其实现在它已经被添加了，分数为0" << endl;
    }
    // 正确做法：先用count
    string checkName = "XiaoWang";
    if (scores.count(checkName) == 0) {
        cout << checkName << " 确实不在表中" << endl;
    } else {
        cout << checkName << " 的分数是 " << scores[checkName] << endl;
    }

    // 4. 遍历所有学生（注意顺序是不确定的）
    cout << "\n所有学生成绩（无序输出）：" << endl;
    for (auto& pair : scores) {            // pair 是键值对
        cout << pair.first << " : " << pair.second << " 分" << endl;
    }

    // 5. 删除一个学生（可选）
    scores.erase("XiaoGang");
    if (scores.find("XiaoGang") == scores.end()) {
        cout << "\n已删除小刚" << endl;
    }

    return 0;
}

运行结果示意（每次可能顺序不同）：

XiaoMing 的成绩是 95 分
小红的成绩存在，为 88 分
小王不存在？其实现在它已经被添加了，分数为0
小王 确实不在表中

所有学生成绩（无序输出）：
XiaoLi : 91 分
XiaoHong : 88 分
XiaoMing : 95 分
XiaoWang : 0 分

已删除小刚

7. 相关指引与拓展

如果你需要按键排序的容器，请使用 map（红黑树）——它按键从小到大排列，但插入和查找比哈希表慢一丁点。
如果你只需要存储键，而不需要值，可以使用 unordered_set（哈希集合），用法类似，只有键没有值。
哈希表在STL中还有很多变种：unordered_multimap（允许重复键），但初学者掌握基本的 unordered_map 就够了。
如果你想深入了解哈希表的实现原理，可以搜索“哈希表链表法开放地址法”，或者学习如何为自定义类型写哈希函数（以后在项目中会用到）。

哈希表就像一个超级书包，任何东西只要给出标签，就能瞬间找到。它的查找速度非常快，平均只需要一步，特别适合处理大量数据。但在C++里使用哈希表时，需要包含头文件 <unordered_map>，并且键类型必须支持“哈希计算”，比如整数、字符串等常见类型都可以。如果使用自定义类型，需要自己提供哈希函数，等学到后面再了解吧。现在就用它来快速存取你的各种数据吧！

例题精讲