【C++】哈希对unordered_map和unodered_set的封装

「爱情、让人受尽委屈。」 2024-04-26 11:03 69阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏： [C++学习][C]  
> ?️博客主页：[睿睿的博客主页][Link 1]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一.哈希表的修改
 *  二.封装map和set
 *  三.普通迭代器
 *  四.const迭代器
 *  五.insert返回值，operator\[\]和key不能修改的问题
 *  总结

## 前言 ##

在前面的学习里面，我们完成了红黑树对map和set的封装，今天我们就用哈希里面的开散列对unordered\_map和unodered\_set进行封装。其实哈希的封装和红黑树的封装是非常相像的，所以我们这里简单道来。

## 一.哈希表的修改 ##

和红黑树一样，我们把模板参数改成：

template<class K,class T,class KeyOfT,class HashFunc = DefaultHashFunc<K>>
    class HashTable
    {
        }

`K`：关键码类型  
`T`：对于unordered\_map，T就是有个键值对；对于unordered\_set，T就是Key。  
`keyOfT`：取出元素（主要是为unordered\_map设计）  
`HashFunc`：仿函数，将key转换成整数，才能进行取模。  
结点改为：

template<class T>
    	struct HashNode
    	{
        
    		T _data;
    		HashNode<T>* _next=nullptr;
    
    		HashNode(const T& data):_data(data)
    		{
        }
    	};

## 二.封装map和set ##

对于map和set，我们也是直接修改一下模板传过来的值就可以了。

## 三.普通迭代器 ##

template<class K, class T,class Ptr,class Ref, class KeyOfT, class  HashFunc>
    	struct HTIterator
    	{
        
    	public:
    
    		typedef HashNode<T> Node;
    		typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc> Self;
    		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
    
    		Node* _node;
    		HashTable <K, T, KeyOfT, HashFunc>* _pht;
    		HTIterator(Node* node, HashTable <K,T,KeyOfT, HashFunc>* pht) :_node(node),_pht(pht)
    		{
        }
    
    		Ref operator*()
    		{
        
    			return _node->_data;
    		}
    
    		Ptr operator->()
    		{
        
    			return &(_node->_data);
    		}
    
    		bool operator!=(const Self& t)
    		{
        
    			return _node != t._node;
    		}
    	};

在这里对于迭代器的++操作，要寻找下一个元素就有两种情况，链表的下一个或者下一个哈希桶，所以这里为了找到下一个哈希桶，就要把哈希传过来，所以这里要传哈希的指针，为了使迭代器可以写出哈希的指针，这里的迭代器的模板参数也要有`keyofT`和`hashfunc`。

Self& operator++()
    		{
        
    			if (_node->_next)
    			{
        
    				_node = _node->_next;
    			}
    			else
    			{
        
    				KeyOfT kot;
    				HashFunc hf;
    				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
    				hashi++;
    				while (hashi < _pht->_table.size())
    				{
        
    					if (_pht->_table[hashi])
    					{
        
    						_node = _pht->_table[hashi];
    						return *this;
    					}
    					hashi++;
    				}
    
    					_node = nullptr;
    			}
    
    			return *this;
    		}

## 四.const迭代器 ##

随后我们就可以构造出const迭代器了。随后我们就要写出用普通迭代器构造const迭代器的构造函数。并且这里要在hashtable之前使用hashtable，就要先申明一下：

