C++用哈希表封装unordered_set和unordered_map

发布时间：2023年12月20日

前言? ? ? ??

一、修改kv模型为data模型

1.添加MyUnorderedSet.h和MyUnorderedMap.h

四、unordered_map重载operator[]?

总结

前言? ? ? ??

????????在上一篇文章中，我们手写了一份哈希表，也确实实现了插入删除查找等功能，但是我们只写了一份“Key，Value”模型的哈希表，并没有“Key”模型的，同时我们也没有迭代器遍历的功能，因此我们现在要用写好的哈希表去模仿库里面的unordered_ser和unordered_map。

? ? ? ?本文是根据这个哈希表进行的修改添加，具体代码如下

HashTable.h

#pragma once
#include<vector>
 
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
 
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto& e : s)
		{
			sum *= 31;
			sum += e;
		}
		return sum;
	}
};
namespace kky_open_address
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE,
	};
	
	template<class K, class V>
	struct HashDate
	{
		pair<K, V> _kv;
		Status _s;
	};
 
	template<class K,class V ,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		Hash hs;
 
		HashDate<K,V>* Find(const K& key)
		{
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s != DELETE && _tables[hashi]._kv.first == key)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}
 
		bool Erase(const K& key)
		{
			HashDate<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			return false;
		}
 
		bool Insert(const pair<K,V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
			if (_n*10 / _tables.size() >= 7)
			{
				int newcapacity = _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newcapacity);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if(_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
 
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;
 
			return true;
		}
		
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//printf("[%d]->%d:%s\n", i,_tables[i]._kv.first, "EXIST");
					cout << "[" << i << "]->" << _tables[i]._kv.first<<":" << _tables[i]._kv.second << endl;
				}
				else if(_tables[i]._s == EMPTY)
				{
					//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "EMPTY");
					cout << "[" << i << "]->" <<endl;
				}
				else
				{
					//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "DELETE");
					cout << "[" << i << "]->" <<"DELETE" << endl;
				}
			}
			cout << endl;
		}
 
	private:
		vector<HashDate<K,V>> _tables;
		size_t _n;
	};
 
	void test01()
	{
		HashTable<int, int> ht;
		int arr[] = { 3,13,23,4,5,14,7,13 };
		for (auto e : arr)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Print();
		ht.Erase(13);
		ht.Print();
		ht.Insert(make_pair(33,33));
		ht.Print();
	}
	void test02()
	{
		string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
		HashTable<string, int> ht;
		for (auto e : arr)
		{
			HashDate<string, int>* ret = ht.Find(e);
			if(ret)
				ret->_kv.second++;
			else
				ht.Insert(make_pair(e, 1));
		}
		ht.Print();
	}
}
 
