【C++】哈希表的模拟实现及 unordered_set 和 unorderded_map 的封装

前言

上一篇文章中讲到了哈希的概念和stl中关于哈希容器的使用，并且在后面对开散列进行了模拟实现，那么在这一篇文章中在开散列的基础上进行改造成哈希表，并且在哈希表的基础上封装 unordered_set 和 unordered_map。

一、哈希表的模拟实现

1.1 哈希表的改造

1.1.1 模板参数列表的改造

k：表示关键码类型

t：不同容器v的类型不同，如果是unordered_map，k代表一个键值对，如果是unordered_set，t 为 k。

koft： 因为v的类型不同，通过value取key的方式就不同，详细见
unordered_map/set的实现

hf: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将key转换为整形数字才能取模

template<class k, class t ,  class koft , class hf>
class hash_table;

1.1.2 增加迭代器操作

// 前置声明，否则后面的__htiterator找不到hash_table
	template<class k, class t, class koft, class hf>
	class hash_table;

	template<class k, class t , class ref, class ptr, class koft, class hf>
	struct __htiterator
	{
		typedef hashnode<t> node;
		typedef __htiterator<k, t, ref , ptr , koft, hf> self;

		// 成员变量
		node* _node;
		// 由于const迭代器中const修饰this
		// 所以这里需要加const，否则会导致权限放大
		// 编译无法通过的情况
		const hash_table<k, t, koft, hf>* _pht;
		// 
		size_t hashi;

		// 构造函数
		__htiterator(node* node, hash_table<k, t, koft, hf>* pht , size_t i)
			:_node(node)
			,_pht(pht)
			,hashi(i)
		{}

		// 构造函数
		__htiterator(node* node, const hash_table<k, t, koft, hf>* pht, size_t i)
			:_node(node)
			, _pht(pht)
			, hashi(i)
		{}

		self& operator++()
		{
			if (_node->_next)
			{
				// 若当前桶其他节点没有走完
				// 那么继续走下一个节点
				_node = _node->_next;
			}
			else
			{
				// 若当前桶的所有节点都已经走完
				// 那么继续向下一个桶不为空的桶走
				hashi++;
				while (hashi < _pht->_table.size())
				{
					if (_pht->_table[hashi])
					{
						_node = _pht->_table[hashi];
						break;

					}

					hashi++;
				}

				if (hashi == _pht->_table.size())
					_node = nullptr;
			}

			return *this;
		}

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

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

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

1.2 哈希表的模拟实现

1.2.1 哈希表中仿函数的实现

若存储key的类型不是整形时，需要将其转化为整数，整形不需要处理，日常中我们最常用到的类型是string，那么这里就写一个string转化为整形的版本。

// 整数类型
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 (size_t i = 0; i < s.size(); i++)
		{
			sum = sum * 31 + s[i];
		}
		return sum;
	}
};

1.2.2 哈希表中节点类的实现

namespace hash_bucket
{
	template<class t>
	struct hashnode
	{
		hashnode* _next;
		t _data;

		hashnode(const t& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

}

1.2.3 哈希表中迭代器类的实现

namespace hash_bucket
{
	// 前置声明，否则后面的__htiterator找不到hash_table
	template<class k, class t, class koft, class hf>
	class hash_table;

	template<class k, class t, class ref, class ptr, class koft, class hf>
	struct __htiterator
	{
		typedef hashnode<t> node;
		typedef __htiterator<k, t, ref, ptr, koft, hf> self;

		// 成员变量
		node* _node;
		// 由于const迭代器中const修饰this
		// 所以这里需要加const，否则会导致权限放大
		// 编译无法通过的情况
		const hash_table<k, t, koft, hf>* _pht;
		// 
		size_t hashi;

		// 构造函数
		__htiterator(node* node, hash_table<k, t, koft, hf>* pht, size_t i)
			:_node(node)
			, _pht(pht)
			, hashi(i)
		{}

		// 构造函数
		__htiterator(node* node, const hash_table<k, t, koft, hf>* pht, size_t i)
			:_node(node)
			, _pht(pht)
			, hashi(i)
		{}

		self& operator++()
		{
			if (_node->_next)
			{
				// 若当前桶其他节点没有走完
				// 那么继续走下一个节点
				_node = _node->_next;
			}
			else
			{
				// 若当前桶的所有节点都已经走完
				// 那么继续向下一个桶不为空的桶走
				hashi++;
				while (hashi < _pht->_table.size())
				{
					if (_pht->_table[hashi])
					{
						_node = _pht->_table[hashi];
						break;

					}

					hashi++;
				}

				if (hashi == _pht->_table.size())
					_node = nullptr;
			}

			return *this;
		}

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

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

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

1.2.4 哈希表中构造函数、析构函数和 clear() 函数的实现

namespace hash_bucket
{
	template<class k, class t, class koft, class hf>
	class hash_table
	{
	public:
		typedef hashnode<t> node;

