5、无序容器unordered系列：哈希表原理、unordered_set/map的使用、自定义哈希函数、性能对比（红黑树vs哈希表）、实战：缓存系统设计

好，咱们今天来聊聊无序容器。说实话，我刚入行那会儿，对哈希表又爱又怕。爱它快，怕它坑。后来踩过几次坑，才真正摸透了它的脾气。

unordered系列容器，说白了就是哈希表的C++实现。它跟map/set最大的区别就一个字：快。平均O(1)的查找速度，比红黑树的O(log n)快了一个量级。但代价是什么？元素无序，而且内存占用更大。

5.1 哈希表原理：桶、哈希函数、冲突解决

哈希表的核心思想很简单：通过一个哈希函数，把key映射到一个数组下标。这个数组的每个位置，我们叫它“桶”（bucket）。

举个例子，假设我们有一个哈希函数 hash(key) = key % 10，那么key=17就会落到第7个桶里。理想情况下，每个桶里最多一个元素，查找就是O(1)。

但现实没那么完美。不同的key可能映射到同一个桶，这就叫哈希冲突。C++标准库用的是“链地址法”——每个桶其实是一个链表，冲突的元素就挂在同一个桶的链表上。

我见过有人把自定义对象塞进unordered_set，结果哈希函数写得稀烂，所有元素都挤到同一个桶里，查找直接退化成O(n)。嗯，那场面，惨不忍睹。

5.2 unordered_set / unordered_map 的基本使用

这两个容器的用法跟set/map几乎一模一样。区别在于：unordered版本不保证元素顺序，但插入和查找更快。

#include <unordered_set>
#include <unordered_map>
#include <iostream>

int main() {
    // unordered_set 基本用法
    std::unordered_set<int> us = {3, 1, 4, 1, 5, 9};
    us.insert(2);
    us.erase(1);
    
    // 注意：遍历顺序是不确定的！
    for (int x : us) {
        std::cout << x << " ";  // 可能是 9 3 4 5 2
    }
    
    // unordered_map 基本用法
    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 << it->second;  // 输出 87
    }
    
    return 0;
}

5.3 自定义哈希函数

这是unordered系列最让人头疼的地方。标准库为基本类型（int、string等）提供了哈希函数，但自定义类型就得自己写。

我曾经接手过一个项目，里面有个自定义的Point类，直接塞进了unordered_set。编译报错，然后有人写了个哈希函数——直接把x和y加起来。你想想看，Point(1,2)和Point(2,1)的哈希值一样，冲突率直接爆炸。

正确的做法是这样的：

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 {
        // 使用boost::hash_combine的思路
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // 混合两个哈希值
    }
};

// 使用
std::unordered_set<Point, PointHash> points;
points.insert({1, 2});
points.insert({3, 4});

5.4 性能对比：红黑树 vs 哈希表

很多初学者会问：既然哈希表这么快，为什么还要用红黑树？

答案是：没有银弹。两种数据结构各有优劣。

特性	红黑树 (map/set)	哈希表 (unordered_map/set)
查找时间复杂度	O(log n)	平均O(1)，最坏O(n)
插入时间复杂度	O(log n)	平均O(1)，最坏O(n)
元素顺序	有序（按key排序）	无序
内存占用	较低（每个节点只存数据+指针）	较高（需要预分配桶数组）
范围查询	支持（lower_bound/upper_bound）	不支持
迭代器稳定性	插入/删除不影响其他迭代器	rehash时所有迭代器失效

我个人习惯这样选：

• 需要有序遍历或范围查询 → 用map/set
• 只需要按键查找，不关心顺序 → 用unordered版本
• 数据量小（几十个元素）→ 随便选，差别不大
• 数据量大且对性能敏感 → 优先考虑unordered，但要做好哈希函数

5.5 实战：缓存系统设计

好了，理论说完了，咱们来点实战。我设计一个简单的LRU缓存系统，用unordered_map实现O(1)查找。

LRU（Least Recently Used）的核心思想：当缓存满了，淘汰最久没被访问的元素。这需要两个数据结构的配合：

• unordered_map：快速查找key是否存在
• 双向链表：维护访问顺序

#include <unordered_map>
#include <list>
#include <utility>

template<typename Key, typename Value>
class LRUCache {
private:
    size_t capacity_;
    std::list<std::pair<Key, Value>> items_;  // 双向链表，维护访问顺序
    std::unordered_map<Key, 
        typename std::list<std::pair<Key, Value>>::iterator> cache_;
    
public:
    LRUCache(size_t cap) : capacity_(cap) {}
    
    Value get(const Key& key) {
        auto it = cache_.find(key);
        if (it == cache_.end()) {
            throw std::runtime_error("Key not found");
        }
        // 把访问的元素移到链表头部
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }
    
    void put(const Key& key, const Value& value) {
        auto it = cache_.find(key);
        if (it != cache_.end()) {
            // key已存在，更新值并移到头部
            it->second->second = value;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        
        // 如果缓存满了，淘汰最久未使用的（链表尾部）
        if (cache_.size() >= capacity_) {
            auto last = items_.back();
            cache_.erase(last.first);
            items_.pop_back();
        }
        
        // 插入新元素到链表头部
        items_.emplace_front(key, value);
        cache_[key] = items_.begin();
    }
    
    bool exists(const Key& key) const {
        return cache_.find(key) != cache_.end();
    }
};

这个缓存系统我在一个高并发的API网关里用过。当时每秒要处理上万次请求，每个请求都要查用户权限。用这个LRU缓存，命中率大概70%，响应时间从原来的15ms降到了2ms。嗯，效果立竿见影。

最后说一句：unordered系列虽然快，但别滥用。如果你的数据量很小，或者需要频繁遍历，vector+二分查找可能更合适。选对工具，比用好工具更重要。

---

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