unordered 容器与哈希原理

定义与作用

C++11 引入的哈希表容器——std::unordered_map、std::unordered_set 及其 multi 变体——提供平均 O(1) 的查找、插入和删除，基于哈希表实现，元素不保证顺序。

#include <unordered_map>
#include <unordered_set>

std::unordered_map<std::string, int> cache;
cache["飞翔科技-用户1"] = 100;

std::unordered_set<int> ids{1, 2, 3, 3, 2};  // {1, 2, 3} 无序
特性map/setunordered_map/set
底层红黑树哈希表（开链法）
查找O(log n)平均 O(1)，最坏 O(n)
有序是否
内存较低较高（桶 + 链表）
键要求operator<std::hash<Key> + operator==

核心原理

哈希表结构（开链法）

负载因子与 rehash

完整示例

示例一：飞翔科技用户会话缓存

场景说明：小崔用 unordered_map 实现飞翔科技的分布式会话缓存，自定义哈希函数优化性能。

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

struct SessionInfo {
    std::string userId;
    std::string token;
    std::chrono::system_clock::time_point lastAccess;
    int ttlSeconds;
};

class SessionCache {
public:
    // 插入或更新会话
    void upsert(const std::string& token, SessionInfo info) {
        cache_[token] = std::move(info);
    }

    // 查找会话（O(1) 平均）
    const SessionInfo* get(const std::string& token) const {
        auto it = cache_.find(token);
        return it != cache_.end() ? &it->second : nullptr;
    }

    // 移除过期会话
    void evict(int maxAgeSeconds) {
        auto now = std::chrono::system_clock::now();
        for (auto it = cache_.begin(); it != cache_.end(); ) {
            auto age = std::chrono::duration_cast<std::chrono::seconds>(
                now - it->second.lastAccess).count();
            if (age > maxAgeSeconds)
                it = cache_.erase(it);
            else
                ++it;
        }
    }

    // 查看负载状态
    void stats() const {
        std::cout << "桶数: " << cache_.bucket_count()
                  << ", 元素数: " << cache_.size()
                  << ", 负载因子: " << cache_.load_factor()
                  << ", 最大负载因子: " << cache_.max_load_factor() << "\n";
    }

private:
    std::unordered_map<std::string, SessionInfo> cache_;
};

int main() {
    SessionCache cache;

    // 调低最大负载因子，减少碰撞
    // cache.max_load_factor(0.5);  // 示例中先不调

    auto now = std::chrono::system_clock::now();

    cache.upsert("tok_A1B2", {"大翔", "tok_A1B2", now, 3600});
    cache.upsert("tok_C3D4", {"白歌", "tok_C3D4", now, 7200});
    cache.upsert("tok_E5F6", {"小崔", "tok_E5F6", now, 1800});
    cache.upsert("tok_G7H8", {"黄俪", "tok_G7H8", now, 3600});
    cache.upsert("tok_I9J0", {"李眉", "tok_I9J0", now, 7200});

    cache.stats();

    // 查找
    auto* session = cache.get("tok_C3D4");
    if (session)
        std::cout << "找到会话: " << session->userId
                  << " (TTL: " << session->ttlSeconds << "s)\n";

    // 预留桶数避免 rehash
    cache.stats();
}

预期输出：

桶数: 13, 元素数: 5, 负载因子: 0.384615, 最大负载因子: 1
找到会话: 白歌 (TTL: 7200s)
桶数: 13, 元素数: 5, 负载因子: 0.384615, 最大负载因子: 1

逐段分析：

  • find 先计算 hash(token) % bucket_count 定位桶，再在链表中比较 → 平均 O(1)
  • load_factor < max_load_factor 时不触发 rehash
  • erase 在遍历中安全删除（返回下一个有效迭代器）

示例二：自定义哈希——IPv4 地址

场景说明：李眉需要为 IP 地址设计高效的哈希函数，用于 unordered_set 黑名单。

#include <iostream>
#include <unordered_set>
#include <string>
#include <cstdint>

struct IPv4 {
    uint8_t a, b, c, d;

    bool operator==(const IPv4& other) const {
        return a == other.a && b == other.b &&
               c == other.c && d == other.d;
    }
};

// 自定义哈希：将 4 字节合并为 1 个 uint32_t
struct IPv4Hash {
    size_t operator()(const IPv4& ip) const {
        return (static_cast<size_t>(ip.a) << 24) |
               (static_cast<size_t>(ip.b) << 16) |
               (static_cast<size_t>(ip.c) << 8)  |
               (static_cast<size_t>(ip.d));
    }
};

std::string to_string(const IPv4& ip) {
    return std::to_string(ip.a) + "." + std::to_string(ip.b) + "." +
           std::to_string(ip.c) + "." + std::to_string(ip.d);
}

int main() {
    // unordered_set 指定自定义哈希和相等比较
    std::unordered_set<IPv4, IPv4Hash> blacklist;

    blacklist.insert({192, 168, 1, 100});
    blacklist.insert({10, 0, 0, 1});
    blacklist.insert({172, 16, 0, 55});
    blacklist.insert({192, 168, 1, 200});

    // 测试查找
    IPv4 test1 = {192, 168, 1, 100};
    IPv4 test2 = {192, 168, 1, 101};

    std::cout << std::boolalpha;
    std::cout << to_string(test1) << " 在黑名单: "
              << blacklist.count(test1) << "\n";
    std::cout << to_string(test2) << " 在黑名单: "
              << blacklist.count(test2) << "\n";

    std::cout << "桶数: " << blacklist.bucket_count()
              << ", 元素数: " << blacklist.size() << "\n";

    // 查看每个桶
    for (size_t i = 0; i < blacklist.bucket_count(); ++i) {
        std::cout << "bucket[" << i << "]: " << blacklist.bucket_size(i)
                  << " 个元素\n";
    }
}

预期输出：

192.168.1.100 在黑名单: true
192.168.1.101 在黑名单: false
桶数: 13, 元素数: 4
bucket[0]: 0 个元素
bucket[1]: 1 个元素
...

逐段分析：

  • IPv4Hash 将 4 字节 IP 地址完美哈希为 32 位整数，零碰撞（所有可能的 IPv4）
  • std::unordered_set<IPv4, IPv4Hash> 中 IPv4Hash 是第三模板参数
  • count 等价于 find != end，返回 0 或 1（对 set 而言）
  • 完美哈希 + 低负载因子 → 查找接近真正的 O(1)

易错场景与面试考点

易错场景

1. 自定义键类型需要同时提供 hash 和 ==

struct Key { int id; };
struct KeyHash { size_t operator()(const Key& k) const { return k.id; } };
// 如果没定义 operator==，两个不同对象但 id 相同会被当作不同 key

2. rehash 导致迭代器失效

auto it = umap.find(key);
umap.insert(new_pair);  // 可能触发 rehash → it 失效

3. 元素顺序不稳定

// 同一组数据在不同运行中遍历顺序可能不同
// 如果需要有序，应使用 map

面试考点

考点要点
冲突解决开链法（separate chaining），链表挂在桶上
负载因子size / bucket_count，超过 max 触发 rehash
rehash扩容桶数组，重新哈希所有元素
自定义哈希特化 std::hash<T> 或提供自定义函数对象
最坏情况全碰撞 → O(n)，需良好的哈希函数
reserve预分配桶数，避免多次 rehash
性能权衡时间 vs 空间：低负载因子减少碰撞但浪费内存