	public:
		// 构造函数
		hash_table(int n = 10)
			:_table(vector<node*>(n))
			, _n(0)
		{}

		// 析构函数
		~hash_table()
		{
			clear();
		}

		void clear()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				node* cur = _table[i];

				while (cur)
				{
					node* next = cur->_next;
					delete cur;

					cur = next;
				}

				_table[i] = nullptr;
			}
		}

	private:
		vector<node*> _table;
		int _n;
	};
}

1.2.5 哈希表中swap 和 size 函数的实现

namespace hash_bucket
{
	template<class k, class t, class koft, class hf>
	class hash_table
	{
	public:

		size_t size()
		{
			return _n;
		}

		void swap(hash_table<k, t, koft, hf>& ht)
		{
			_table.swap(ht._table);
			swap(_n, ht._n);
		}

	private:
		vector<node*> _table;
		int _n;
	};
}

1.2.6 哈希表中 begin 和 end 函数的实现

namespace hash_bucket
{
	template<class k, class t, class koft, class hf>
	class hash_table
	{
	public:
		typedef hashnode<t> node;
		typedef __htiterator<k, t, t&, t*, koft, hf> iterator;
		typedef __htiterator<k, t, const t&, const t*, koft, hf> const_iterator;

		// 将__htiterator设置为hash_table的友元
		// 使__htiterator可以访问hash_table的私有
		template<class k, class t, class ref, class ptr, class koft, class hf>
		friend struct __htiterator;

	public:
		// 迭代器
		iterator begin()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i])
					return iterator(_table[i], this, i);
			}

			return end();
		}

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

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

			return end();
		}

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

	private:
		vector<node*> _table;
		int _n;
	};
}

1.2.7 哈希表中 find 函数的实现

namespace hash_bucket
{
	template<class k, class t, class koft, class hf>
	class hash_table
	{
	public:
		typedef hashnode<t> node;
		typedef __htiterator<k, t, t&, t*, koft, hf> iterator;
		typedef __htiterator<k, t, const t&, const t*, koft, hf> const_iterator;

		// 将__htiterator设置为hash_table的友元
		// 使__htiterator可以访问hash_table的私有
		template<class k, class t, class ref, class ptr, class koft, class hf>
		friend struct __htiterator;

	public:
		// 查找
		iterator find(const k& key)
		{
			hf hf;
			koft koft;
			int hashi = hf(key) % _table.size();
			node* cur = _table[hashi];
			while (cur)
			{
				if (koft(cur->_data) == key)
					return iterator(cur, this, hashi);

				cur = cur->_next;
			}

			// 找不到返回空
			return end();
		}

	private:
		vector<node*> _table;
		int _n;
	};
}

1.2.8 哈希表中 insert 和 erase 函数的实现

namespace hash_bucket
{
	template<class k, class t, class koft, class hf>
	class hash_table
	{
	public:
		typedef hashnode<t> node;
		typedef __htiterator<k, t, t&, t*, koft, hf> iterator;
		typedef __htiterator<k, t, const t&, const t*, koft, hf> const_iterator;

		// 将__htiterator设置为hash_table的友元
		// 使__htiterator可以访问hash_table的私有
		template<class k, class t, class ref, class ptr, class koft, class hf>
		friend struct __htiterator;

	public:
		// 插入
		pair<iterator, bool> insert(const t& data)
		{
			hf hf;
			koft koft;

			iterator tmp = find(koft(data));
			// 不允许有相同的值
			if (tmp != end())
				return make_pair(tmp, false);

			// 扩容
			if (_n == _table.size())
			{
				int newcapacity = 2 * _table.size();
				hash_table newtable(newcapacity);

				for (size_t i = 0; i < _table.size(); i++)
				{
					node* cur = _table[i];

					while (cur)
					{
						node* next = cur->_next;
						int hashi = hf(koft(cur->_data)) % newcapacity;

						cur->_next = newtable._table[hashi];
						newtable._table[hashi] = cur;
						cur = next;
					}

					_table[i] = nullptr;
				}
				_table.swap(newtable._table);
			}

			// 头插 
			int hashi = hf(koft(data)) % _table.size();
			node* newnode = new node(data);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;

			return make_pair(iterator(newnode, this, hashi), true);
		}

