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

《C++进阶之STL》【哈希表】

news 2026/5/11 21:06:08

《C++进阶之STL》——哈希表（unordered系列容器）全解析

C++11 引入了以哈希表为底层实现的无序关联容器，主要包括以下四个：

容器名称	底层实现	元素是否允许重复	按什么排序	主要用途	典型场景
`unordered_set<T>`	哈希表	不允许重复	无序	快速去重 + 查找	元素存在性判断、去重
`unordered_multiset<T>`	哈希表	允许重复	无序	允许重复元素的集合	统计词频、多重计数
`unordered_map<Key, T>`	哈希表	key 不重复	无序	键值对快速查找	缓存、配置表、计数、映射关系
`unordered_multimap<Key, T>`	哈希表	key 可重复	无序	允许 key 重复的键值对	一对多映射、多值映射

这四个容器统称为unordered 系列，与map/set的最大区别在于：

底层结构：哈希表（桶数组 + 链表/红黑树） vs 红黑树
时间复杂度：平均 O(1)，最坏 O(n)
是否有序：完全无序

一、哈希表在 STL 中的核心实现原理（非常重要）

现代 C++（GCC/libstdc++ 和 LLVM/libc++）的unordered_*容器基本都采用以下结构：

桶数组（bucket array） + 每个桶挂一条链表（或红黑树）

桶数组大小是 2 的幂（常见初始 8、16、32…）
插入元素时：计算 hash 值 → 取模桶数量 → 放入对应桶的链表
负载因子（load factor）达到一定值（通常 1.0）时 → 扩容（rehash）
GCC 11+ 在桶内元素较多时会转为红黑树（避免哈希碰撞退化成 O(n)）

最关键的三个概念：

哈希函数（hash function）
相等比较（key_equal）
负载因子与扩容策略

二、哈希函数与相等比较（最容易踩坑的地方）

// 默认使用std::hash<Key>// 计算哈希值std::equal_to<Key>// 判断是否相等

自定义类型必须同时提供：

structPerson{std::string name;intage;booloperator==(constPerson&other)const{returnname==other.name&&age==other.age;}};// 自定义哈希函数（必须满足：相等的对象哈希值必须相等）structPersonHash{size_toperator()(constPerson&p)const{size_t h1=std::hash<std::string>{}(p.name);size_t h2=std::hash<int>{}(p.age);returnh1^(h2<<1);// 简单组合方式// 更推荐：使用 boost::hash_combine 或其他成熟实现}};

正确用法（三种方式任选）：

// 方式1：模板参数指定std::unordered_set<Person,PersonHash>s;// 方式2：构造时传入std::unordered_set<Person,PersonHash>s(0,PersonHash(),std::equal_to<Person>{});// 方式3：C++20 异构查找（推荐，性能更好）std::unordered_set<Person,PersonHash,std::equal_to<>>s;

三、常用 API 速查表（高频操作）

操作类型	函数	时间复杂度（平均）	备注 / 注意事项
插入	`insert(value)`	O(1)	返回 pair<iterator, bool>
原地构造插入	`emplace(args...)`	O(1)	效率更高，避免拷贝
查找	`find(key)`	O(1)	返回迭代器，找不到返回 end()
计数	`count(key)`	O(1)	unordered_set 永远是 0 或 1
访问/修改	`operator[]`（仅 map）	O(1)	键不存在时会插入默认构造对象！
访问（安全）	`at(key)`	O(1)	键不存在抛异常
删除	`erase(key)`/`erase(iterator)`	O(1)	erase(iterator) 返回下一个迭代器
清空	`clear()`	O(n)	capacity 可能保留
桶相关	`bucket_count()`	O(1)	当前桶数量
负载因子	`load_factor()`/`max_load_factor()`	O(1)	默认 max_load_factor ≈ 1.0
手动扩容	`reserve(n)`	O(n)	预分配能容纳 n 个元素的空间
重新哈希	`rehash(n)`	O(n)	强制设置桶数量为 n（通常是 2 的幂）

四、高频使用场景代码示例

1. 快速去重 + 存在性判断（unordered_set）

std::unordered_set<std::string>seen;for(constauto&word:words){if(seen.insert(word).second){// 插入成功，代表之前没有}}

2. 词频统计（unordered_map）

std::unordered_map<std::string,int>freq;for(constauto&word:text){freq[word]++;}

3. 高效缓存（LRU 常配合使用）

classLRUCache{private:std::unordered_map<int,std::list<std::pair<int,int>>::iterator>map;std::list<std::pair<int,int>>list;size_t capacity;public:LRUCache(intcap):capacity(cap){}intget(intkey){autoit=map.find(key);if(it==map.end())return-1;// 移动到头部list.splice(list.begin(),list,it->second);returnit->second->second;}voidput(intkey,intvalue){autoit=map.find(key);if(it!=map.end()){list.splice(list.begin(),list,it->second);it->second->second=value;return;}if(map.size()>=capacity){intold=list.back().first;list.pop_back();map.erase(old);}list.emplace_front(key,value);map[key]=list.begin();}};

4. 自定义哈希 + 自定义相等（C++20 异构查找写法）

structCaseInsensitiveHash{size_toperator()(std::string_view s)const{size_t h=0;for(charc:s){h=h*31+std::toupper(c);}returnh;}};std::unordered_set<std::string,CaseInsensitiveHash,std::equal_to<>>s;

五、性能陷阱与优化技巧（生产必知）

哈希碰撞攻击（Hash DoS）
- 恶意构造大量哈希值相同的 key → O(n) 退化
- 解决：使用安全的哈希函数（如 SipHash），或 C++20 之后的随机种子
负载因子过高
- 默认 max_load_factor = 1.0
- 建议提前reserve预估元素数量
频繁 rehash
- 插入时触发多次扩容 → 性能灾难
- 解决方案：reserve(n)或max_load_factor(0.25)（牺牲空间换时间）
自定义类型的哈希质量
- 低质量哈希 → 大量元素落入同一个桶
- 推荐使用：boost::hash_combine或std::hash的组合
内存占用
- 每个元素 ≈ 8~16 字节（指针 + 节点开销）
- 桶数组也占用内存（空桶也占空间）

六、总结对比：unordered vs ordered

需求	推荐容器	平均时间复杂度	是否有序	内存占用	适用场景
需要快速查找/去重	unordered_set	O(1)	否	较高	存在性、去重、计数
需要有序遍历	set	O(log n)	是	较低	需要排序、范围查询
key-value 快速查找	unordered_map	O(1)	否	较高	缓存、配置、映射
key-value 有序	map	O(log n)	是	较低	需要按 key 排序输出