当前位置：首页 > article >正文

【高阶数据结构】哈希表封装unordered_map、unordered_set

article 2025/1/6 20:49:03

哈希表封装unordered_map、unordered_set

1.源码及框架分析
2.模拟实现unordered_map和unordered_set
- 1.支持 insert 的实现
- 2.支持 iterator 的实现
- 3.unordered_map支持 operator [] 的实现
3.总代码
- 1.HashTable.h
- 2.UnorderedMap.h
- 3.UnorderedSet.h
- 4.Test.cpp

1.源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，容器的名字是hash_map和hash_set，它是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中。hash_map和hash_set的实现结构框架核心部分截取出来如下：

// stl_hash_set
template <class Value, class HashFcn = hash<Value>,
	class EqualKey = equal_to<Value>,
	class Alloc = alloc>
class hash_set
{
private:
	typedef hashtable<Value, Value, HashFcn, identity<Value>,
		EqualKey, Alloc> ht;
	ht rep;
public:
	typedef typename ht::key_type key_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;

	typedef typename ht::const_iterator iterator;
	typedef typename ht::const_iterator const_iterator;
	hasher hash_funct() const { return rep.hash_funct(); }
	key_equal key_eq() const { return rep.key_eq(); }
};

// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,
	class EqualKey = equal_to<Key>,
	class Alloc = alloc>
class hash_map
{
private:
	typedef hashtable<pair<const Key, T>, Key, HashFcn,
		select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
	ht rep;
public:
	typedef typename ht::key_type key_type;
	typedef T data_type;
	typedef T mapped_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;
	typedef typename ht::iterator iterator;
	typedef typename ht::const_iterator const_iterator;
};

// stl_hashtable.h
template <class Value, class Key, class HashFcn,
	class ExtractKey, class EqualKey,
	class Alloc>
class hashtable {
public:
	typedef Key key_type;
	typedef Value value_type;
	typedef HashFcn hasher;
	typedef EqualKey key_equal;
private:
	hasher hash;
	key_equal equals;
	ExtractKey get_key;
	typedef __hashtable_node<Value> node;

	vector<node*, Alloc> buckets;
	size_type num_elements;
public:
	typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
		Alloc> iterator;
	pair<iterator, bool> insert_unique(const value_type& obj);
	const_iterator find(const key_type& key) const;
};

template <class Value>
struct __hashtable_node
{
	__hashtable_node* next;
	Value val;
};

通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复用同一个hashtable实现key和key/value结构，hash_set传给hash_table的是两个key，hash_map传给hash_table的是pair<const key，value>
需要注意的是源码里面跟map/set源码类似，命名风格比较乱，这里比map和set还乱，hash_set模板参数居然用的Value命名，hash_map用的是Key和T命名。下面我们模拟一份自己的出来，就按自己的风格走了。

2.模拟实现unordered_map和unordered_set

1.支持 insert 的实现

参考源码框架，unordered_map和unordered_set复用之前我们实现的哈希表。
这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型使用T。
其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K，还是pair<K，V>，那么insert内部进行插入时要用K对象转换成整形取模和K比较相等，因为pair的value不参与计算取模，且默认支持的是key和value一起比较相等，我们需要时的任何时候只需要比较K对象，所以我们在unordered_map和unordered_set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K比较相等，具体细节参考如下代码实现。

//HashTable.h
namespace 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
	{
		typedef HashNode<T> Node;

	public:
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			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
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			//lower_bound：大于等于
			//upper_bound：大于

			return pos == last ? *(last - 1) : *pos;
		}
		
		HashTable()
			:_tables(__stl_next_prime(0))
			, _n(0)
		{}

		bool Insert(const T& data)
		{
			KeyOfT kot;
			Hash hash;

			//若存在，插入失败
			if (Find(kot(data)))
				return false;

			//负载因子==1时：扩容
			if (_n == _tables.size())
			{
				vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
				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)) % newTable.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTable);
			}
			
			size_t hashi = hash(kot(data)) % _tables.size();

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return true;
		}

	private:
		vector<Node*> _tables; //指针数组
		size_t _n;             //表中存储数据个数
	};
}

//UnorderedSet.h
namespace xzy
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		bool Insert(const K& key)
		{
			return _ht.Insert(key);
		}
		
	private:
		hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
	};
}

//UnorderedMap.h
namespace xzy
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		bool Insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};
}

2.支持 iterator 的实现

