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

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

插入逻辑简述：

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

标签： node c++ 质数 red