【C++】开散列实现unordered_map与unordered_set的封装

平凡的人1

发布于 2023-10-15 12:19:01

19300

代码可运行

文章被收录于专栏：从小白开始修炼从小白开始修炼

运行总次数：0

代码可运行

本文主要介绍unordered_map与unordered_set的封装，此次封装主要用上文所说到的开散列,通过开散列的一些改造来实现unordered_map与unordered_set的封装

一、模板参数

由于unordered_set 是 K 模型的容器，而 unordered_map 是 KV 模型的容器,所以需要对结点的参数进行改造，unordered_set可以使用，unordered_map也可以使用,改为T _data即可

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

T模板参数可能是键值Key，也可能是Key和Value构成的键值对。如果是unordered_map容器，那么它传入底层哈希表的模板参数就是Key和Key和Value构成的键值对，如果是unordered_set容器，那么它传入底层哈希表的模板参数就是Key和Key

	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
	private:
		buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};

	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
     private: 
		buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;
	};

如此就可以实现泛型了，如果是unordered_set，结点当中存储的是键值Key；如果是unordered_map，结点当中存储的就是<Key, Value>键值对：

哈希表仿函数的支持：KeyOfT👇

我们通过哈希计算出对应的哈希地址：但是插入的时候就不能直接用data去进行比较了

对于unordered_set:data是key是可以比较的，对于unordered_map:data是键值对,我们需要取出键值对的first。而data既可以是unordered_set的，也可以是unordered_map的，所以我们需要仿函数来实现不同容器所对应的需求，然后传入：

unordered_map返回kv.first

template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
    }
	private:
		buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};

unordered_set返回key:

template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
     private: 
		buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;
	};

这也就是Hashtable需要KeyOfT的原因所在。

二、string的特化

字符串无法取模，在这里重新写一遍，字符串无法取模的问题写库的大神们早就想到了

预留一个模板参数，无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 131;
			//顺序？abc，cba
			hash += ch;
		}
		return hash;
	}
};

string的特化：符合string类型的优先走string类型

template<class K,class V,class Hash=HashFunc<K>>
class unordered_map
template<class K,class Hash = HashFunc<K>>
class unordered_set

三、正向迭代器

哈希表的正向迭代器对哈希表指针和结点指针进行了封装，++运算符重载，可以访问下一个非空的桶，所以每个正向迭代器里面存的是哈希表地址。

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

	template<class K,class T,class Hash,class KeyOfT>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Hash, KeyOfT> Self;
		typedef HashTable<K, T, Hash, KeyOfT> HT;

		Node* _node;
		HT* _ht;
    }

所以我们构造迭代器的时候需要知道节点的地址和哈希表的地址

	__HTIterator(Node*node,HT*ht)
			:_node(node)
			,_ht(ht)
		{}

++运算符重载的实现：如果当前的桶还有节点，那么++就是当前桶下一个节点，如果当前元素是所在的桶的最后一个元素，那么++就是下一个非空的桶了

如何去找下一个非空桶：其实很简单，通过当前节点的值算出当前桶的hashi，然后++hashi就是下一个桶了，找到下一个非空桶即可

		T& operator*()
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &_node->_data;
		}

		bool operator !=(const Self& s) const
		{
			return _node != s._node;
		}
		Self& operator++()
		{
			if (_node->_next)//当前桶还有节点
			{
				_node = _node->_next;
			}
            //找下一个非空的桶
			else
			{
				KeyOfT kot;
				Hash hash;
				size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();//当前桶的哈希地址
				++hashi;
				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])//非空桶

					{
						_node = _ht->_tables[hashi];
						break;
					}
					else
					{
						++hashi;
					}
				}
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
	};

–问题：哈希表中的迭代器是单向迭代器，并没有反向迭代器，所以没有实现–-运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。

存在的小细节：👇

	template<class K,class T,class Hash,class KeyOfT>
	class HashTable
	{
		typedef HashNode<T> Node;
		template<class K,class T,class Hash,class KeyOfT>
		friend struct __HTIterator;

	public:
		typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this);
				}
			}
			return iterator(nullptr, this);
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
      private:
		vector<Node*> _tables;
		size_t _n = 0;
    };

++运算符重载去寻找下一个结点时，会访问_tables,而_tables是哈希表中的私有成员，所以我们需要把迭代器__HTIterator声明为哈希表的友元

正向迭代器__HTIterator的typedef放在了public,这是为了外部能够使用我们的typedef之后的正向迭代器