iterator核心源代码

template <class Value, class Key, class HashFcn,
	class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
	typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
		hashtable;
	typedef __hashtable_iterator<Value, Key, HashFcn,
		ExtractKey, EqualKey, Alloc>
		iterator;
	typedef __hashtable_const_iterator<Value, Key, HashFcn,
		ExtractKey, EqualKey, Alloc>
		const_iterator;
	typedef __hashtable_node<Value> node;
	typedef forward_iterator_tag iterator_category;
	typedef Value value_type;
	node* cur;
	hashtable* ht;
	__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
	__hashtable_iterator() {}
	reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
	pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
	iterator& operator++();
	iterator operator++(int);
	bool operator==(const iterator& it) const { return cur == it.cur; }
	bool operator!=(const iterator& it) const { return cur != it.cur; }
};

template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
	const node* old = cur;
	cur = cur->next;
	if (!cur) {
		size_type bucket = ht->bkt_num(old->val);
		while (!cur && ++bucket < ht->buckets.size())
			cur = ht->buckets[bucket];
	}
	return *this;
}

iterator实现思路分析：

iterator实现的大框架跟list的iterator思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
这里的难点是operator++的实现。iterator中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点反而是结构设计的问题，参考上面的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用key值计算出当前桶位置，依次往后找下一个不为空的桶即可。
begin()返回第一个桶中第一个节点指针构造的迭代器，这⾥end()返回迭代器可以用空表示。
unordered_set的iterator不支持修改key，我们把unordered_set的第⼆个模板参数改成const K即可， HashTable<K，const K，SetKeyOfT，Hash> _ht;
unordered_map的iterator不支持修改key，但是可以修改value，我们把unordered_map的第二个模板参数pair的第一个参数改成const K即可， HashTable<K，pair<const K，V>，MapKeyOfT，Hash> _ht;
支持完整的迭代器还有很多细节需要修改，具体参考下面的代码。

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//前置声明：解决 HTIterator 与 HashTable 互相依赖的问题
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	class HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
		typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	public:
		HTIterator(Node* node, const HT* ht) //注意：构造const迭代器时，const权限问题，可以缩小，不能放大
			:_node(node)
			, _ht(ht)
		{}

		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())
				{
					_node = _ht->_tables[hashi];

					if (_node)
						break; 
					else 
						hashi++; 
				}

				//所有的桶都走完了，当前迭代器就是end()，也就是_node等于nullptr
				if (hashi == _ht->_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;
		}

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

	private:
		Node* _node;
		const HT* _ht;
	};

	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 class 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++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return { cur, this };
				}
			}
			return End();
		}

		Iterator End()
		{
			return { nullptr, this };
		}

		ConstIterator Begin() const
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return { cur, this };
				}
			}
			return End();
		}

		ConstIterator End() const
		{
			return { nullptr, this };
		}

		HashTable()
			:_tables(__stl_next_prime(0))
			, _n(0)
		{}

	private:
		vector<Node*> _tables; //指针数组
		size_t _n;             //表中存储数据个数
	};
}

//UnorderedSet.h
namespace xzy
{
	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.End();
		}

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

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

	private:
		hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
	};
};

//UnorderedMap.h
namespace xzy
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				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();
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};
}

3.unordered_map支持 operator [] 的实现

unordered_map要支持 operator [] 主要需要修改insert返回值，修改HashTable中的insert返回值为pair<Iterator, bool> Insert(const T& data)
有了 insert 支持 operator [] 实现就很简单了，具体参考下面代码实现。

//HashTable.h
Iterator Find(const K& key)
{
	KeyOfT kot;
	Hash hash;

	size_t hashi = hash(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			return Iterator(cur, this);
		}
		cur = cur->_next;
	}
	return End();
}

pair<Iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	Hash hash;

	Iterator it = Find(kot(data));

	//若存在，插入失败
	if (it != End())
		return { it, false };

	//负载因子==1时：扩容
	if (_n == _tables.size())
	{
		vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
		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)) % newTable.size();
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newTable);
	}
			
	size_t hashi = hash(kot(data)) % _tables.size();

	//头插
	Node* newnode = new Node(data);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return { Iterator(newnode, this), true };
}

//UnorderedMap.h
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
	return _ht.Insert(kv);
}

V& operator[](const K& key)
{
	pair<iterator, bool> ret = Insert({ key, V() });

	//return ret.first.operator->()->second;
	return ret.first->second;
}