//这里就别写= DefaultHashFunc<K> 了，不然会保错：重定义参数
    	template<class K, class T, class KeyOfT, class  HashFunc>
    	class HashTable;
    	template<class K, class T,class Ptr,class Ref, class KeyOfT, class  HashFunc>
    	struct HTIterator
    	{
        
    	public:
    
    		typedef HashNode<T> Node;
    		typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc> Self;
    		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
    
    		Node* _node;
    
    		//这里如果传过来的是const类型的pht，权限会放大，所以说要改成下面的情况：
    		//HashTable <K, T, KeyOfT, HashFunc>* _pht;
    		/*HTIterator(Node* node, HashTable <K,T,KeyOfT, HashFunc>* pht) :_node(node),_pht(pht)
    		{}*/
    
    		//因为在这里我们对于这个哈希桶不会进行修改，所以直接用const修饰，这样只会出现权限的缩小或平移
    		const HashTable <K, T, KeyOfT, HashFunc>* _pht;
    		HTIterator(Node* node, const HashTable <K, T, KeyOfT, HashFunc>* pht) :_node(node), _pht(pht)
    		{
        }
    
    		HTIterator(const iterator& it) :_node(it._node), _pht(it._pht)
    		{
        }
    
    		Ref operator*()
    		{
        
    			return _node->_data;
    		}
    
    		Ptr operator->()
    		{
        
    			
    			return &(_node->_data);
    		}
    
    		Self& operator++()
    		{
        
    			if (_node->_next)
    			{
        
    				_node = _node->_next;
    			}
    			else
    			{
        
    				KeyOfT kot;
    				HashFunc hf;
    				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
    				hashi++;
    				while (hashi < _pht->_table.size())
    				{
        
    					if (_pht->_table[hashi])
    					{
        
    						_node = _pht->_table[hashi];
    						return *this;
    					}
    					hashi++;
    				}
    
    					_node = nullptr;
    			}
    
    			return *this;
    		}
    
    		bool operator!=(const Self& t)
    		{
        
    			return _node != t._node;
    		}
    	};

## 五.insert返回值，operator\[\]和key不能修改的问题 ##

这里和红黑树封装map和set类似，就不用多说了。下面看看完整代码：