		// 删除
		bool erase(const k& key)
		{
			node* tmp = find(key);
			// 找不到则删除失败
			if (tmp == nullptr)
				return false;

			hf hf;
			koft koft;
			int hashi = hf(key) % _table.size();
			node* prev = nullptr;
			node* cur = _table[hashi];
			while (cur)
			{
				node* next = cur->_next;
				if (koft(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = next;
					}
					else
					{
						prev->_next = next;
					}

					_n--;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = next;
				}
			}

			return false;
		}

	private:
		vector<node*> _table;
		int _n;
	};
}

1.2.9 哈希表的整体实现

#pragma once

#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
#include<set>


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& s)
	{
		size_t sum = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			sum = sum * 31 + s[i];
		}
		return sum;
	}
};

namespace hash_bucket
{
	template<class t>
	struct hashnode
	{
		hashnode* _next;
		t _data;

		hashnode(const t& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	// 前置声明，否则后面的__htiterator找不到hash_table
	template<class k, class t, class koft, class hf>
	class hash_table;

	template<class k, class t , class ref, class ptr, class koft, class hf>
	struct __htiterator
	{
		typedef hashnode<t> node;
		typedef __htiterator<k, t, ref , ptr , koft, hf> self;

		// 成员变量
		node* _node;
		// 由于const迭代器中const修饰this
		// 所以这里需要加const，否则会导致权限放大
		// 编译无法通过的情况
		const hash_table<k, t, koft, hf>* _pht;
		// 
		size_t hashi;

		// 构造函数
		__htiterator(node* node, hash_table<k, t, koft, hf>* pht , size_t i)
			:_node(node)
			,_pht(pht)
			,hashi(i)
		{}

		// 构造函数
		__htiterator(node* node, const hash_table<k, t, koft, hf>* pht, size_t i)
			:_node(node)
			, _pht(pht)
			, hashi(i)
		{}

		self& operator++()
		{
			if (_node->_next)
			{
				// 若当前桶其他节点没有走完
				// 那么继续走下一个节点
				_node = _node->_next;
			}
			else
			{
				// 若当前桶的所有节点都已经走完
				// 那么继续向下一个桶不为空的桶走
				hashi++;
				while (hashi < _pht->_table.size())
				{
					if (_pht->_table[hashi])
					{
						_node = _pht->_table[hashi];
						break;

					}

					hashi++;
				}

				if (hashi == _pht->_table.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 koft , class hf>
	class hash_table
	{
	public:
		typedef hashnode<t> node;
		typedef __htiterator<k, t, t& , t* ,koft, hf> iterator;
		typedef __htiterator<k, t, const t&, const t*, koft, hf> const_iterator;

		// 将__htiterator设置为hash_table的友元
		// 使__htiterator可以访问hash_table的私有
		template<class k, class t, class ref, class ptr, class koft, class hf>
		friend struct __htiterator;

	public:
		// 构造函数
		hash_table(int n = 10)
			:_table(vector<node*>(n))
			,_n(0)
		{}

		// 析构函数
		~hash_table()
		{
			clear();
		}

		void clear()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				node* cur = _table[i];

				while (cur)
				{
					node* next = cur->_next;
					delete cur;

					cur = next;
				}

				_table[i] = nullptr;
			}
		}

		size_t size()
		{
			return _n;
		}

		void swap(hash_table<k,t,koft,hf>& ht)
		{
			_table.swap(ht._table);
			swap(_n, ht._n);
		}

		// 迭代器
		iterator begin()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i])
					return iterator(_table[i], this, i);
			}

			return end();
		}

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

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

			return end();
		}

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

		// 插入
		pair<iterator,bool> insert(const t& data)
		{
			hf hf;
			koft koft;

			iterator tmp = find(koft(data));
			// 不允许有相同的值
			if (tmp != end())
				return make_pair(tmp,false);

			// 扩容
			if (_n == _table.size())
			{
				int newcapacity = 2 * _table.size();
				hash_table newtable(newcapacity);

				for (size_t i = 0; i < _table.size(); i++)
				{
					node* cur = _table[i];

					while (cur)
					{
						node* next = cur->_next;
						int hashi = hf(koft(cur->_data)) % newcapacity;

						cur->_next = newtable._table[hashi];
						newtable._table[hashi] = cur;
						cur = next;
					}

					_table[i] = nullptr;
				}
				_table.swap(newtable._table);
			}

			// 头插 
			int hashi = hf(koft(data)) % _table.size();
 			node* newnode = new node(data);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;

			return make_pair(iterator(newnode,this,hashi),true);
		}

