Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》

欢迎点赞，关注！

        这一期我们来讲解并模拟实现unordered_map和unordered_set。有了前面的铺垫，这一篇就要相对简单很多了。

 

1、unordered_set和unordered_map的使用

        在C++标准模板库(STL)中，unordered_set和unordered_map是两种非常重要的关联容器，它们基于哈希表实现，提供了高效的查找、插入和删除操作。本文将详细讲解这两种容器的特性、用法、内部实现原理。

      1.1、unordered_set的使用

        unordered_set是一个存储唯一元素的容器，其中每个元素的值同时也是它的键。

        我们把unordered_set的使用快速过一遍。因为在日常使用中，unordered_set的使用和set的使用很相似。接口都是类似的。

#include <unordered_set>
#include <iostream>int main() {// 创建unordered_setstd::unordered_set<int> numbers = {1, 2, 3, 4, 5};// 插入元素numbers.insert(6);numbers.emplace(7);  // 更高效的插入方式//下两篇会详细讲解emplace接口// 查找元素if (numbers.find(3) != numbers.end()) {std::cout << "3 found in the set\n";}// 删除元素numbers.erase(4);// 遍历元素for (const auto& num : numbers) {std::cout << num << " ";}std::cout << "\n";// 获取大小std::cout << "Size: " << numbers.size() << "\n";return 0;
}

         unordered_set的主要特性：

                唯一性：容器中不允许有重复的元素

                无序性：元素不以任何特定顺序存储

                哈希实现：基于哈希表实现，平均情况下提供O(1)的查找复杂度

                动态大小：容器可以根据需要动态扩展或收缩

        我们可以把unordered_set理解成不能排序的set，并且unordered_set的插入，删除，查找平均时间复杂度都是O(1)，效率比set要高。

         1.2、unordered_map的使用

        unordered_map是存储键值对的关联容器，其中每个键都是唯一的。与map不同unordered_map中的元素不以任何特定顺序排序。

        操作我们也不细讲了，因为常用接口和map的接口都差不多。

#include <unordered_map>
#include <iostream>
#include <string>int main() {// 创建unordered_mapstd::unordered_map<std::string, int> word_counts = {{"apple", 5},{"banana", 3}};// 插入元素word_counts.insert({"orange", 2});word_counts["pear"] = 4;  // 使用下标操作符插入// 访问元素std::cout << "apple count: " << word_counts["apple"] << "\n";// 查找元素auto it = word_counts.find("banana");if (it != word_counts.end()) {std::cout << "banana count: " << it->second << "\n";}// 删除元素word_counts.erase("orange");// 遍历元素for (const auto& pair : word_counts) {std::cout << pair.first << ": " << pair.second << "\n";}// 获取大小std::cout << "Size: " << word_counts.size() << "\n";return 0;
}

        unordered_map的主要特性：

                键唯一性：每个键只能在容器中出现一次

                无序性：键值对不以任何特定顺序存储

                哈希实现：基于哈希表实现，平均情况下提供O(1)的访问复杂度

                快速访问：通过键可以直接访问对应的值

               如果我们想要支持自定义类型的比较和存储，需要让自定义类型支持哈希映射和==的比较。unordered_map和unordered_set同理。

#include<iostream>
#include<unordered_map>
#include<unordered_set>
using namespace std;struct node
{int _a;int _b;bool operator==(const node& x) const{return (_a == x._a) && (_b == x._b);}
};class A
{
public://需要注意仿函数的重载()一定是public:size_t operator()(const node& x) const{int ret = x._a;ret *= 131;ret += x._b;ret *= 131;return ret;}
};int main()
{unordered_set<node, A> s;unordered_map<node, string, A> mp;s.insert({ 1,1 });s.insert({ 2,2 });node x = { 1,1 };mp[{1, 2}] = "11";node x1 = { 2,3 };mp.insert({x1, "ss"});//传入pair(key,value)return 0;
}

 2、unordered_map和unordered_set的封装

        基于我们上节课实现的哈希表，我们对unordered_set和unordered_map进行封装。需要注意的是我们使用的是链地址法进行封装，因为stl中的unordered_map和unordered_set也是链地址法。

        2.1、KeyOfT

        上期我们的哈希表查找key值，我们是通过直接访问kv.first来实现的。但是由于封装的时候我们想让unordered_set和unordered_map用同一个哈希表，所以我们对哈希表的模板参数中传入KeyOfT，然后在访问key值时使用KeyOfT的方式:

