当前位置：首页 > news >正文

【数据结构】hash表(unordered_map)

news 2026/7/4 22:32:46

【数据结构】树
【数据结构】stl容器

std::unordered_map 是 C++ STL 中的无序关联容器，它基于哈希表实现，提供平均 O(1) 的查找、插入和删除操作。下面我结合 STL 的典型实现（以 GCC libstdc++ 和标准规范为基础，参考 SGI STL 风格的源码分析）来详细解答你的问题。讲解会从底层结构入手，然后逐步说明数组（桶数组）的大小决定、插入/删除时的变化逻辑。我会引用简化后的源码片段（基于标准库的伪代码表示，实际源码在 <bits/unordered_map.h> 和 <bits/hashtable.h> 中更复杂，但核心原理一致），并组织逻辑为：结构概述 → 数组大小决定 → 插入变化 → 删除变化。讲解使用中文，确保逻辑清晰。

1. 底层结构：基于数组 + 链表的开链哈希表

是的，你的描述基本正确：std::unordered_map 底层是一个桶数组（bucket array），每个桶对应一个链表（用于处理哈希碰撞）。具体过程如下：

哈希计算：对键（key）计算哈希值（使用 std::hash 或自定义哈希函数），然后取余得到桶索引：hash(key) % bucket_count，其中bucket_count是数组大小。
碰撞处理：如果多个键的哈希值取余后落到同一个桶（下标），则在该桶的链表中存储这些键值对（pair<key, mapped_type>）。查找时，先定位桶，然后在链表中逐个用键的相等比较函数（默认 std::equal_to 或自定义）匹配键。
为什么用链表：链表允许动态添加/删除碰撞元素，保持平均链长短（通过负载因子控制）。

在 STL 源码中，unordered_map 继承自 _Hashtable 模板类，桶数组通常是std::vector<_Hash_node_base*>或类似结构，每个节点 (_Hash_node) 包含键值对和 next 指针，形成单向链表（C++11 后优化为前向链表以节省内存）。

简化源码示例（参考 GCC 实现）：

// 简化后的 _Hashtable 结构（实际更复杂）template<typename_Key,typename_Tp,...>class_Hashtable{protected:size_t _M_bucket_count;// 桶数组大小_Node**_M_buckets;// 桶数组：指针数组，指向每个桶的链表头size_t _M_element_count;// 当前元素数float_M_max_load_factor=1.0f;// 最大负载因子，默认1.0size_t_M_get_bucket_index(constkey_type&__k)const{return__hash(__k)%_M_bucket_count;// hash 值取余得到下标}// 节点结构：包含键值对和 next 指针struct_Node{_Node*_M_next;// 链表指针std::pair<const_Key,_Tp>_M_value;// 键值对（键 const，不可改）};};

解释：_M_buckets是核心数组（动态分配），初始可能为 nullptr。查找/插入时，先计算索引index = hash(key) % _M_bucket_count，然后遍历_M_buckets[index]的链表，用 equal 比较键。如果链长过长，会影响性能，因此有 rehash 机制。

这种设计确保了无序（遍历顺序依赖哈希，不保证排序），但平均高效。

2. 桶数组的大小是什么决定的？

桶数组的大小（bucket_count）由以下因素决定：

初始大小：标准不指定，取决于实现。通常为 0（空表，延迟分配）或一个小素数（如 2、11），以避免早期碰撞。GCC 中初始为 0，在第一次插入时自动 rehash 到一个小值（如 2）。
动态调整：大小不是固定，而是根据元素数和负载因子动态变化。负载因子（load_factor）定义为size() / bucket_count()，标准要求实现保持在 max_load_factor（默认 1.0）以下。
影响因素：
- max_load_factor：用户可设置（e.g., m.max_load_factor(0.75f)），默认 1.0，表示平均每个桶不超过 1 个元素。
- rehash 策略：实现通常选择素数大小（prime number），以减少哈希碰撞。增长时大约翻倍（e.g., 从 11 到 23，到 47 等）。
- reserve(n)：用户可调用 reserve(n) 预分配空间，使桶足够容纳 n 个元素而不 rehash（类似于 vector 的 reserve）。

源码中，bucket_count 通过_M_bucket_count维护，用户可查询bucket_count()。初始决定逻辑在构造函数中：

// 简化构造函数_Hashtable():_M_bucket_count(0),_M_buckets(nullptr),_M_element_count(0){}// 第一次插入时调用 _M_rehash(初始小值，如 2)

解释：大小不是用户直接决定，而是实现根据负载自动管理，以保持性能。用户可通过 rehash(n) 强制设置至少 n 个桶。

3. 插入节点时，数组会变化吗？怎么变化？