#pragma once
    #include<vector>
    #include<iostream>
    using namespace std;
    
    
    template<class T>
    class DefaultHashFunc
    {
        
    public:
    	size_t operator()(const T& key)
    	{
        
    		return (size_t)key;
    	}
    };
    
    template<>
    class DefaultHashFunc<string>
    {
        
    public:
    	size_t operator()(const string& key)
    	{
        
    		size_t value = 1;
    		for (auto& e : key)
    		{
        
    			value *= 131;
    			value += e;
    		}
    		return value;
    	}
    };
    namespace hash_bucket
    {
        
    	template<class T>
    	struct HashNode
    	{
        
    		T _data;
    		HashNode<T>* _next=nullptr;
    
    		HashNode(const T& data):_data(data)
    		{
        }
    	};
    
    
    	//这里就别写== DefaultHashFunc<K> 了，不然会保错：重定义参数
    	template<class K, class T, class KeyOfT, class  HashFunc >
    	class HashTable;
    
    	template<class K, class T,class Ptr,class Ref, class KeyOfT, class  HashFunc>
    	struct HTIterator
    	{
        
    	public:
    
    		typedef HashNode<T> Node;
    		typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc> Self;
    		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
    
    		Node* _node;
    
    		//这里如果传过来的是const类型的pht，权限会放大，所以说要改成下面的情况：
    		//HashTable <K, T, KeyOfT, HashFunc>* _pht;
    		/*HTIterator(Node* node, HashTable <K,T,KeyOfT, HashFunc>* pht) :_node(node),_pht(pht)
    		{}*/
    
    		//因为在这里我们对于这个哈希桶不会进行修改，所以直接用const修饰，这样只会出现权限的缩小或平移
    		const HashTable <K, T, KeyOfT, HashFunc>* _pht;
    		HTIterator(Node* node, const HashTable <K, T, KeyOfT, HashFunc>* pht) :_node(node), _pht(pht)
    		{
        }
    
    		HTIterator(const iterator& it) :_node(it._node), _pht(it._pht)
    		{
        }
    
    		Ref operator*()
    		{
        
    			return _node->_data;
    		}
    
    		Ptr operator->()
    		{
        
    			return &(_node->_data);
    		}
    
    		Self& operator++()
    		{
        
    			if (_node->_next)
    			{
        
    				_node = _node->_next;
    			}
    			else
    			{
        
    				KeyOfT kot;
    				HashFunc hf;
    				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
    				hashi++;
    				while (hashi < _pht->_table.size())
    				{
        
    					if (_pht->_table[hashi])
    					{
        
    						_node = _pht->_table[hashi];
    						return *this;
    					}
    					hashi++;
    				}
    
    					_node = nullptr;
    			}
    
    			return *this;
    		}
    
    		bool operator!=(const Self& t)
    		{
        
    			return _node != t._node;
    		}
    	};
    
    	template<class K,class T, class KeyOfT,class HashFunc= DefaultHashFunc<K> >
    	class HashTable
    	{
        
    		typedef HashNode<T> Node;
    		//友员声明
    		template<class K, class T, class Ptr,class Ref,class KeyOfT, class HashFunc>
    		friend struct HTIterator;
    	public:
    		HashTable()
    		{
        
    			_table.resize(10,nullptr);
    		}
    
    		~HashTable()
    		{
        
    			for (int i = 0; i < _table.size(); i++)
    			{
        
    				Node* cur = _table[i];
    				while (cur)
    				{
        
    					Node* next = cur->_next;
    					delete cur;
    					cur = next;
    					
    				}
    
    				_table[i] = nullptr;
    			}
    		}
    
    		typedef HTIterator<K, T,T*,T&, KeyOfT, HashFunc>  iterator;
    		typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc>  const_iterator;
    
    
    		iterator begin()
    		{
        
    			for (int i = 0; i < _table.size(); i++)
    			{
        
    				if (_table[i])
    				{
        
    					return iterator(_table[i], this);
    				}
    			}
    
    			return iterator(nullptr, this);
    		}
    
    
    		iterator end()
    		{
        
    			return iterator(nullptr, this);
    		}
    
    		const_iterator begin() const
    		{
        
    			for (int i = 0; i < _table.size(); i++)
    			{
        
    				if (_table[i])
    				{
        
    					return const_iterator(_table[i], this);
    				}
    			}
    
    			return const_iterator(nullptr, this);
    		}
    
    
    		const_iterator end() const
    		{
        
    			return const_iterator(nullptr, this);
    		}
    
    		pair<iterator,bool> Insert(const T& data)
    		{
        
    			KeyOfT kot;
    			auto it = Find(kot(data));
    			if (it!=end())
    			{
        
    				return make_pair(it,true);
    			}
    			HashFunc hf;
    			if (_table.size() == _n)
    			{
        
    				//扩容
    
    				HashTable newhash;
    				size_t newsize = _table.size() * 2;
    				newhash._table.resize(newsize);
    				for (int i = 0; i < _table.size(); i++)
    				{
        
    					Node* cur = _table[i];
    					while (cur)
    					{
        
    						Node* next = cur->_next;
    						
    						size_t hashi = hf(kot(cur->_data)) % newsize;
    						cur->_next = newhash._table[i];
    						newhash._table[i] = cur;
    
    						cur = next;
    					}
    					_table[i] = nullptr;
    				}
    
    				_table.swap(newhash._table);
    			}
    			
    			size_t hashi = hf(kot(data)) % _table.size();
    			Node* cur = new Node(data);
    			cur->_next = _table[hashi];
    			_table[hashi] = cur;
    			_n++;
    
    			return make_pair(iterator(cur,this),false);
    			
    		}
    
    
    
    		iterator Find(const K& key)
    		{
        
    			HashFunc hf;
    			KeyOfT kot;
    			size_t hashi = hf(key) % _table.size();
    			Node* cur = _table[hashi];
    			while (cur)
    			{
        
    				if (kot(cur->_data) == key)
    				{
        
    					return iterator(cur,this);
    				}
    				cur = cur->_next;
    			}
    
    			return end();
    		}
    
    		bool Erase(const K& key)
    		{
        
    			HashFunc hf;
    			KeyOfT kot;
    			size_t hashi = hf(key) % _table.size();
    			Node* cur = _table[hashi];
    			Node* prev = nullptr;
    			while (cur)
    			{
        
    				
    				if (kot(cur->_data) ==key)
    				{
        
    					if (prev == nullptr)
    					{
        
    						_table[hashi] = cur->_next;
    					}
    					else
    					{
        
    						prev->_next = cur->_next;
    					}
    					delete cur;
    					cur = nullptr;
    					return true;
    				}
    
    				prev = cur;
    				cur = cur->_next;
    			}
    
    			return false;
    
    			
    		}
    
    		void Print()
    		{
        
    			for (int i = 0; i < _table.size(); i++)
    			{
        
    				printf("[%d]: ", i);
    				Node* cur = _table[i];
    
    				while (cur)
    				{
        
    					cout << "("<<cur->_kv.first << ":" << cur->_kv.second<<")" << " ->";
    					cur = cur->_next;
    				}
    				printf("NULL\n");
    			}
    		}
    	private:
    		vector<Node*>  _table;
    		size_t _n=0;
    	};
    }