		// 删除
		bool erase(const k& key)
		{
			node* tmp = find(key);
			// 找不到则删除失败
			if (tmp == nullptr)
				return false;

			hf hf;
			koft koft;
			int hashi = hf(key) % _table.size();
			node* prev = nullptr;
			node* cur = _table[hashi];
			while (cur)
			{
				node* next = cur->_next;
				if (koft(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = next;
					}
					else
					{
						prev->_next = next;
					}

					_n--;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = next;
				}
			}

			return false;
		}

		// 查找
		iterator find(const k& key)
		{
			hf hf;
			koft koft;
			int hashi = hf(key) % _table.size();
			node* cur = _table[hashi];
			while (cur)
			{
				if (koft(cur->_data) == key)
					return iterator(cur,this,hashi);

				cur = cur->_next;
			}

			// 找不到返回空
			return end();
		}

		void some()
		{
			size_t bucketsize = 0;
			size_t maxbucketlen = 0;
			size_t sum = 0;
			double averagebucketlen = 0;

			for (size_t i = 0; i < _table.size(); i++)
			{
				node* cur = _table[i];
				if (cur)
				{
					++bucketsize;
				}

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

				sum += bucketlen;

				if (bucketlen > maxbucketlen)
				{
					maxbucketlen = bucketlen;
				}
			}

			averagebucketlen = (double)sum / (double)bucketsize;

			printf("all bucketsize:%d\n", _table.size());
			printf("bucketsize:%d\n", bucketsize);
			printf("maxbucketlen:%d\n", maxbucketlen);
			printf("averagebucketlen:%lf\n\n", averagebucketlen);
		}

	private:
		vector<node*> _table;
		int _n;

	public:
		void testht1()
		{
			hash_table<int, int> ht;
			int a[] = { 4,14,24,34,5,7,1 };
			for (auto e : a)
			{
				ht.insert(make_pair(e, e));
			}

			ht.insert(make_pair(3, 3));
			ht.insert(make_pair(3, 3));
			ht.insert(make_pair(-3, -3));

			ht.some();
		}

		void testht2()
		{
			string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
			//hashtable<string, int, hashfuncstring> ht;
			hash_table<string, int> ht;
			for (auto& e : arr)
			{
				//auto ret = ht.find(e);
				hashnode<string, int>* ret = ht.find(e);
				if (ret)
				{
					ret->_kv.second++;
				}
				else
				{
					ht.insert(make_pair(e, 1));
				}
			}

			ht.insert(make_pair("apple", 1));
			ht.insert(make_pair("sort", 1));

			ht.insert(make_pair("abc", 1));
			ht.insert(make_pair("acb", 1));
			ht.insert(make_pair("aad", 1));
		}

		void testht3()
		{
			const size_t n = 1000;

			unordered_set<int> us;
			set<int> s;
			hash_table<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 begin3 = clock();
			for (auto e : v)
			{
				ht.insert(make_pair(e, e));
			}
			size_t end3 = clock();
			cout << "hash_table insert:" << end3 - begin3 << endl << endl;


			size_t begin4 = clock();
			for (auto e : v)
			{
				s.find(e);
			}
			size_t end4 = clock();
			cout << "set find:" << end4 - begin4 << endl;

			size_t begin5 = clock();
			for (auto e : v)
			{
				us.find(e);
			}
			size_t end5 = clock();
			cout << "unordered_set find:" << end5 - begin5 << endl;

			size_t begin6 = clock();
			for (auto e : v)
			{
				ht.find(e);
			}
			size_t end6 = clock();
			cout << "hash_table find:" << end6 - begin6 << endl << endl;

			cout << "插入数据个数：" << us.size() << endl << endl;
			ht.some();

			size_t begin7 = clock();
			for (auto e : v)
			{
				s.erase(e);
			}
			size_t end7 = clock();
			cout << "set erase:" << end7 - begin7 << endl;

			size_t begin8 = clock();
			for (auto e : v)
			{
				us.erase(e);
			}
			size_t end8 = clock();
			cout << "unordered_set erase:" << end8 - begin8 << endl;

			size_t begin9 = clock();
			for (auto e : v)
			{
				ht.erase(e);
			}
			size_t end9 = clock();
			cout << "hash_table erase:" << end9 - begin9 << endl << endl;
		}
	};

}

二、unordered_set的实现及测试

#pragma once

#include"hashtable.h"

namespace aj
{
	template<class k>
	class unordered_set
	{
	public:
		struct setkeyoft
		{
			const k& operator()(const k& k)
			{
				return k;
			}
		};