是的，插入（insert 或 emplace）可能导致数组变化（rehash），但不是每次都变。具体逻辑：

插入过程：
1. 计算 hash(key) % bucket_count 得到桶索引。
2. 在该桶的链表中搜索是否已有相同键（用 equal 比较）。
3. 如果键存在，更新值（或根据策略处理）；如果不存在，添加新节点到链表（通常添加到头部或尾部，O(1)）。
4. 元素数递增（_M_element_count++）。
5. 检查负载：如果load_factor() > max_load_factor()，触发 rehash。
rehash 变化：
- 何时变化：仅当插入后负载超过阈值时（默认 >1.0）。这确保链长不超过常数，保持 O(1) 平均时间。
- 怎么变化：
  - 计算新大小：通常是当前 bucket_count 的约 2 倍，并选择下一个素数（e.g., 11 → 23）。
  - 分配新桶数组（new _Node**[new_size]）。
  - 遍历所有旧元素，重新计算 hash % new_size，插入到新链表（O(n) 时间，n 为元素数）。
  - 释放旧数组，更新 _M_buckets 和 _M_bucket_count。
  - 摊销后，插入仍是 O(1)。

简化源码示例（insert 和 rehash）：

// 简化 insertstd::pair<iterator,bool>insert(constvalue_type&__v){size_t __code=_M_hash_code(__v.first);// 计算 hashsize_t __bkt=__code%_M_bucket_count;// 取余得索引_Node*__node=_M_find_node(__bkt,__v.first,__code);// 在链表中用 equal 找键if(__node)return{iterator(__node),false};// 存在，返回 false// 添加新节点_Node*__new_node=_M_allocate_node(__v);__new_node->_M_next=_M_buckets[__bkt];// 插入链表头_M_buckets[__bkt]=__new_node;++_M_element_count;// 检查 rehashif(_M_rehash_required())_M_rehash(_M_next_bkt(_M_bucket_count*2));// 如果需要，rehashreturn{iterator(__new_node),true};}// 简化 rehashvoid_M_rehash(size_t __n){size_t __new_size=_M_next_bkt(__n);// 找下一个素数大小 (>=n)_Node**__new_buckets=new_Node*[__new_size]();// 新数组，初始化 nullptr// 迁移旧元素for(size_t __i=0;__i<_M_bucket_count;++__i){_Node*__p=_M_buckets[__i];while(__p){_Node*__next=__p->_M_next;size_t __new_bkt=_M_hash_code(__p->_M_v().first)%__new_size;// 重新取余__p->_M_next=__new_buckets[__new_bkt];// 插入新链表__new_buckets[__new_bkt]=__p;__p=__next;}}delete[]_M_buckets;// 释放旧数组_M_buckets=__new_buckets;_M_bucket_count=__new_size;}

解释：rehash 是 O(n) 操作，但 infrequent（负载控制下）。如果频繁插入，可用 reserve(n) 预先扩大，避免多次 rehash。注意：rehash 后，所有迭代器失效（因为桶重分配）。

4. 删除节点时，数组会变化吗？怎么变化？

通常不会变化。删除（erase）不会自动触发 rehash 或缩小数组，除非用户手动调用 rehash(0) 或类似。

删除过程：
1. 计算 hash(key) % bucket_count 得到索引。
2. 在链表中用 equal 找键，找到后从链表移除节点（O(链长)，平均 O(1)）。
3. 元素数递减（_M_element_count–）。
4. 不检查负载：标准不要求在删除时缩小桶数组（min_load_factor 不强制，默认无）。一些实现（如 GCC）只在插入时扩大，不自动缩小，以避免频繁调整。
何时变化：
- 如果用户调用 rehash(n)，会强制调整到至少 n 个桶（可能缩小如果 n 小）。
- 删除后负载很低（e.g., <0.25），有些实现可能有可选缩小，但标准库默认不（为了性能，避免震荡）。
- 怎么变化：如果触发（手动），类似插入的 rehash：计算新大小，迁移元素。但实际中，删除不改变数组大小，桶可能变空但保留。

简化源码示例（erase）：

// 简化 erasesize_typeerase(constkey_type&__k){size_t __code=_M_hash_code(__k);size_t __bkt=__code%_M_bucket_count;_Node*__prev=nullptr;_Node*__p=_M_buckets[__bkt];while(__p){// 遍历链表if(_M_equal(__k,__p->_M_v().first)){// 用 equal 匹配if(__prev)__prev->_M_next=__p->_M_next;else_M_buckets[__bkt]=__p->_M_next;_M_deallocate_node(__p);// 释放节点--_M_element_count;return1;// 删除成功}__prev=__p;__p=__p->_M_next;}return0;// 未找到// 注意：无 rehash 调用}