template<class K,class T,class KeyOfT,class Hash>

        这个KeyOfT是跟着unordered_set和unordered_map的时候写的，所以等我们进一步封装的时候再去实现KeyOfT。 

         2.2、迭代器

        我们对上一次的哈希表进行升级，是他支持迭代器：

template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
struct HTIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;Node* _node;const HT* _pht;HTIterator(Node* node,const HT* pht):_node(node),_pht(pht){}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]){_node = _pht->_tables[hashi];break;}//这个地方和线性探测不一样，不要让他成环++hashi;}if (hashi == _pht->_tables.size()){_node = nullptr;//如果跳出循环发现这个位置根本不存在说明没有下一个节点了}//注意这是前置++return *this;}}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return  _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;//比较地址}
};

        我们模板参数有6个，K,T是存储类型不多说了，和我们哈希表的一样，ref是引用，ptr是指针，大家应该也都知道，keyOfT是提取key值，hash是哈希映射函数。

        对于operator++，首先如果这个节点是链中的一个节点，并且他还有下一个节点，那我们直接加加就可以了。如果没有，那么我们就去找下一个链。首先我们通过哈希哈希函数找到当前节点在的链子，记作hashi。然后把hashi加加跳过当前的链子，之后一直往后遍历知道找到下一个链子的位置。

        接下来我们让哈希表支持迭代器。

	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>friend struct HTIterator;typedef HashNode<T> Node;
public:typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;Iterator Begin(){if (_n == 0)return End();for (size_t i = 0;i < _tables.size();i++){if (_tables[i]){return Iterator(_tables[i],this);}}return End();}Iterator End(){return Iterator(nullptr,this);}ConstIterator Begin() const{if (_n == 0)return End();for (size_t i = 0;i < _tables.size();i++){if (_tables[i]){return ConstIterator(_tables[i], this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}

        因为我们在写迭代器类的时候用了hashTable中的私有成员变量，所以要在hashTable中对迭代器类进行友元声明。 

        对于begin来说，我们就通过遍历，找到第一个出现值的位置就行了，如果走到最后了都没出现值，那说明我们当前哈希表是空的，直接返回end(),而end()实际上是返回一个nullptr构造的迭代器。

      2.3、插入

        我们对插入操作改造升级，使他和源码的返回值相同：

pair<Iterator, bool> Insert(const T& data)
{KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return { it,false };Hash hs;if (_n == _tables.size()){//扩容//HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1));遍历旧表，将旧表的数据全部重新映射到新表//for (size_t i = 0; i < _tables.size(); i++)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables);//我们不采用上面的方式，因为上面的方式每个节点都得拷贝一次vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), 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 = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { Iterator(newnode,this),true };
}

        这段内容没什么难点，大家看看就好了。 

         2.4、unordered_map的封装

        现在我们新建一个头文件unordered_map.h，然后写一下unordered_map的类：

#include"HashTable.h"template<class K,class V,class hash=HashFunc<K>>
class unordered_map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) const //仿函数记得加const{return kv.first;}};
public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, hash>::Iterator iterator;typedef typename hash_bucket::HashTable< K, pair<const K, V>, MapKeyOfT, hash>::ConstIterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key,V() });return ret.first->second;}
private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, hash> _ht;
};

        由于我们要保证unordered_map中存储的值的key值不被修改，所以哈希表的私有变量我们第二个传入的模版参数是pair<const K,V>。

        2.5、unordered_set的封装

        说实话这也没啥好说的，大家看看就好。

#include"HashTable.h"
template<class K,class Hash=HashFunc<K>>
class unordered_set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public://注意迭代器都是大类里面封装好的迭代器，不能拿最开始定义的那个类的迭代器typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){return _ht.Begin();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};

3、总结 

        unordered_set经常用于去重以及存在性检查。unordered_map常用于快速键值查找以及频率统计。在后续做算法题时，经常会用到这两个容器。

特性	unordered_set	unordered_map
存储内容	仅 Key	Key-Value 对
哈希冲突处理	链地址法	链地址法
时间复杂度	平均 O(1)，最坏 O(n)	平均 O(1)，最坏 O(n)
动态扩容	需要	需要
迭代器支持	可以自定义	可以自定义

        好了，今天的内容就分享到这，我们下期再见！