第二十一章：无序容器与哈希

说实话，刚学C++那会儿，我对unordered_set和unordered_map是有点抵触的。为啥？因为set和map用得好好的，红黑树多优雅啊。直到我在一个项目里处理了上百万条日志数据，才发现红黑树的查找速度开始吃力了。嗯，这时候哈希表就派上用场了。

21.1 无序容器：unordered_set 和 unordered_map

先说说这两个容器是干嘛的。unordered_set存的是不重复的元素集合，unordered_map存的是键值对。它们跟set/map最大的区别就是——无序。

什么叫无序？你插入的顺序和遍历的顺序，大概率不一样。我刚开始用的时候还以为是bug，后来才反应过来：哈希表本来就不保证顺序。

unordered_set 基本用法

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> us = {3, 1, 4, 1, 5, 9};
    
    // 插入
    us.insert(2);
    us.insert(6);
    
    // 查找
    if (us.find(4) != us.end()) {
        std::cout << "找到了4" << std::endl;
    }
    
    // 删除
    us.erase(1);
    
    // 遍历（注意：顺序不固定）
    for (int x : us) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

你看，重复的1只存了一次。这就是unordered_set的特性——自动去重。

unordered_map 基本用法

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> scores;
    
    // 插入
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    
    // 查找
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Bob的分数: " << it->second << std::endl;
    }
    
    // 遍历
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

21.2 哈希表原理

说白了，哈希表就是一个数组加一个哈希函数。数组的每个位置叫"桶"（bucket），哈希函数把键映射到桶的索引上。

举个例子：假设我们有10个桶，哈希函数是key % 10。那么键23就放到桶3，键47就放到桶7。查找的时候，直接算一下哈希值，去对应的桶里找就行了。时间复杂度O(1)——理想情况下。

但问题来了：如果两个不同的键算出了同一个桶索引呢？比如13和23，% 10都是3。这就叫哈希冲突。

解决冲突：链地址法

C++的unordered_*容器用的是链地址法。每个桶其实是一个链表，冲突的元素都挂在这个链表上。

// 伪代码示意
// 桶0: [空]
// 桶1: [空]
// 桶2: [空]
// 桶3: [13] -> [23] -> [33]
// 桶4: [空]
// ...

查找的时候，先算哈希值找到桶，再在链表里遍历查找。如果链表太长，性能就退化成O(n)。所以哈希表有个重要指标——负载因子（元素个数 / 桶个数）。负载因子越大，冲突概率越高。

21.3 自定义哈希函数

默认情况下，C++为基本类型（int、string、指针等）提供了哈希函数。但如果你用自定义类型做键，就得自己写哈希函数了。

我记得有一次，项目里要用unordered_map存用户信息，键是一个自定义的UserID结构体。编译直接报错——没有哈希函数。嗯，这时候就得自己动手了。

方法一：函数对象

struct UserID {
    std::string name;
    int id;
    
    bool operator==(const UserID& other) const {
        return name == other.name && id == other.id;
    }
};

// 自定义哈希函数对象
struct UserIDHash {
    std::size_t operator()(const UserID& uid) const {
        // 组合哈希值
        return std::hash<std::string>()(uid.name) ^ 
               (std::hash<int>()(uid.id) << 1);
    }
};

int main() {
    std::unordered_map<UserID, std::string, UserIDHash> userMap;
    
    userMap[{"Alice", 1001}] = "管理员";
    userMap[{"Bob", 1002}] = "普通用户";
    
    return 0;
}

方法二：特化std::hash

// 特化std::hash
namespace std {
    template<>
    struct hash<UserID> {
        std::size_t operator()(const UserID& uid) const {
            std::size_t h1 = std::hash<std::string>()(uid.name);
            std::size_t h2 = std::hash<int>()(uid.id);
            return h1 ^ (h2 << 1);
        }
    };
}

// 这样就不用显式指定哈希函数了
std::unordered_map<UserID, std::string> userMap;

21.4 性能对比与选择

操作	unordered_set/map	set/map
查找	平均O(1)，最坏O(n)	O(log n)
插入	平均O(1)，最坏O(n)	O(log n)
删除	平均O(1)，最坏O(n)	O(log n)
遍历顺序	无序	有序（升序）
内存占用	较高（桶数组+链表）	较低（节点+指针）

怎么选？我个人习惯是：需要快速查找就用unordered，需要有序遍历就用ordered。但要注意，如果哈希函数写得不好，unordered的性能可能还不如ordered。

21.5 知识体系总览

下面这张图把本章的核心逻辑串起来了：

21.6 避坑指南

最后分享几个我踩过的坑：

• 迭代器失效：rehash会导致所有迭代器失效。如果你在遍历时插入了大量元素，可能会触发rehash，迭代器就废了。解决办法：提前reserve()。
• 自定义类型必须提供==运算符：哈希函数只负责定位桶，桶内的精确查找还是靠==。忘了写==？编译报错。
• 不要用指针做键：除非你确定指针指向的对象不会变。我见过有人用char*做键，结果两个内容相同的字符串因为地址不同，被当成不同的键。
• 哈希函数要快：哈希函数本身如果太复杂，反而比红黑树还慢。我一般用标准库提供的std::hash组合一下就够了。

好了，这一章就到这里。记住一句话：哈希表不是万能的，但没有哈希表是万万不能的。用对了地方，它就是性能利器。

---

公众号:蓝海资料掘金营，微信deep3321