**set的封装：**

namespace zxr
    {
        
    	template<class K>
    	class unordered_set
    	{
        
    	private:
    		struct SetKeyOfT
    		{
        
    			const K& operator()(const K& key)
    			{
        
    				return key;
    			}
    		};
    		hash_bucket::HashTable<K, K,SetKeyOfT> _ht;
    
    	public:
    
    		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
    		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
    
    		iterator begin()const
    		{
        
    			return _ht.begin();
    		}
    		iterator end()const
    		{
        
    			return _ht.end();
    		}
    		pair<iterator,bool> insert(const K&data)
    		{
        
    			pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> it= _ht.Insert(data);
    			return pair<iterator,bool>(it.first, it.second);
    			
    		}
    
    		bool erase(const K& key)
    		{
        
    			return _ht.Erase(key);
    		}
    		bool find(const K& key)
    		{
        
    			return _ht.Find(key);
    		}
    	};
    }

**map的封装：**

namespace zxr
    {
        
    	template<class K,class V>
    	class unordered_map
    	{
        
    	private:
    		struct MapKeyOfT
    		{
        
    			const K& operator()(const pair<const K,V>& kv)
    			{
        
    				return kv.first;
    			}
    		};
    		hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT> _ht;
    
    	public:
    		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator 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<const K,V>& data)
    		{
        
    			return _ht.Insert(data);
    		}
    
    		V& operator [](const K& key)
    		{
        
    			auto it = insert(make_pair(key,V()));
    			return it.first->second;
    		}
    		bool erase(const K& key)
    		{
        
    			return _ht.Erase(key);
    		}
    		bool find(const K& key)
    		{
        
    			return _ht.Find(key);
    		}
    	};
    }

## 总结 ##

![在这里插入图片描述][11a97f5cc9714b6bb721efc1375d0c11.png]  
  在这里我们在讲几个之前没理解的点，我们的迭代器在平时可以用const迭代器来介绍迭代器，就是因为库里面已经写了用普通迭代器构造const迭代器的构造函数，随意我们才能理所当然的使用。  
这里要强调的还是，同一模板传了不同参数，此时就生成了两个不同的类型，无论模板参数是const还是普通，都不在是同一个类型了。  
![在这里插入图片描述][d3542481a7a8476ab1723da8a2e216e3.png]

封装的过程都是这样的：  
1、哈希表  
2、封装map和set  
3、普通迭代器  
4、const迭代器  
5、insert返回值 operator\[\]  
6、key不能修改的问题

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 2]  
> [C语言学习][C 1]  
> [算法][Link 3]  
> [智力题][Link 4]  
> [初阶数据结构][Link 5]  
> [Linux学习][Linux]  
> [C++学习][C]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/12f74707e0d74b0db152affa52aac3f3.gif
[C]: https://blog.csdn.net/qq_74310471/category_12289978.html
[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f2d441bf56ea4a578f41375ecaa28b67.gif
[11a97f5cc9714b6bb721efc1375d0c11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/7cee09ec97c649f6a714bdb6002491ea.png
[d3542481a7a8476ab1723da8a2e216e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f0fc3096af1d4810944e50cc144beae6.png
[Link 2]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[C 1]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 5]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Linux]: https://blog.csdn.net/qq_74310471/category_12291120.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e299369803ac4b8a8c943c6bde37b1dd.gif