C++哈希表模拟实现unordered_map 与unordered_set

    enum Status//标记存储值的状态
	{
		EMPTY,//空
		EXIST,//存在
		DELETE//删除
	};

哈希表设计代码（开放定址法/闭散列解决哈希冲突）

#pragma once
#include<string>
#include<vector>
#include<iostream>
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 e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};
 
 
namespace open_address//开放定址法/闭散列
{
	enum Status//标记存储值的状态
	{
		EMPTY,//空
		EXIST,//存在
		DELETE//删除
	};
 
	template<class K,class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _s;//状态
	};
 
	template<class K,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			//检查是否已经存在
			if (Find(kv.first))
				return false;
			//检查是否需要扩容
			// 负载因子0.7就扩容
			if (_n * 10 / _tables.size() == 7)
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(newSize);
 
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
						newHT.Insert(_tables[i]._kv);
				}
 
				_tables.swap(newHT._tables);
			}
			//插入
 
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIST)
			{
				++hashi;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;
			return true;
		}
 
		HashData<K, V>* Find(const K& key)//若是一次性找不到，则一直找到空就结束
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			while (_tables[hashi]._s !=EMPTY)
			{
				if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}
 
		// 伪删除法
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}
 
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else
				{
					printf("[%d]->D\n", i);
				}
			}
			cout << endl;
		}
 
	private:
		vector<HashData<K,V>> _tables;
		size_t _n = 0;// 存储的关键字的个数
	};
}

哈希表的扩容问题：

负载因子：存储关键字个数/空间大小，当负载因子为0.7时就扩容

开散列（链地址法/开链法/拉链法)

哈希表（开散列解决哈希冲突）模拟实现unordered_map 与unordered_set

HashTable.h

#pragma once
#include<string>
#include<vector>
#include<iostream>
using namespace std;
 
template<class K>
struct  HashFunc  // 哈希函数采用除留余数法，被模的key必须要为整形才可以处理
{
	size_t operator()(const K& key)
	{
		 return (size_t)key;
	}
};
 
template<>
struct HashFunc<string>//将字符串映射成一个整型 （若key为字符串）
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};
 
 
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 Hash, class KeyOfT>
	class HashTable;
 
	template<class K, class T, class Ref,class Ptr,class Hash, class KeyOfT>
	struct __HTIterator
	{
		typedef  HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
		Node* _node;
		const HashTable<K, T, Hash, KeyOfT>* _pht;//权限可以平移/缩小，不能放大
		size_t _hashi;
 
		__HTIterator(Node*node, HashTable<K, T, Hash, KeyOfT>* pht, size_t hashi)
			:_node(node)
			,_pht(pht)
			,_hashi(hashi)
		{}
 
		//有普通的this( HashTable的this)指针与const修饰的this指针，走更适配的
		__HTIterator(Node* node, const HashTable<K, T, Hash, KeyOfT>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}
 
		Self& operator++()
		{
			if (_node->_next)//当前桶没走完,还有节点,走到下一个节点
			{
				_node = _node->_next;
			}
			else//当前桶已走完，找下一个桶的起始节点
			{
				++_hashi;
				while (_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
					++_hashi;
				}
 
				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;
		}
	};
 
	// unordered_set -> Hashtable<K, K>
	// unordered_map -> Hashtable<K, pair<K, V>>
	template<class K,class T,class Hash,class KeyOfT>
	class HashTable
	{
		typedef HashNode<T> Node;
 
		template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
		friend struct __HTIterator;
 
	public:
 
		typedef  __HTIterator<K, T, T&, T*, Hash, KeyOfT> iterator;
		typedef  __HTIterator<K, T, const T&, const T*, Hash, KeyOfT> 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()
		{
			_tables.resize(10);
		}
 
		~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 hf;//将关键字转成/映射成一个整型  （data可以为int，可以为string）
			KeyOfT kot;//取出data中的关键字，data若为Key则就是它本身，data若为pair，则取得pair的第一个元素
 
			iterator it = Find(kot(data));
			if (it != end())
				return make_pair(it, false);
			
 
			//检查是否需要扩容
			// 负载因子最大到1
			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 = hf(kot(cur->_data)) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}
 
 
			size_t hashi = hf(kot(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 hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this,hashi);
				}
				cur = cur->_next;
			}
			return end();
		}
 
		bool Erase(const K& key)
		{
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(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;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
 
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}

MyUnorderedMap.h

#pragma once
#include"HashTable.h"
 
namespace djx
{
	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>,  Hash, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
 
		iterator end()
		{
			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->second;
		}
 
		const V& operator[](const K& key) const
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return  ret.first->second;
		}
 
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
 
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		hash_bucket::HashTable<K, pair<const K, V>,  Hash, MapKeyOfT> _ht;
	};
}

#pragma once
#include"HashTable.h"
 
namespace djx
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		// 对类模板取内嵌类型，加typename告诉编译器这里是类型
		typedef typename hash_bucket::HashTable<K, K, Hash, SetKeyOfT>::const_iterator  iterator;
		typedef typename hash_bucket::HashTable<K, K, Hash, SetKeyOfT>::const_iterator  const_iterator;
 
		const_iterator begin() const
		{
			return _ht.begin();
		}
 
		const_iterator end() const
		{
			return _ht.end();
		}
 
		pair<const_iterator, bool> insert(const K& key)
		{
			auto ret = _ht.Insert(key);
			return make_pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
		}
		
		iterator find(const K& key)
		{
			auto ret = _ht.Find(key);
			return const_iterator(ret._node, ret._pht, ret._hashi);
		}
 
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
 
	private:
		hash_bucket::HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

void test_set()
{
	djx::unordered_set<int> us;
	us.insert(4);
	us.insert(19);
	us.insert(62);
	us.insert(3);
 
	djx::unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
 
	auto e = us.find(19);
	cout << *e << endl;
 
	us.erase(19);
	for (auto e : us)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_map()
{
	djx::unordered_map<string, string> dict;
	dict.insert(make_pair("sort", ""));
	dict.insert(make_pair("string", ""));
	dict.insert(make_pair("insert", ""));
	for (auto& kv : dict)
	{
		//kv.first += 'x';不可以修改K
		kv.second += 'x';
 
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;
 
	string arr[] = { "苹果","葡萄","葡萄","甜瓜"};
	djx::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;
 
	count_map.erase("苹果");
}