namespace kky_hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;
		HashNode(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
 
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		HashTable(const HashTable<K,V>& ht)
		{
			_tables.resize(ht._tables.size(), nullptr);
			for (size_t i = 0; i < ht._tables.size(); i++)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* newnode = new Node(cur->_kv);
					if (_tables[i]==nullptr)
					{
						_tables[i] = newnode;
					}
					else
					{
						newnode->_next = _tables[i];
						_tables[i] = newnode;
					}
					cur = cur->_next;
				}
			}
		}
 
		HashTable<K, V>& operator=(HashTable<K, V> ht)
		{
			_tables.swap(ht._tables);
			swap(_n, ht._n);
			return *this;
		}
 
 
		~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;
			}
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			Hash hs;
			if (Find(kv.first))
				return false;
			if (_n == _tables.size())
			{
				vector<Node*> newtables;
				newtables.resize(_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(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					//置空，防止析构出现问题
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}
			size_t hashi = hs(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}
 
		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
 
		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
 
					return true;
				}
 
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
 
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				cout << "[" << i << "]" << "挂载"<<"->";
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				cout << endl;
			}
			cout << endl;
		}
 
		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			double averageBucketLen = 0;
 
 			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}
 
				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}
 
 
				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}
 
			averageBucketLen = (double)bucketSize / (double)_n;
 
			printf("all bucketSize:%d\n",_tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}
 
	private:
		vector<Node*> _tables;
		size_t _n;
	};
	void test01()
	{
		HashTable<int, int> ht;
		int arr[] = { 3,13,23,4,5,14,33,34,43,44 };
		for (auto e : arr)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Print();
		cout << ht.Find(43) << endl;
		ht.Erase(43);
		ht.Print();
		cout << ht.Find(43) << endl;
	}
	void test02()
	{
		string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
		HashTable<string, int> ht;
		for (auto e : arr)
		{
			HashNode<string, int>* ret = ht.Find(e);
			if (ret)
				ret->_kv.second++;
			else
				ht.Insert(make_pair(e, 1));
		}
	}
	void test03()
	{
		const size_t N = 1000000;
 
		unordered_set<int> us;
		set<int> s;
		HashTable<int, int> ht;
 
		vector<int> v;
		v.reserve(N);
		srand(time(0));
		for (size_t i = 0; i < N; ++i)
		{
			//v.push_back(rand()); // N比较大时，重复值比较多
			v.push_back(rand() + i); // 重复值相对少
			//v.push_back(i); // 没有重复，有序
		}
 
		size_t begin1 = clock();
		for (auto e : v)
		{
			s.insert(e);
		}
		size_t end1 = clock();
		cout << "set insert:" << end1 - begin1 << endl;
 
		size_t begin2 = clock();
		for (auto e : v)
		{
			us.insert(e);
		}
		size_t end2 = clock();
		cout << "unordered_set insert:" << end2 - begin2 << endl;
 
		size_t begin10 = clock();
		for (auto e : v)
		{
			ht.Insert(make_pair(e, e));
		}
		size_t end10 = clock();
		cout << "HashTbale insert:" << end10 - begin10 << endl << endl;
 
 
		size_t begin3 = clock();
		for (auto e : v)
		{
			s.find(e);
		}
		size_t end3 = clock();
		cout << "set find:" << end3 - begin3 << endl;
 
		size_t begin4 = clock();
		for (auto e : v)
		{
			us.find(e);
		}
		size_t end4 = clock();
		cout << "unordered_set find:" << end4 - begin4 << endl;
 
		size_t begin11 = clock();
		for (auto e : v)
		{
			ht.Find(e);
		}
		size_t end11 = clock();
		cout << "HashTable find:" << end11 - begin11 << endl << endl;
 
		cout << "插入数据个数：" << us.size() << endl << endl;
		ht.Some();
 
		size_t begin5 = clock();
		for (auto e : v)
		{
			s.erase(e);
		}
		size_t end5 = clock();
		cout << "set erase:" << end5 - begin5 << endl;
 
		size_t begin6 = clock();
		for (auto e : v)
		{
			us.erase(e);
		}
		size_t end6 = clock();
		cout << "unordered_set erase:" << end6 - begin6 << endl;
 
		size_t begin12 = clock();
		for (auto e : v)
		{
			ht.Erase(e);
		}
		size_t end12 = clock();
		cout << "HashTable Erase:" << end12 - begin12 << endl << endl;
	}
}

? ? ? ? 我们也借鉴了红黑树封装set和map的思想来进行封装。（画图还算比较详细，没看过最好可以小看一下，不然会有点难懂）

? ? ? ? 大厦并不是一下子建成，我们在封装过程中需要缝缝补补，这也是为什么我们看库里面的文件，一时间难以看懂，因为库里面的也是一步一步封装好的。那接下来让我们开始封装吧！

一、修改kv模型为data模型

一样的，我们要将“Key，Value”模型普适化，让这一份代码既可以封装“Key”模型，也可以封装“Key，Value”模型。

1.添加MyUnorderedSet.h和MyUnorderedMap.h

HashTable的第一个参数是Key，无需多说，“Key”模型，和“Key，Value”模型都需要Key。

让第二个参数来决定到底是“Key”模型还是“Key，Value”模型。“Key”模型第二个参数也是Key，“Key，Value”第二个参数是pair<const K,V>。（加const目的是让K无法修改）

同时，将Hash函数放在unordered_set和unordered_map里，因为我们封装的目的就是让你去调用这两个类，而不是去调用HashTable，因此你应该在这里传递Hash函数，并给缺省值。

MyUnorderedSet.h添加

#pragma once
#include"HashTable.h"

namespace kky
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
	private:
		kky_hash_bucket::HashTable<K, K, Hash> ht;
	};
}

MyUnorderedMap.h添加?

#pragma once
#include"HashTable.h"

namespace kky
{
	template<class K,class V,class Hash = HashFunc<K>>
	class unordered_map
	{
	private:
		kky_hash_bucket::HashTable<K, pair<const K, V>, Hash> ht;
	};
}

