c++kquote>std::unordered_map底层采用哈希+拉链法，以质数大小的桶数组和单向链表节点构成，通过哈希值取模定位bucket，负载因子超限触发rehash。
哈希表在 C++ 中最常用的实现就是 std::unordered_map，它底层基于开放寻址或链地址法（主流实现是**分离链表法**），提供平均 O(1) 的插入、查找和删除。它不是标准强制规定实现方式，但所有主流 STL（如 libstdc++、libc++、MSVC STL）都采用**哈希 + 拉链（bucket + linked list）**结构，配合动态扩容和负载因子控制。
核心结构：桶数组 + 单向链表节点
每个桶（bucket）是一个指针，指向一条以哈希值相同元素构成的单向链表。关键成员通常包括：
bucket 数组（vector）：大小为质数（避免哈希冲突聚集），初始一般为 11 或 17Node 结构：含 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++免费学习笔记（深入）”；
计算 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, 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 优化等，但骨架一致：哈希分桶 + 链表容错 + 动态扩容。理解这个模型，读源码就不容易迷失在模板嵌套里。
以上就是c++++如何实现一个哈希表_c++数据结构unordered_map原理【源码】的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488549.html
微信扫一扫 
支付宝扫一扫 