	public:
		// 因为unordered_set中k是不能被改变
		// 所以普通迭代器也无法改变k的值
		// 所以让普通迭代器也是const迭代器
		typedef typename hash_bucket::hash_table<const k, k, setkeyoft, hashfunc<k>>::const_iterator iterator;
		typedef typename hash_bucket::hash_table<const k, k, setkeyoft, hashfunc<k>>::const_iterator const_iterator;

		// 由于_ht.insert(key)返回的普通迭代器
		// 而pair<iterator, bool>中的迭代器
		// 看起来是普通迭代器，但实际上是const迭代器
		// 所以这里不能直接 return _ht.insert(key)
		pair<iterator, bool> insert(const k& key)
		{
			auto tmp = _ht.insert(key);
			return make_pair(iterator(tmp.first._node, tmp.first._pht, tmp.first.hashi), tmp.second);
		}

		// 由于这里普通迭代器也是const迭代器
		// 那么这里只保留const迭代器版本
		/*iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}*/

		const_iterator begin()const
		{
			return _ht.begin();
		}

		const_iterator end()const
		{
			return _ht.end();
		}

		bool erase(const k& key)
		{
			return _ht.erase(key);
		}

		iterator find(const k& key)
		{
			return _ht.find(key);
		}

		void clear()
		{
			_ht.clear();
		}

		size_t size()
		{
			return _ht.size();
		}

		void swap(unordered_set<k>& us)
		{
			_ht.swap(us._ht);
		}
	private:
		// unordered_set中k是不能被改变的
		hash_bucket::hash_table <const k, k , setkeyoft , hashfunc<k>> _ht;
	};

	void test_unordered_set()
	{
		// 17:05
		/*unordered_set<int> us;
		us.insert(5);
		us.insert(15);
		us.insert(52);
		us.insert(3);*/

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

		unordered_set<int> us1;
		us1.insert(1);
		us1.insert(2);
		us1.insert(3);
		us1.insert(4);


		unordered_set<int> us2;
		us2.insert(10);
		us2.insert(20);
		us2.insert(30);
		us2.insert(40);
		for (auto e : us1)
		{
			cout << e << " ";
		}
		cout << endl;

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

		us1.swap(us2);

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

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

三、unordered_map的实现及测试

#pragma once

#include"hashtable.h"

namespace aj
{
	template<class k , class v>
	class unordered_map
	{
	public:
		struct mapkeyoft
		{
			const k& operator()(const pair<k, v>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::hash_table<k, pair<const k, v>, mapkeyoft, hashfunc<k>>::iterator iterator;
		typedef typename hash_bucket::hash_table<k, pair<const k, v>, mapkeyoft, hashfunc<k>>::const_iterator const_iterator;

		pair<iterator,bool> insert(const pair<k, v>& kv)
		{
			return _ht.insert(kv);
		}

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		const_iterator begin()const
		{
			return _ht.begin();
		}

		const_iterator end()const
		{
			return _ht.end();
		}

		v& operator[](const k& key)
		{
			auto tmp = _ht.insert(make_pair(key,v()));
			return tmp.first->second;
		}

		const v& operator[](const k& key)const
		{
			auto tmp = _ht.insert(make_pair(key, v()));
			return tmp.first->second;
		}

		bool erase(const k& key)
		{
			return _ht.erase(key);
		}

		iterator find(const k& key)
		{
			return _ht.find(key);
		}

		void clear()
		{
			_ht.clear();
		}

		size_t size()
		{
			return _ht.size();
		}

		void swap(unordered_map<k,v>& um)
		{
			_ht.swap(um._ht);
		}

	private:
		// unordered_map中k是不能被改变的
		hash_bucket::hash_table <k, pair<const k, v>, mapkeyoft , hashfunc<k>> _ht;
	};
	void test_unordered_map1()
	{
		unordered_map<int, int> um;
		um.insert(make_pair(1, 1));
		um.insert(make_pair(2, 2));
		um.insert(make_pair(3, 3));
		um.insert(make_pair(4, 4));

		unordered_map<int, int>::iterator it = um.begin();
		while (it != um.end())
		{
			cout << it->first << ' ' << it->second << endl;
			++it;
		}
	}

	void test_unordered_map2()
	{
		unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("insert", "插入"));
		dict.insert(make_pair("string", "字符串"));


		for (auto& kv : dict)
		{
			// kv.first += 'x';
			kv.second += 'x';

			cout << kv.first << ":" << kv.second << endl;
		}
		cout << endl;

		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;
	}
}

结尾

到目前已经将哈希的大部分内容讲述完了，那么下一篇文章将继续完善哈希，讲述位图和布隆过滤器。

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