还需要注意的是，哈希表的 const 迭代器不能复用普通迭代器的代码，我们查看源码：

这与我们之前所复用的不同，上面stl源码中可以看到并没有用以前的复用：

这是因为如果使用const版本，那么_tables使用[]返回的就是const版本，那么Node*就相当于是const Node*,就会导致权限放大，无法构造;如果改成const HT* _ht; const Node* _node;，又会导致[]不能修改的问题:

四、构造与析构

默认构造

HashTable()
			:_n(0)
		{
			_tables.resize(__stl_next_prime(0));
		}

析构函数

哈希表当中存储的结点都是new出来的，所以哈希表被析构时必须delete。在析构哈希表时我们只需要遍历取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可👇

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				// 释放桶
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				_tables[i] = nullptr;
			}
		}

五、[]的实现

要想实现[]，我们需要先把Insert的返回值修改成pair<iterator,bool>,最后的返回值也要一起修改

如果有重复的元素就返回这个找到it迭代器 没有重复的就返回newnode迭代器

		pair<iterator, bool> Insert(const T&data)
		{
			KeyOfT kot;
			iterator it = Find(kot(data));
			if (it != end())
			{
				return make_pair(it, false);
			}
			if (_tables.size() == _n)
			{
				vector<Node*> newTables;
				newTables.resize(__stl_next_prime(_tables.size()), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = Hash()(kot(cur->_data))% newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}
			size_t hashi = Hash()(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode,this),true);
		}

六、unordered_map的实现

#pragma once

#include "HashTable.h"
namespace hwc
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}

		pair<iterator, bool> insert(const pair<K, V> data)
		{
			return _ht.Insert(data);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};


	void test_unordered_map()
	{
		string arr[] = { "苹果","香蕉","苹果","西瓜","哈密瓜"};
		unordered_map<string, int> countMap;
		for (auto& e : arr)
		{
			countMap[e]++;
		}

		for (const auto& kv : countMap)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
	}
}

七、unordered_set的实现

#pragma once

#include "HashTable.h"

namespace hwc
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename buckethash::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private: 
		buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;
	};


	void test_unordered_set()
	{
		unordered_set<int> us;
		us.insert(13);
		us.insert(3);
		us.insert(23);
		us.insert(5);
		us.insert(5);
		us.insert(6);
		us.insert(15);
		us.insert(223342);
		us.insert(22);

		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : us)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

八、哈希表代码

#pragma once
#pragma once

#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 131;
			//顺序？abc，cba
			hash += ch;
		}
		return hash;
	}
};


//开散列
namespace buckethash
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

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

	template<class K,class T,class Hash,class KeyOfT>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Hash, KeyOfT> Self;
		typedef HashTable<K, T, Hash, KeyOfT> HT;

		Node* _node;
		HT* _ht;

		__HTIterator(Node*node,HT*ht)
			:_node(node)
			,_ht(ht)
		{}

		T& operator*()
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &_node->_data;
		}

		bool operator !=(const Self& s) const
		{
			return _node != s._node;
		}
		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				Hash hash;
				size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
				++hashi;
				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])
					{
						_node = _ht->_tables[hashi];
						break;
					}
					else
					{
						++hashi;
					}
				}
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
	};

	template<class K,class T,class Hash,class KeyOfT>
	class HashTable
	{
		typedef HashNode<T> Node;
		template<class K,class T,class Hash,class KeyOfT>
		friend struct __HTIterator;

	public:
		typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this);
				}
			}
			return iterator(nullptr, this);
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}



		HashTable()
			:_n(0)
		{
			_tables.resize(__stl_next_prime(0));
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				// 释放桶
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				_tables[i] = nullptr;
			}
		}

		pair<iterator, bool> Insert(const T&data)
		{
			KeyOfT kot;
			iterator it = Find(kot(data));
			if (it != end())
			{
				return make_pair(it, false);
			}
			if (_tables.size() == _n)
			{
				vector<Node*> newTables;
				newTables.resize(__stl_next_prime(_tables.size()), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = Hash()(kot(cur->_data))% newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}

			size_t hashi = Hash()(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode,this),true);
		}

		iterator Find(const K& key)
		{
			KeyOfT kot;
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}
				else
				{
					cur = cur->_next;
				}
			}
			return end();
		}

		bool Erase(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (cur == _tables[hashi])
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (int i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return __stl_prime_list[__stl_num_primes - 1];
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}

本篇到此结束…

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-10-11，如有侵权请联系 cloudcommunity@tencent.com 删除

c++