【C++】 unordered_map 与unordered_set

一、 容器简介

在 C++98 中，STL 提供了底层为红黑树结构的关联式容器，查询效率为O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)。为了在海量数据下实现O ( 1 ) O(1)O(1)的常数级查找效率，C++11 引入了 4 个 unordered 系列关联式容器。

1. unordered_map

• 它是存储<key, value>键值对的关联式容器，允许通过 keys 快速索引到对应的 value。
• 在内部，容器没有对键值对按照任何特定的顺序排序。
• 容器将相同哈希值的键值对放在相同的桶中，以此实现极致的查找速度。
• 由于底层单链表结构限制，它的迭代器至少是前向迭代器（不支持反向遍历）。

2. unordered_set

• 它是仅存储唯一关键码（Key）的关联式容器，是处理海量数据去重与极速存在性校验的绝佳利器。
• 与unordered_map机制相同，其内部元素同样无序，依靠哈希函数将关键码映射并存储到对应的哈希桶中。
• 为了防止底层哈希映射位置被破坏，容器中的元素不能被修改（其迭代器本质上是const迭代器）。
• 同样仅支持单向迭代，其插入、查找、删除的平均时间复杂度均能达到常数级别O ( 1 ) O(1)O(1)。

二、 核心接口与使用示例

1. 容量与基础查询

• empty()：检测容器是否为空。
• size()：获取容器的有效元素个数。

unordered_map<string,int>dict;dict.insert({"apple",1});boolisEmpty=dict.empty();// 返回 falsesize_t count=dict.size();// 返回 1

2. 元素查找

• find(const K& key)：返回 key 在哈希桶中的位置迭代器，若未找到则返回end()。
• count(const K& key)：返回关键码为 key 的键值对个数。因容器中 key 不可重复，故返回值最大为 1，常用于快速判断元素是否存在。

unordered_set<int>us={1,2,3};// 使用 find 查找autoit=us.find(2);if(it!=us.end()){cout<<"找到了: "<<*it<<endl;}// 使用 count 判断存在性if(us.count(4)==0){cout<<"元素 4 不存在"<<endl;}

3. operator[] 的特殊机制

unordered_map提供了operator[]，其实际调用了底层的插入操作。用参数 key 与默认值构造键值对进行插入：

• 若 key 不在容器中，插入成功并返回默认值的引用。
• 若 key 已存在，插入失败，但会返回原来 key 对应的 value 引用。

unordered_map<string,string>dict;dict["insert"]="插入";// key不存在，插入 {"insert", ""}，随后将其 value 修改为 "插入"dict["insert"]="覆盖";// key已存在，直接返回 value 引用并修改为 "覆盖"

三、 面试题实战

实战 1：

重复 N 次的元素

给定一个数组，找出一个出现了特定次数的元素。利用unordered_map统计频次。