2.修改HashNode

? ? ? ? 首先，将HashNode模板参数改成T，你传递的T是“pair<K,V>”，那我里面的数据_data就是pair<K,V>，你传递T的是“Key”，数据_data也是Key。

3.修改HashTable

模板类型改成T，同时修改下面的类型，该给T就给T。

但我们仅仅修改这个T也是无法达到想要的效果。比如find函数我们传递的类型是单值key，通过key判断在不在，你如果是kv模型，就会存在问题，所以我们应该添加上仿函数帮助我们处理。

unordered_set里添加SetKeyOfT，走个过场，取出key，并将类型传递给HashTable当做第三参数

unordered_map里添加MapKeyOfT，取出kv中的key，传递给HashTable当做第三参数。

?在HashTable也添加KeyOfT，后续构建的地方也都添加这个类。如下

用KeyOfT构建对象，无论是k还是kv，利用仿函数就可以取出存在data里面的key了。

后续的地方都可以这样取出，为了方便观看，这里就不多做展示了。?

最后使用代码测试一下，set测试

map测试

没问题，成功的用一张哈希表构建出了k模型和kv模型。?

二、普通迭代器

现在我们要封装迭代器了，但是迭代器的++还算是个问题。

如下图，如果当前结点是4，那么我们很容易找到他的下一个结点为14，但如果一直++到44呢？44的下一个应该是5了，那我们如何知道当前的索引hashi为多少呢？并且我们哈希表也没有，就算知道了索引hashi也没办法计算。

因此，至少我们得将哈希表的地址传递给iterator当做参数，只有能够访问到哈希表，才可以进行迭代器的++。

????????那么hashi我们要不要传，如果传，就可以直接用，如果不传，我们也可以通过哈希表来计算。因为迭代器我们并不会生成很多个，大部分的使用场景都是只使用O（1）个迭代器帮我们遍历。这里为了效率，我们牺牲了一点点空间，我们选择传递hashi。

????????那么我们现在就有三个参数，一个结点node，一个哈希表pht，还有一个索引hashi。

????????并写出构造函数、operator++、operator!=、operator*、operator->?。

operator!=、operator*、operator-> 都很简单不多赘述。

????????对于operator++，如果当前节点的_next存在，就走到_next即可，若不存在，根据hashi++，一直走到结点存在的地方，_node = _pht->_tables[_hashi];? 如果hashi==_tables.size()，也就是走到了末尾还没遇到不为空的结点，证明后续没有结点了，就将_node给到nullptr，最后return *this;

代码如下

template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator
{
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, KeyOfT, Hash> Self;
	HashTable<K, T, KeyOfT, Hash>* _pht;
	Node* _node;
	size_t _hashi;
	__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht,size_t hashi)
		:_node(node)
		,_pht(pht)
		,_hashi(hashi)
	{}
	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			while (++_hashi < _pht->_tables.size())
			{
				if (_pht->_tables[_hashi])
				{
					_node = _pht->_tables[_hashi];
					break;
				}
			}
            if (_hashi == _pht->_tables.size())
            {
				_node = nullptr;
            }
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

后续我们就在HashTable里面添加iterator的begin()和end()，同时再unordered_map和unordered_set里复用一下迭代器就可以了。

HashTable添加如下代码

unordered_set添加（为什么要用typename，因为走到当前iterator的时候，哈希表里面的iterator，还没有实例化，加了typename告诉编译器，你先别急，等后面实例化之后再去找iterator?在红黑树封装map和set有更详细的介绍。）

?unordered_map添加

我们用如下代码测试一下

报错了，看下面的第二张图，我们发现_pht根本找不到，这是为什么呢？

这是因为编译器会往上找，并不会往下找，目前的_HTIterator和HashTable他们两个存在相互依赖的关系，HashTable要用_HTIterator里面的iterator,_HTIterator要用HashTable这一张表，那么我们应该如何处理呢？

第一个方法是不要传递HashTable，传递HashTable里面的vector，因为我们只使用到了HashTable里面的那个vector，来进行遍历（实现++操作里面需要）。这是一个办法。
第二个方法是前置声明，告诉编译器HashTable在下面，你去下面找。

这里我们选择了第二种方法，目的是让我们可以更好的掌握前置声明，还有友元（等下会提到）

那么我们只需要在前面添加上声明即可。

