c++如何实现一个哈希表_c++数据结构unordered_map原理【源码】

哈希表在 C++ 中最常用的实现就是 std::unordered_map，它底层基于开放寻址或链地址法（主流实现是**分离链表法**），提供平均 O(1) 的插入、查找和删除。它不是标准强制规定实现方式，但所有主流 STL（如 libstdc++、libc++、MSVC STL）都采用**哈希 + 拉链（bucket + linked list）**结构，配合动态扩容和负载因子控制。

核心结构：桶数组 + 单向链表节点

每个桶（bucket）是一个指针，指向一条以哈希值相同元素构成的单向链表。关键成员通常包括：

• bucket 数组（vector）：大小为质数（避免哈希冲突聚集），初始一般为 11 或 17
• Node 结构：含 key、value、next 指针（可能还有 hash 值缓存）
• 元素总数（size）和桶数量（bucket_count）：用于计算负载因子 load_factor = size / bucket_count
• 最大负载因子（max_load_factor）：默认 1.0，超限触发 rehash

哈希与映射：如何定位 bucket

给定 key，流程如下：

• 调用 std::hash()(key) 得到一个 size_t 类型哈希值（对自定义类型需特化或传 Hash 函数对象）
• 用 hash_value % bucket_count 算出下标（libstdc++ 实际用更优的 hash_value & (bucket_count - 1)，但前提是 bucket_count 是 2 的幂；而实际它用的是质数，所以仍是取模）
• 遍历该 bucket 对应链表，用 operator== 比较 key（注意：哈希相等 ≠ key 相等，必须二次判断）

插入与扩容：rehash 是性能关键

插入逻辑简述：

立即学习“C++免费学习笔记（深入）”；

InsCode

InsCode 是CSDN旗下的一个无需安装的编程、协作和分享社区

下载

• 计算 bucket 下标
• 遍历链表检查 key 是否已存在（存在则更新 value）
• 不存在则 new Node 插入链表头（或尾，取决于实现），size++
• 若 size > max_load_factor * bucket_count，触发 rehash：分配新桶数组（更大质数），把所有旧节点重新 hash 插入新表

libstdc++ 中 rehash 会将 bucket_count 设为「不小于指定值的最小质数」，质数表是静态预置的（如 11, 23, 47, 97...）。

简易手写版（简化链地址法）示意

template , typename Eq = std::equal_to>
class simple_unordered_map {
    struct Node { K key; V value; Node* next; Node(const K& k, const V& v) : key(k), value(v), next(nullptr) {} };
    std::vector buckets;
    size_t _size = 0;
    float max_load = 1.0f;
    Hash hasher;
    Eq equal;
size_t hash_index(const K& k) const { return hasher(k) % buckets.size(); }

void rehash(size_t new_bucket_count) {
    std::vector new_buckets(new_bucket_count, nullptr);
    for (Node* node : buckets) {
        while (node) {
            Node* next = node->next;
            size_t idx = hasher(node->key) % new_bucket_count;
            node->next = new_buckets[idx];
            new_buckets[idx] = node;
            node = next;
        }
    }
    buckets.swap(new_buckets);
}

public:
simple_unordered_map() { buckets.resize(11, nullptr); }
V& operator[](const K& k) {
    size_t idx = hash_index(k);
    Node*& head = buckets[idx];
    for (Node* p = head; p; p = p->next) {
        if (equal(p->key, k)) return p->value;
    }
    // 未找到，插入新节点（头插）
    Node* newNode = new Node(k, V{});
    newNode->next = head;
    buckets[idx] = newNode;
    ++_size;
    if (_size > max_load * buckets.size()) rehash(/*下一个质数*/);
    return buckets[idx]->value;
}

~simple_unordered_map() {
    for (Node* head : buckets) {
        while (head) {
            Node* next = head->next;
            delete head;
            head = next;
        }
    }
}
};
基本上就这些。真正工业级实现（如 GCC 的 libstdc++/include/bits/hashtable.h）还涉及内存池、移动语义、迭代器失效规则、const_iterator 支持、emplace 优化等，但骨架一致：哈希分桶 + 链表容错 + 动态扩容。理解这个模型，读源码就不容易迷失在模板嵌套里。