std::unordered_map底层采用哈希+拉链法，以质数大小的桶数组和单向链表节点构成，通过哈希值取模定位bucket，负载因子超限触发rehash。
哈希表在 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>()(key)</key>得到一个 size_t 类型哈希值（对自定义类型需特化或传 Hash 函数对象） - 用
hash_value % bucket_count算出下标（libstdc++ 实际用更优的hash_value & (bucket_count - 1)，但前提是 bucket_count 是 2 的幂；而实际它用的是质数，所以仍是取模） - 遍历该 bucket 对应链表，用
operator==比较 key（注意：哈希相等 ≠ key 相等，必须二次判断）
插入与扩容：rehash 是性能关键
插入逻辑简述：
立即学习“C++免费学习笔记（深入）”；
- 计算 bucket 下标
- 遍历链表检查 key 是否已存在（存在则更新 value）
- 不存在则 new Node 插入链表头（或尾，取决于实现），size++
- 若
size > max_load_factor * bucket_count，触发 rehash：分配新桶数组（更大质数），把所有旧节点重新 hash 插入新表
libstdc++ 中 rehash 会将 bucket_count 设为「不小于指定值的最小质数」，质数表是静态预置的（如 11, 23, 47, 97...）。
简易手写版（简化链地址法）示意
（仅演示核心逻辑，无异常/allocator/迭代器等完整功能）template <typename K, typename V, typename Hash = std::hash<K>, typename Eq = std::equal_to<K>>
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<Node*> buckets;
size_t _size = 0;
float max_load = 1.0f;
Hash hasher;
Eq equal;
<pre class="brush:php;toolbar:false;">size_t hash_index(const K& k) const { return hasher(k) % buckets.size(); }
void rehash(size_t new_bucket_count) {
std::vector<Node*> 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 优化等，但骨架一致：哈希分桶 + 链表容错 + 动态扩容。理解这个模型，读源码就不容易迷失在模板嵌套里。
