C++ unordered_map 与 unordered_set 的实现思路

也可以把它理解成桶数组里保存了某种指针，真正的数据节点挂在后面。具体是链表、节点数组，还是别的实现细节，要看标准库版本；但对使用者来说，核心逻辑没变。

冲突怎么处理

哈希冲突一定会发生，区别只在于发生得多不多。不同 key 算出来的哈希值，最后可能落到同一个桶里。这个时候就不能只靠数组下标直接命中，只能继续在桶里找。

示意如下：

[ 桶 0 ] [ 桶 1 ] [ 桶 2 ] [ 桶 3 ] [ 桶 4 ]
              |
              v
          key1 -> key2 -> key3

这里 key1、key2、key3 都落在桶 1。插入时只要接到这个桶下面就行，查找时则要顺着桶内结构逐个比对。

三、为什么平均能做到 O(1)

哈希表的快，不是因为它从来不冲突，而是因为大多数时候冲突不多。

如果桶分布比较均匀，查找时先通过哈希函数定位桶，再在桶里做很短的遍历，平均成本就接近 O(1)。这也是它适合做高频查找、去重、索引映射的原因。

真正麻烦的是冲突堆在一起。那时候一次查找就要扫完整个桶，最坏情况会退化得很难看。标准库会通过扩容和 rehash 来缓解这个问题：桶数量变多，元素重新分布，单个桶里的压力就小了。

四、rehash 和负载因子

负载因子描述的是元素数量和桶数量的比例。比例越高，桶越容易变长，冲突也越多。

C++ 里可以通过 max_load_factor 控制阈值，通过 rehash 主动调整桶数量。实际开发里，我通常不会频繁碰这两个接口，但如果你知道数据规模大概有多大，提前 reserve 或 rehash 一下，效果比让它边跑边扩更稳。

rehash 发生时，大致流程就是：

1. 申请更多桶；
2. 重新计算每个元素该落到哪个桶；
3. 把旧桶里的节点搬过去。

这个过程不是免费午餐，扩容本身有成本，所以别把它当成'无限顺滑'的事情。你一旦在热点路径里反复触发扩容，延迟会抖得很明显。

五、查找和插入的实际写法

unordered_map 查找

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;
    map["apple"] = 1;
    map["banana"] = 2;
    map["cherry"] = 3;

    std::string key = "banana";
    if (map.find(key) != map.end()) {
        std::cout << "Found: " << key << " => " << map[key] << std::endl;
    } else {
        std::cout << key << " not found." << std::endl;
    }
    return 0;
}

unordered_set 查找

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> set = {1, 2, 3, 4, 5};
    int key = 3;
    if (set.find(key) != set.end()) {
        std::cout << "Found: " << key << std::endl;
    } else {
        std::cout << key << " not found." << std::endl;
    }
    return 0;
}

这两段代码都很直白：find 找到了就返回迭代器，没找到就返回 end()。这也是我更倾向于推荐的写法，先查再用，比直接下标访问更稳，尤其是 unordered_map 里 operator[] 可能会顺手帮你插入一个新元素。

六、自定义哈希函数

默认的 std::hash 覆盖了很多常见类型，但一旦 key 是自定义结构体，就得自己定义哈希规则，同时还要提供相等比较。

#include <iostream>
#include <unordered_map>
#include <functional>

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

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.x) ^ (std::hash<int>()(k.y) << 1);
    }
};

int main() {
    std::unordered_map<Key, int, KeyHash> map;
    map[{1, 2}] = 3;
    Key key = {1, 2};
    if (map.find(key) != map.end()) {
        std::cout << "Found key (1, 2) with value: " << map[key] << std::endl;
    } else {
        std::cout << "Key (1, 2) not found." << std::endl;
    }
    return 0;
}

这里有个很现实的问题：哈希函数写得能跑，不代表写得好。^ 拼起来的方式足够简单，但分布质量一般；如果 key 组合比较复杂，碰撞还是会偏多。很多场景下它够用，真要压性能，就得认真看哈希分布，而不是只图省事。

七、几个实际使用时容易踩的点

• 负载因子太高，冲突会明显变多，查找速度跟着掉。
• unordered_map 里如果你只是想判断 key 是否存在，优先用 find，别一上来就用 operator[]。
• 自定义 key 时，hash 和 == 必须配套，不然容器行为会很怪。
• 如果需要稳定顺序，别用 unordered_map / unordered_set 硬顶，直接换 map / set 更省心。

八、结语

unordered_map 和 unordered_set 的核心并不复杂：哈希定位桶，桶内处理冲突，必要时扩容重排。它们的优势是平均查找快，代价是顺序不可控，极端冲突时性能会抖。

理解这层逻辑之后，很多使用上的选择就比较顺了：什么时候该提前扩容，什么时候该写自定义哈希，什么时候该换成有序容器，基本都能判断出来。