目录一、 容器简介二、 核心接口与使用示例1. 容量与基础查询2. 元素查找3. operator[] 的特殊机制三、 面试题实战实战 1实战 2四、 哈希表底层原理五、 底层完整实现1. 基础组件与哈希函数2. 哈希桶与迭代器实现3. 封装 unordered_set4. 封装 unordered_map六、 扩展应用七、 总结一、 容器简介在 C98 中STL 提供了底层为红黑树结构的关联式容器查询效率为O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)。为了在海量数据下实现O ( 1 ) O(1)O(1)的常数级查找效率C11 引入了 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_mapstring,intdict;dict.insert({apple,1});boolisEmptydict.empty();// 返回 falsesize_t countdict.size();// 返回 12. 元素查找find(const K key)返回 key 在哈希桶中的位置迭代器若未找到则返回end()。count(const K key)返回关键码为 key 的键值对个数。因容器中 key 不可重复故返回值最大为 1常用于快速判断元素是否存在。unordered_setintus{1,2,3};// 使用 find 查找autoitus.find(2);if(it!us.end()){cout找到了: *itendl;}// 使用 count 判断存在性if(us.count(4)0){cout元素 4 不存在endl;}3. operator[] 的特殊机制unordered_map提供了operator[]其实际调用了底层的插入操作。用参数 key 与默认值构造键值对进行插入若 key 不在容器中插入成功并返回默认值的引用。若 key 已存在插入失败但会返回原来 key 对应的 value 引用。unordered_mapstring,stringdict;dict[insert]插入;// key不存在插入 {insert, }随后将其 value 修改为 插入dict[insert]覆盖;// key已存在直接返回 value 引用并修改为 覆盖三、 面试题实战实战 1重复 N 次的元素给定一个数组找出一个出现了特定次数的元素。利用unordered_map统计频次。classSolution{public:intrepeatedNTimes(vectorintA){size_t NA.size()/2;unordered_mapint,intm;for(autoe:A){m[e];// 元素不存在则初始化为0后加1存在则直接加1}for(autoe:m){if(e.secondN)returne.first;}return-1;}};实战 2两个数组的交集求两个数组的交集并去重。利用unordered_set实现去重与快速匹配。classSolution{public:vectorintintersection(vectorintnums1,vectorintnums2){unordered_setints1;for(autoe:nums1)s1.insert(e);unordered_setints2;for(autoe:nums2)s2.insert(e);vectorintvRet;for(autoe:s1){if(s2.find(e)!s2.end()){vRet.push_back(e);}}returnvRet;}};四、 哈希表底层原理具体讲解哈希表哈希表通过哈希函数将元素的关键码映射为存储位置。常见的哈希函数有除留余数法Hash(key) key % capacity。当不同关键字计算出相同的哈希地址时即发生哈希冲突。解决冲突的方法有两种闭散列开放定址法寻找下一个空位置存放冲突元素如线性探测。其载荷因子必须严格限制在 0.7 - 0.8 以下容易产生数据堆积空间利用率低。开散列链地址法 / 哈希桶将哈希地址相同的元素归于同一个桶通过单链表链接。STL 主要采用开散列其载荷因子可以达到 1.0空间利用率和查找效率更优。五、 底层完整实现以下为基于开散列哈希桶完整封装unordered_map和unordered_set的核心代码。1. 基础组件与哈希函数#pragmaonce#includeiostream#includevector#includestringusingnamespacestd;templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};// 针对 string 的哈希特化 (BKDR Hash)templatestructHashFuncstring{size_toperator()(conststringkey){size_t hash0;for(autoe:key){hash*31;hashe;}returnhash;}};2. 哈希桶与迭代器实现namespacehash_bucket{templateclassTstructHashNode{T _data;HashNodeT*_next;HashNode(constTdata):_data(data),_next(nullptr){}};templateclassK,classT,classKeyOfT,classHashclassHashTable;// 迭代器实现templateclassK,classT,classPtr,classRef,classKeyOfT,classHashstructHTIterator{typedefHashNodeTNode;typedefHTIteratorK,T,Ptr,Ref,KeyOfT,HashSelf;Node*_node;constHashTableK,T,KeyOfT,Hash*_pht;HTIterator(Node*node,constHashTableK,T,KeyOfT,Hash*pht):_node(node),_pht(pht){}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}booloperator!(constSelfs){return_node!s._node;}Selfoperator(){if(_node-_next){_node_node-_next;}else{KeyOfT kot;Hash hs;size_t hashihs(kot(_node-_data))%_pht-_tables.size();hashi;while(hashi_pht-_tables.size()){if(_pht-_tables[hashi])break;hashi;}if(hashi_pht-_tables.size())_nodenullptr;else_node_pht-_tables[hashi];}return*this;}};// 哈希表主体templateclassK,classT,classKeyOfT,classHashclassHashTable{templateclassK,classT,classPtr,classRef,classKeyOfT,classHashfriendstructHTIterator;typedefHashNodeTNode;public:typedefHTIteratorK,T,T*,T,KeyOfT,HashIterator;typedefHTIteratorK,T,constT*,constT,KeyOfT,HashConstIterator;HashTable(){_tables.resize(10,nullptr);}~HashTable(){for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;deletecur;curnext;}_tables[i]nullptr;}}IteratorBegin(){if(_n0)returnEnd();for(size_t i0;i_tables.size();i){if(_tables[i])returnIterator(_tables[i],this);}returnEnd();}IteratorEnd(){returnIterator(nullptr,this);}pairIterator,boolInsert(constTdata){KeyOfT kot;Iterator itFind(kot(data));if(it!End())returnmake_pair(it,false);Hash hs;if(_n_tables.size()){vectorNode*newtables(_tables.size()*2,nullptr);for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;size_t hashihs(kot(cur-_data))%newtables.size();cur-_nextnewtables[hashi];newtables[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newtables);}size_t hashihs(kot(data))%_tables.size();Node*newnodenewNode(data);newnode-_next_tables[hashi];_tables[hashi]newnode;_n;returnmake_pair(Iterator(newnode,this),true);}IteratorFind(constKkey){KeyOfT kot;Hash hs;size_t hashihs(key)%_tables.size();Node*cur_tables[hashi];while(cur){if(kot(cur-_data)key)returnIterator(cur,this);curcur-_next;}returnEnd();}boolErase(constKkey){KeyOfT kot;Hash hs;size_t hashihs(key)%_tables.size();Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(kot(cur-_data)key){if(prevnullptr)_tables[hashi]cur-_next;elseprev-_nextcur-_next;deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}private:vectorNode*_tables;size_t _n0;};}3. 封装 unordered_setnamespacebit{templateclassK,classHashHashFuncKclassunordered_set{structSetKeyOfT{constKoperator()(constKkey){returnkey;}};public:typedeftypenamehash_bucket::HashTableK,constK,SetKeyOfT,Hash::Iterator iterator;typedeftypenamehash_bucket::HashTableK,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();}pairiterator,boolinsert(constKkey){return_ht.Insert(key);}iteratorFind(constKkey){return_ht.Find(key);}boolErase(constKkey){return_ht.Erase(key);}private:hash_bucket::HashTableK,constK,SetKeyOfT,Hash_ht;};}4. 封装 unordered_mapnamespacebit{templateclassK,classV,classHashHashFuncKclassunordered_map{structMapKeyOfT{constKoperator()(constpairK,Vkv){returnkv.first;}};public:typedeftypenamehash_bucket::HashTableK,pairconstK,V,MapKeyOfT,Hash::Iterator iterator;typedeftypenamehash_bucket::HashTableK,pairconstK,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();}pairiterator,boolinsert(constpairK,Vkv){return_ht.Insert(kv);}Voperator[](constKkey){pairiterator,boolret_ht.Insert(make_pair(key,V()));returnret.first-second;}iteratorFind(constKkey){return_ht.Find(key);}boolErase(constKkey){return_ht.Erase(key);}private:hash_bucket::HashTableK,pairconstK,V,MapKeyOfT,Hash_ht;};}六、 扩展应用在海量数据处理场景下常规哈希表会面临内存不足的问题。此时可以使用哈希思想的延伸结构位图 (BitMap)使用二进制比特位代表数据是否存在适用于海量整型数据的快速查找与去重。布隆过滤器 (Bloom Filter)将哈希函数与位图结合通过多个哈希函数将一个数据映射到位图中。适用于容忍一定误判率的海量字符串查重过滤场景空间优势极大。七、 总结若业务场景需要数据保持特定顺序输出应选择基于红黑树的map/set。若核心需求为极限速度的增删查改优先选用unordered_map/unordered_set。STL 的底层通过仿函数提取器KeyOfT实现了HashTable泛型代码的复用理解这一点有助于掌握 C 的泛型编程逻辑。在使用operator[]时需明确其底层包含插入逻辑仅查询判断时应优先使用find()或count()。