?????????添加前置声明后，再次编译，又报错了，看下面第二张图，报错提示告诉我们_pht里_tables是私有成员，外部无法访问。

????????这就可以用到C++友元的概念了，在A中写友元B，代表B是A的友元，B类里面可以访问A类私有成员。那么我想让__HTIterator访问HashTable的私有成员，那么就应该在HashTable里面写友元__HTIterator。

? ? ? ? HashTable添加如下代码即可

现在就没有问题了。

三、const迭代器?

老生常谈了，const迭代器只有这两个地方改为const就可以了。

HashTable中iterator和const_iterator模板参数为

再如下修改一下即可?

?再添加一份const_iterator的begin()和end()方便调用

unordered_set修改如下，因为set的特性是只有key，因此无论iterator还是const_iterator我们都不要修改，因此typedef都为const_iterator，也就是无论iterator还是const_iterator本质都为const_iterator

unordered_map需要普通的迭代器不能修改key，const的迭代器kv都不能修改，因此是正常操作，代码如下

完成修改后，我们就按照之前的代码运行一下，看看普通的有没有bug，发现报错了，这是为什么呢？

分析情况如下，你构建const迭代器时传递的this被const修饰过，由于构造参数写的是普通的，因此传参发生了权限扩大，就报错了，?

修改如下，添加上const关键字，同时也要在变量_pht的地方也用const修饰，不然用const的赋值给普通的也是不可以的。

再次运行就没问题了。

切换为const迭代器再做测试。

我们在__HTIterator写一个拷贝构造函数，支持从普通的转为const的就可以了。?

?最后测试，没问题了。

四、unordered_map重载operator[]?

要将Insert返回类型从bool转化为iterator （为什么可以去红黑树封装set和map查看）

同时Find函数也应该修改，需要返回一个迭代器，修改如下

?Insert函数修改

?unordered_set修改

unordered_map也修改?

重载operator[]，为什么返回的是ret.frist->second呢？

ret.frist是iterator，我们iterator里面重载了operator->，这样就可以去到_data数据的地址了，再->second就可以取到第二个数据，这里编译器帮我们简化了，因此可以少些一个->

实际上应该这样写，但是太不美观了，为了可读性采用上面的写法。

最后测试一下，没问题。?

总结

????????我们修改了很多地方，一直在缝缝补补，为什么不一下子就弄好呢？因为我刚学会走路，你偏要我去跨栏，那我不得先把走路联系好，再学跑步，最后再去跨栏嘛，一步一步虽然慢，但是胜在稳健，封装也是如此。

? ? ? ? 最后附上总代码

HashTable.h

#pragma once
#include<vector>

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto& e : s)
		{
			sum *= 31;
			sum += e;
		}
		return sum;
	}
};
namespace kky_open_address
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE,
	};

	template<class K, class V>
	struct HashDate
	{
		pair<K, V> _kv;
		Status _s;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
			:_n(0)
		{
			_tables.resize(10);
		}
		Hash hs;

		HashDate<K, V>* Find(const K& key)
		{
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s != DELETE && _tables[hashi]._kv.first == key)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashDate<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			return false;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
			if (_n * 10 / _tables.size() >= 7)
			{
				size_t newcapacity = _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newcapacity);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;

			return true;
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//printf("[%d]->%d:%s\n", i,_tables[i]._kv.first, "EXIST");
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "EMPTY");
					cout << "[" << i << "]->" << endl;
				}
				else
				{
					//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "DELETE");
					cout << "[" << i << "]->" << "DELETE" << endl;
				}
			}
			cout << endl;
		}

	private:
		vector<HashDate<K, V>> _tables;
		size_t _n;
	};

	void test01()
	{
		HashTable<int, int> ht;
		int arr[] = { 3,13,23,4,5,14,7,13 };
		for (auto e : arr)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Print();
		ht.Erase(13);
		ht.Print();
		ht.Insert(make_pair(33, 33));
		ht.Print();
	}
	void test02()
	{
		string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
		HashTable<string, int> ht;
		for (auto e : arr)
		{
			HashDate<string, int>* ret = ht.Find(e);
			if (ret)
				ret->_kv.second++;
			else
				ht.Insert(make_pair(e, 1));
		}
		ht.Print();
	}
}