classSolution{public:intrepeatedNTimes(vector<int>&A){size_t N=A.size()/2;unordered_map<int,int>m;for(autoe:A){m[e]++;// 元素不存在则初始化为0后加1，存在则直接加1}for(auto&e:m){if(e.second==N)returne.first;}return-1;}};

实战 2：

两个数组的交集

求两个数组的交集并去重。利用unordered_set实现去重与快速匹配。

classSolution{public:vector<int>intersection(vector<int>&nums1,vector<int>&nums2){unordered_set<int>s1;for(autoe:nums1)s1.insert(e);unordered_set<int>s2;for(autoe:nums2)s2.insert(e);vector<int>vRet;for(autoe:s1){if(s2.find(e)!=s2.end()){vRet.push_back(e);}}returnvRet;}};

四、 哈希表底层原理

具体讲解哈希表

哈希表通过哈希函数将元素的关键码映射为存储位置。常见的哈希函数有除留余数法：Hash(key) = key % capacity。

当不同关键字计算出相同的哈希地址时，即发生哈希冲突。解决冲突的方法有两种：

1. 闭散列（开放定址法）：寻找下一个空位置存放冲突元素（如线性探测）。其载荷因子必须严格限制在 0.7 - 0.8 以下，容易产生数据堆积，空间利用率低。
2. 开散列（链地址法 / 哈希桶）：将哈希地址相同的元素归于同一个桶，通过单链表链接。STL 主要采用开散列，其载荷因子可以达到 1.0，空间利用率和查找效率更优。

五、 底层完整实现

以下为基于开散列（哈希桶）完整封装unordered_map和unordered_set的核心代码。

1. 基础组件与哈希函数

#pragmaonce#include<iostream>#include<vector>#include<string>usingnamespacestd;template<classK>structHashFunc{size_toperator()(constK&key){return(size_t)key;}};// 针对 string 的哈希特化 (BKDR Hash)template<>structHashFunc<string>{size_toperator()(conststring&key){size_t hash=0;for(autoe:key){hash*=31;hash+=e;}returnhash;}};

2. 哈希桶与迭代器实现

namespacehash_bucket{template<classT>structHashNode{T _data;HashNode<T>*_next;HashNode(constT&data):_data(data),_next(nullptr){}};template<classK,classT,classKeyOfT,classHash>classHashTable;// 迭代器实现template<classK,classT,classPtr,classRef,classKeyOfT,classHash>structHTIterator{typedefHashNode<T>Node;typedefHTIterator<K,T,Ptr,Ref,KeyOfT,Hash>Self;Node*_node;constHashTable<K,T,KeyOfT,Hash>*_pht;HTIterator(Node*node,constHashTable<K,T,KeyOfT,Hash>*pht):_node(node),_pht(pht){}Refoperator*(){return_node->_data;}Ptroperator->(){return&_node->_data;}booloperator!=(constSelf&s){return_node!=s._node;}Self&operator++(){if(_node->_next){_node=_node->_next;}else{KeyOfT kot;Hash hs;size_t hashi=hs(kot(_node->_data))%_pht->_tables.size();++hashi;while(hashi<_pht->_tables.size()){if(_pht->_tables[hashi])break;++hashi;}if(hashi==_pht->_tables.size())_node=nullptr;else_node=_pht->_tables[hashi];}return*this;}};// 哈希表主体template<classK,classT,classKeyOfT,classHash>classHashTable{template<classK,classT,classPtr,classRef,classKeyOfT,classHash>friendstructHTIterator;typedefHashNode<T>Node;public:typedefHTIterator<K,T,T*,T&,KeyOfT,Hash>Iterator;typedefHTIterator<K,T,constT*,constT&,KeyOfT,Hash>ConstIterator;HashTable(){_tables.resize(10,nullptr);}~HashTable(){for(size_t i=0;i<_tables.size();i++){Node*cur=_tables[i];while(cur){Node*next=cur->_next;deletecur;cur=next;}_tables[i]=nullptr;}}IteratorBegin(){if(_n==0)returnEnd();for(size_t i=0;i<_tables.size();i++){if(_tables[i])returnIterator(_tables[i],this);}returnEnd();}IteratorEnd(){returnIterator(nullptr,this);}pair<Iterator,bool>Insert(constT&data){KeyOfT kot;Iterator it=Find(kot(data));if(it!=End())returnmake_pair(it,false);Hash hs;if(_n==_tables.size()){vector<Node*>newtables(_tables.size()*2,nullptr);for(size_t i=0;i<_tables.size();i++){Node*cur=_tables[i];while(cur){Node*next=cur->_next;size_t hashi=hs(kot(cur->_data))%newtables.size();cur->_next=newtables[hashi];newtables[hashi]=cur;cur=next;}_tables[i]=nullptr;}_tables.swap(newtables);}size_t hashi=hs(kot(data))%_tables.size();Node*newnode=newNode(data);newnode->_next=_tables[hashi];_tables[hashi]=newnode;++_n;returnmake_pair(Iterator(newnode,this),true);}IteratorFind(constK&key){KeyOfT kot;Hash hs;size_t hashi=hs(key)%_tables.size();Node*cur=_tables[hashi];while(cur){if(kot(cur->_data)==key)returnIterator(cur,this);cur=cur->_next;}returnEnd();}boolErase(constK&key){KeyOfT kot;Hash hs;size_t hashi=hs(key)%_tables.size();Node*prev=nullptr;Node*cur=_tables[hashi];while(cur){if(kot(cur->_data)==key){if(prev==nullptr)_tables[hashi]=cur->_next;elseprev->_next=cur->_next;deletecur;--_n;returntrue;}prev=cur;cur=cur->_next;}returnfalse;}private:vector<Node*>_tables;size_t _n=0;};}

3. 封装 unordered_set

namespacebit{template<classK,classHash=HashFunc<K>>classunordered_set{structSetKeyOfT{constK&operator()(constK&key){returnkey;}};public:typedeftypenamehash_bucket::HashTable<K,constK,SetKeyOfT,Hash>::Iterator iterator;typedeftypenamehash_bucket::HashTable<K,constK,SetKeyOfT,Hash>::ConstIterator const_iterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pair<iterator,bool>insert(constK&key){return_ht.Insert(key);}iteratorFind(constK&key){return_ht.Find(key);}boolErase(constK&key){return_ht.Erase(key);}private:hash_bucket::HashTable<K,constK,SetKeyOfT,Hash>_ht;};}

4. 封装 unordered_map

namespacebit{template<classK,classV,classHash=HashFunc<K>>classunordered_map{structMapKeyOfT{constK&operator()(constpair<K,V>&kv){returnkv.first;}};public:typedeftypenamehash_bucket::HashTable<K,pair<constK,V>,MapKeyOfT,Hash>::Iterator iterator;typedeftypenamehash_bucket::HashTable<K,pair<constK,V>,MapKeyOfT,Hash>::ConstIterator const_iterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pair<iterator,bool>insert(constpair<K,V>&kv){return_ht.Insert(kv);}V&operator[](constK&key){pair<iterator,bool>ret=_ht.Insert(make_pair(key,V()));returnret.first->second;}iteratorFind(constK&key){return_ht.Find(key);}boolErase(constK&key){return_ht.Erase(key);}private:hash_bucket::HashTable<K,pair<constK,V>,MapKeyOfT,Hash>_ht;};}

六、 扩展应用

在海量数据处理场景下，常规哈希表会面临内存不足的问题。此时可以使用哈希思想的延伸结构：

1. 位图 (BitMap)：使用二进制比特位代表数据是否存在，适用于海量整型数据的快速查找与去重。
2. 布隆过滤器 (Bloom Filter)：将哈希函数与位图结合，通过多个哈希函数将一个数据映射到位图中。适用于容忍一定误判率的海量字符串查重过滤场景，空间优势极大。

七、 总结

• 若业务场景需要数据保持特定顺序输出，应选择基于红黑树的map/set。
• 若核心需求为极限速度的增删查改，优先选用unordered_map/unordered_set。
• STL 的底层通过仿函数提取器（KeyOfT）实现了HashTable泛型代码的复用，理解这一点有助于掌握 C++ 的泛型编程逻辑。
• 在使用operator[]时需明确其底层包含插入逻辑，仅查询判断时应优先使用find()或count()。