3.总代码

1.HashTable.h

#pragma once

#include<iostream>
#include<vector>
#include<string>
using namespace std;

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

struct StringHashFunc
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& ch : s)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};

//string较为常用，可以进行特化
template<>
struct HashFunc<string>
{
	//字符串转换成整形，可以把字符ASCII码相加即可 
	//但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 
	//这里我们使用BKDR哈希的思路，用上次的计算结果去乘一个质数，这个质数一般取31, 131等效果会比较好
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& ch : s)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//前置声明：解决 HTIterator 与 HashTable 互相依赖的问题
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	class HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
		typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	public:
		HTIterator(Node* node, const HT* ht) //注意：构造const迭代器时，const权限问题，可以缩小，不能放大
			:_node(node)
			, _ht(ht)
		{}

		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())
				{
					_node = _ht->_tables[hashi];

					if (_node)
						break;
					else
						hashi++;
				}

				//所有的桶都走完了，当前迭代器就是end()，也就是_node等于nullptr
				if (hashi == _ht->_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;
		}

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

	private:
		Node* _node;
		const HT* _ht;
	};

	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 class 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++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return { cur, this };
				}
			}
			return End();
		}

		Iterator End()
		{
			return { nullptr, this };
		}

		ConstIterator Begin() const
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return { cur, this };
				}
			}
			return End();
		}

		ConstIterator End() const
		{
			return { nullptr, this };
		}

		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			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
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			//lower_bound：大于等于
			//upper_bound：大于

			return pos == last ? *(last - 1) : *pos;
		}

		HashTable()
			:_tables(__stl_next_prime(0))
			, _n(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;
			}
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hash;

			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur, this);
				}
				cur = cur->_next;
			}
			return End();
		}

		pair<Iterator, bool> Insert(const T& data)
		{
			KeyOfT kot;
			Hash hash;

			Iterator it = Find(kot(data));

			//若存在，插入失败
			if (it != End())
				return { it, false };

			//负载因子==1时：扩容
			if (_n == _tables.size())
			{
				vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
				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)) % newTable.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTable);
			}
			
			size_t hashi = hash(kot(data)) % _tables.size();

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return { Iterator(newnode, this), true };
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hash;

			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						//删除头节点
						_tables[hashi] = cur->_next;
					}
					else
					{
						//删除中间节点
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

	private:
		vector<Node*> _tables; //指针数组
		size_t _n;             //表中存储数据个数
	};
}

2.UnorderedMap.h

#pragma once

#include"HashTable.h"

namespace xzy
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				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();
		}

		iterator Find(const K& key)
		{
			return _ht.Find(key);
		}

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

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = Insert({ key, V() });

			//return ret.first.operator->()->second;
			return ret.first->second;
		}

		bool Erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};
}

3.UnorderedSet.h

#pragma once

#include"HashTable.h"

namespace xzy
{
	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.End();
		}

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

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

		iterator Find(const K& key)
		{
			return _ht.Find(key);
		}

		pair<iterator, bool> Insert(const K& key)
		{
			return _ht.Insert(key);
		}

		bool Erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
	};
}

4.Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include"UnorderedSet.h"
#include"UnorderedMap.h"

void test_set()
{
	int a[] = { 5,6,8,9,7,4,2,3,1 };
	xzy::unordered_set<int> s;
	for (auto e : a)
	{
		s.Insert(e);
	}

	xzy::unordered_set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//*it = 1; Key不支持修改
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

	xzy::unordered_set<int>::const_iterator cit = s.begin();
	while (cit != s.end())
	{
		//*cit = 1; Key不支持修改
		cout << *cit << " ";
		++cit;
	}
	cout << endl;

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

void test_map()
{
	xzy::unordered_map<string, string> dict;
	dict.Insert({ "sort", "排序" });
	dict.Insert({ "字符串", "string" });

	dict.Insert({ "sort", "排序" });
	dict.Insert({ "left", "左边" });
	dict.Insert({ "right", "右边" });

	dict["left"] = "左边，剩余";
	dict["insert"] = "插入";
	dict["string"];

	xzy::unordered_map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//it->first += 'x';  map中的Key不能被修改
		//it->second += 'x'; map中的Value能被修改

		//cout << it.operator->()->first << ":" << it.operator->()->second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

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

int main()
{
	test_set();
	test_map();

	return 0;
}