namespace kky_hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T,Ref, Ptr, KeyOfT, Hash> Self;
		typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		const HashTable<K, T, KeyOfT, Hash>* _pht;
		Node* _node;
		size_t _hashi;
		__HTIterator(Node* node,const HashTable<K, T, KeyOfT, Hash>* pht,size_t hashi)
			:_node(node)
			,_pht(pht)
			,_hashi(hashi)
		{}
		__HTIterator(const iterator& it)
			:_node(it._node)
			,_pht(it._pht)
			,_hashi(it._hashi)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				while (++_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
				}
				if (_hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}

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

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

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}
	};

	template<class K, class T,class KeyOfT, class Hash>
	class HashTable
	{
		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> const_iterator;
		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if(_tables[i])
				{
					return iterator(_tables[i], this, i);
				}
			}
			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this, -1);
		}

		const_iterator begin() const
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}
			return end();
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this, -1);
		}

		HashTable()
			:_n(0)
		{
			_tables.resize(10);
		}
		HashTable(const HashTable<K, T,KeyOfT, Hash>& ht)
		{
			_tables.resize(ht._tables.size(), nullptr);
			for (size_t i = 0; i < ht._tables.size(); i++)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* newnode = new Node(cur->_kv);
					if (_tables[i] == nullptr)
					{
						_tables[i] = newnode;
					}
					else
					{
						newnode->_next = _tables[i];
						_tables[i] = newnode;
					}
					cur = cur->_next;
				}
			}
		}

		HashTable<K, T,KeyOfT,Hash>& operator=(HashTable<K, T, KeyOfT, Hash> ht)
		{
			_tables.swap(ht._tables);
			swap(_n, ht._n);
			return *this;
		}

		~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)
		{
			Hash hs;
			KeyOfT koft;
			iterator it = Find(koft(data));
			if (it._node)
				return make_pair(it, false);
			if (_n == _tables.size())
			{
				vector<Node*> newtables;
				newtables.resize(_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(koft(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					//置空，防止析构出现问题
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}
			size_t hashi = hs(koft(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode, this, hashi), true);
		}

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

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;

					return true;
				}

				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				cout << "[" << i << "]" << "挂载" << "->";
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				cout << endl;
			}
			cout << endl;
		}

		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			double averageBucketLen = 0;

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}


				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)bucketSize / (double)_n;

			printf("all bucketSize:%d\n", _tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}

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

MyUnorderedSet.h

#pragma once
#include"HashTable.h"

namespace kky
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename kky_hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
		typedef typename kky_hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

		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);
		}
	private:
		kky_hash_bucket::HashTable<K, K, SetKeyOfT, Hash> ht;
	};
	void set_test01()
	{
		unordered_set<int> s;
		s.Insert(1);
		s.Insert(555);
		s.Insert(55);
		s.Insert(5);
		unordered_set<int>::iterator it = s.begin();
		while (it != s.end()) 
		{
			cout << *it << endl;
			++it;
		}
	}
}

?MyUnorderedMap.h

#pragma once
#include"HashTable.h"

namespace kky
{
	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 kky_hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
		typedef typename kky_hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::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<K,V>& kv)
		{
			return ht.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = ht.Insert(make_pair(key, V()));
			return ret.first.operator->()->second;
		}

	private:
		kky_hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> ht;
	};
	void map_test01()
	{
		unordered_map<string, string> dict;
		dict.Insert(make_pair("sort", "排序"));
		dict.Insert(make_pair("left", "左边"));
		dict.Insert(make_pair("right", "右边"));
		unordered_map<string, string>::const_iterator it = dict.begin();
		while (it != dict.end())
		{
			/*it->second = "test";*/
			cout << it->first<<":"<<it->second << endl;
			++it;
		}
	}
	void map_test02()
	{
		string arr[] = { "香蕉", "苹果","苹果", "苹果", "香蕉", "梨子", "香蕉", "梨子", "草莓", "梨子", "苹果", "苹果", "苹果" };
		unordered_map<string, int> count_map;
		for (auto& e : arr)
		{
			count_map[e]++;
		}

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

test.cpp

#include<iostream>
#include<string>
#include<set>
#include<unordered_set>
using namespace std;
#include"HashTable.h"
#include"MyUnorderedMap.h"
#include"MyUnorderedSet.h"
int main()
{
	kky::set_test01();
	kky::map_test02();
}

?谢谢大家观看！！！！！

文章来源:https://blog.csdn.net/kkbca/article/details/135090556
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！