15、unordered系列容器（上）：哈希表原理、unordered_set与unordered_map、自定义哈希函数

好，咱们今天来聊聊C++里一个非常实用的系列——unordered容器。说实话，我早年刚学STL的时候，用的最多的就是map和set，觉得它们已经够好了。直到后来在一个高并发的日志处理项目中，数据量一上来，map的插入和查找速度明显拖了后腿。那时候我才意识到，有序容器不是万能的。于是，我认真研究了一下unordered系列，从此一发不可收拾。

15.1 哈希表：unordered容器的灵魂

unordered系列容器的底层实现，说白了就是哈希表。你想想看，为什么它叫“unordered”？因为它不排序。那它凭什么快？就凭哈希表这个数据结构。

哈希表的核心思想很简单：通过一个哈希函数，把关键字映射到一个数组的某个位置。比如你要存一个整数42，哈希函数算出它应该放在数组的第5个槽位，那你就直接放进去。查找的时候也一样，直接算哈希值，然后去那个位置取。时间复杂度平均是O(1)，比红黑树的O(log n)快不少。

但哈希表也有个绕不开的问题——哈希冲突。不同的关键字可能算出同一个位置。比如42和84，如果哈希函数是取模10，那它们都会映射到位置2。怎么办？C++ STL用的是链地址法：每个槽位挂一个链表（或者更高效的数据结构），冲突的元素就链在后面。

我在项目中遇到过一个问题：某个模块用unordered_map存了几百万个短字符串，结果性能突然下降。排查后发现是哈希函数太弱，大量字符串冲突了，链表变得很长。后来换了更好的哈希函数，性能直接翻倍。嗯，这里要注意：不要迷信默认哈希函数，尤其是对自定义类型。

15.2 unordered_set：只存键，不存值

unordered_set，说白了就是一个哈希表实现的集合。它只存储键，不存储值。每个元素在集合中唯一，重复插入会被忽略。

它的典型应用场景是什么？去重。比如你从文件里读了一堆ID，想快速知道哪些是重复的，用unordered_set就对了。

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> ids;
    ids.insert(100);
    ids.insert(200);
    ids.insert(100);  // 重复，不会插入
    ids.insert(300);

    std::cout < "集合大小: " << ids.size() << std::endl;  // 输出3

    // 查找
    if (ids.find(200) != ids.end()) {
        std::cout << "找到了200" << std::endl;
    }

    return 0;
}

我个人习惯用find而不是count来判断元素是否存在。虽然count也能用，但find语义更清晰——我是在找东西，不是在数个数。

15.3 unordered_map：键值对的哈希表

unordered_map是unordered_set的“升级版”——每个键关联一个值。它的用法和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;

    // 遍历
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Bob的分数: " << it->second << std::endl;
    }

    return 0;
}

这里有个坑，我曾经踩过：用operator[]访问不存在的键时，会自动插入一个默认值。比如scores["David"]，如果David不存在，它会插入一个键为"David"、值为0的元素。这有时候不是你想要的。所以，如果你只是想检查键是否存在，用find更安全。

15.4 自定义哈希函数：让unordered容器支持你的类型

默认情况下，unordered容器只支持基本类型（int、string等）和部分STL类型。如果你想用自定义类型作为键，比如一个Point结构体，那就得自己提供哈希函数和相等比较函数。

为什么？因为哈希表需要两样东西：哈希值（决定放哪个槽位）和相等判断（解决冲突时判断两个键是否相同）。

来看一个例子：

#include <unordered_set>
#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // 一个简单的组合哈希：把x和y混合起来
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});  // 重复，不会插入

    std::cout << "点的数量: " << points.size() << std::endl;  // 输出2

    return 0;
}

这里我用了std::hash<int>()来分别计算x和y的哈希值，然后用异或和移位把它们组合起来。这个组合方式不是唯一的，但原则是：尽量让不同的(x,y)对产生不同的哈希值。

我曾经在项目中用了一个很糟糕的哈希函数：直接把两个int相加。结果所有对称的点（比如(1,2)和(2,1)）都冲突了，性能惨不忍睹。后来改成了上面的异或+移位方式，问题就解决了。

如果你用的是C++11或更高版本，还可以用lambda表达式来定义哈希函数，更简洁：

auto hash = [](const Point& p) {
    return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
};
std::unordered_set<Point, decltype(hash)> points(0, hash);

嗯，这里要注意：decltype(hash)是必须的，因为模板参数需要知道哈希函数的类型。

15.5 知识体系总览

为了让你更直观地理解unordered系列容器的核心逻辑，我画了一张图：

这张图把unordered容器的核心脉络理清了：底层是哈希表，它衍生出unordered_set和unordered_map两个主要容器。而自定义哈希函数，则是让这两个容器支持任意类型的关键。

15.6 性能对比与选择建议

最后，我整理了一个简单的对比表，帮你快速决策：

特性	unordered_set	unordered_map	set / map
底层结构	哈希表	哈希表	红黑树
查找速度	平均O(1)	平均O(1)	O(log n)
元素顺序	无序	无序	有序（升序）
迭代器稳定性	rehash时失效	rehash时失效	插入/删除不影响
适用场景	去重、快速存在性检查	快速键值查找、缓存	需要有序遍历、范围查询

我个人习惯是：只要不需要排序，优先用unordered系列。性能优势太明显了。但如果你需要按顺序遍历元素，或者要做范围查询（比如找出所有大于某个值的元素），那就老老实实用set/map。

好了，关于unordered系列容器的上半部分就讲到这里。哈希表的原理、unordered_set和unordered_map的基本用法、以及如何自定义哈希函数，这些内容已经足够你应付大部分日常开发了。下一节我们会深入讨论unordered_multiset和unordered_multimap，以及一些更高级的用法和性能调优技巧。

---