unordered_map和unordered_set的源码模拟实现_unorderedmap实现源码

在源码中，这两个STL容器都是共用一个框架的所以，我们就用一个框架实现两个

容器，代码细节都在注释上

HashTable.h

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <utility>
//namespace txh
//{
//	enum state
//	{
//		EMPTY,//空
//		EXITS,//存在
//		DELETE,//被删除
//	};
//	template<class K,class V>//元素类
//	class HashData//先画一个存放数据的蓝图，声明和定义
//	{
//	public:
//		 std::pair<K,V> _kv;//哈希表，我们要根据key(也是模板的K)值去模一个值，得到哈希值存到哈希表的位置
//		 //V是数据类型
//
//		 //我们在查找的时候不知道用什么表示为空，没有一个合适的数，0吗，-1，不对，因为这些都有可能是某个数0，-1
//		 //所以不能用，我们用另一种方法，那就是在每个数据上存一个标志代表是否为空
//
//		 //前面定义了enum类型，类名是state，
//		 state _state = EMPTY;//默认都是空
//	};
//
//
//
//	//线性探测法
//	template<class K,class V,class keyConv>
//	class HashTable
//	{
//	public:
//		typedef HashData<K, V> data;
//		keyConv kc;
//		HashTable()
//			:_n(0)
//		{
//			_table.resize(11);
//		}
//
//		//那如果key值不是int而是string 类型呢,我们不可能去特意在模板里判断一个数是否是string类型
//		//那么我们可以传一个模板,因为我们hash主要的是要把key值转换成hash值
//		//我们用一个模板类去封装转换成hash值的方式
//		bool insert(const std::pair<K,V>& kv)//插入元素,我们用pair类接受
//		{
//			//如果表内有相同的值的话，就不插入了
//			if (find(kv.first))
//			{
//				return false;
//			}
//
//			if (_n * 10 / _table.size() > 7)//负载因子大于0.7我们的冲突就会变大，导致效率下降
//				//在线性探测中，所以我们就需要扩容，扩多少倍呢，扩质数倍其实是很好的，java中只是扩2倍，没有按质数扩
//				//按质数扩会降低哈希冲突率
//			{
//				HashTable<K, V,keyConv> newtable;
//				newtable._table.resize(2 * _table.size());
//
//				for (auto& e:_table)//为什么要重新插入，是因为我们扩容之后，下标映射变了，所以要重新插入
//				{
//					if(e._state == EXITS)
//					{
//					  /* int hashi = e._kv.first % newtable._table.size();
//					   newtable._table[hashi]._kv = e._kv;
//					   newtable._table[hashi]._state = e._state;*/
//						newtable.insert(e._kv);//复用写法
//					}
//				}
//				_table.swap(newtable._table);//2023年的现代写法,新表代替了旧表
//			}
//
//
//			//线性探测
//			size_t hashi = kc(kv.first) % _table.size(); //成员里不用capacity的原因是我们的vector的下标引用只能引用size内的值，capacity
//				//肯定大于等于size,所以肯定不能去模除capacity
//			size_t i = 0;
//			while (_table[hashi]._state != EMPTY)//查看当前表的每个元素类是否有空,没空一直继续
//			{
//				//如果当前的hashi被占了，直接去下一个厕所看(就是相邻的下一个)，所以有了i
//				//i控制每一轮要看的厕所不是上一次看过的，所以i++
//				++hashi;
//				hashi %= _table.size();//防止越界
//			}
//			_table[hashi]._kv = kv;
//			_table[hashi]._state = EXITS;
//			++_n;
//			return true;
//		}
//
//		data* find(const K& key)
//		{
//			size_t hashi = kc(key) % _table.size();
//			size_t i = 0;
//			while (_table[hashi]._state != EMPTY)//这是线性探测
//			{
//				if (_table[hashi]._kv.first == key
//					&& _table[hashi]._state == EXITS)
//				{
//					return &_table[hashi];
//				}
//				hashi++;
//				hashi %= _table.size();//防止越界
//			}
//		
//			return nullptr;
//		}
//
//		bool erase(const K& key)
//		{
//			data* ret = find(key);
//			if (!ret)
//			{
//				return false;
//			}
//			else
//			{
//				ret->_state = DELETE;
//				_n--;
//				return true;
//			}
//		}
//	private:
//		std::vector<data> _table;//当前存放元素的表,
//		size_t _n;//代表当前表内有多少个元素
//		//负载因子是什么呢，就是总共插入的元素 除以 总元素 就是负载因子
//	};
//}
//
template <typename T>
struct HashFunc
{
	size_t operator()(const T& key)//键值接受
	{
		size_t hashi = key;
		return hashi;
	}
};//声明键值转换函数是模板类,因为模板类只是个图纸
 
 
template <>//特化之前一定要有一个基础类
struct HashFunc<std::string>
{
	size_t operator()(const std::string& key)
	{
		size_t hashi = 0;
		for (auto e : key)//关键值转hash
		{
			hashi *= 131;
			hashi += e;
		}
		return hashi;
	}
};
namespace HashBucket
{
 
	//开散列，拉链法
	template<class T>//改造后只有一个参数，我们自动去识别是一个参数还是两个参数
	struct HashNode
	{
		HashNode(const T& data) :_data(data), next(nullptr) {}
		T _data;
		HashNode* next;
	};
	template<class K, class T, class keyCon, class KeyofT>
	class HashTable;//在hashIterator类前面声明,编译器就会跟着这个声明去找到相应的模板
	//容器都有迭代器,所以我们要封装一个迭代器，因为我们的迭代器会有重载*，->这种，所以我们直接传ptr这种吧
 
	template<class K,class T,class Ref,class Ptr,class keyCon,class KeyofT>
	class _HashIterator
	{
	public:
		typedef HashNode<T> node;
		typedef _HashIterator<K, T, T&, T*, keyCon, KeyofT> iterator;
		typedef HashTable<K, T, keyCon, KeyofT> HT;
 
 
		_HashIterator(node* node1,HT* ht) :_node(node1),_ht(ht){}
		_HashIterator(const iterator& it):_node(it._node),_ht(it._ht){}
		typedef _HashIterator<K,T,Ref,Ptr,keyCon,KeyofT> self;
 
		self& operator++()
		{
			//先看当前桶里是否有元素，如果后续有元素，那就在桶里++，如果桶里没有，那么就去其他桶
			//里找
			node* cur = _node->next;
			if (cur)
			{
				_node = _node->next;
				//返回迭代器本身
			}
			else
			{
				//去遍历这个桶，找到后续第一个有元素的桶
				keyCon kc;
				//找到当前迭代器里的节点的桶的位置
				size_t hashi = kc(_node->_data) % _ht->_table.size();
 
				//遍历这个桶
				++hashi;
				while (hashi < _ht->_table.size())
				{
					if (_ht->_table[hashi])
					{
						_node = _ht->_table[hashi];
						break;
					}
					hashi++;
				}
				if (hashi == _ht->_table.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
 
		self operator++(int)
		{
			//后置++
			self ret = self(_node,_ht);
			node* cur = _node;
			if (cur)
			{
				_node = _node->next;
				//返回迭代器本身
			}
			else
			{
				//去遍历这个桶，找到后续第一个有元素的桶
				keyCon kc;
				//找到当前迭代器里的节点的桶的位置
				size_t hashi = kc(_node->_data) % _ht->_table.size();
 
				//遍历这个桶
				++hashi;
				while (hashi < _ht->_table.size())
				{
					if (_ht->_table[hashi])
					{
						_node = _ht->_table[hashi];
						break;
					}
					hashi++;
				}
				if (hashi == _ht->_table.size())
				{
					_node = nullptr;
				}
			}
			return ret;//返回迭代器对象的时候，会进行拷贝构造，所以不用担心生命周期
		}
 
		bool operator!=(const self& s)
		{
			return s._node != _node;
		}
 
		Ref operator*()
		{
			return _node->_data;
		}
 
		Ptr& operator->()
		{
			return &_node->_data;
		}
	public:
		node* _node;//有了迭代器，我们就可以直接用迭代器,迭代器++，就是这里的_node = _node->next等
		//我们的++，--操作还会设计到遍历桶，我们的遍历桶只在HashTable里面设计了,所以我们需要有一个
		//可以操作HashTable的动作，因为都是算类，我们可以设计一个指针进行操作,我们用友元
		HT* _ht;
	};
 
	//第二个才是数，第一个只是我们的键值
	template<class K, class T, class keyCon,class KeyofT>
	class HashTable
	{
	public:
 
		//友元声明
		template<class K,class T,class Ref,class Ptr,class KeyCon, class KeyofT>//声明这个_hashIterator是个模板类，告诉编译器我要这个_HashIterator模板类
		//是HashTable类的友元
		friend class _HashIterator;
 
 
		typedef _HashIterator<K,T,T&,T*,keyCon,KeyofT> iterator;
		typedef _HashIterator<K, T,const T&,const T*,keyCon,KeyofT> const_iterator;
		//我们通过传的模板参数来控制我们的迭代器是否是const迭代器
 
		typedef HashNode<T> node;
		keyCon hash;
		KeyofT koft;
		size_t _stl_next_prime(size_t size)
		{
			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] > size)
				{
					return  __stl_prime_list[i];
				}
			}
		}
		HashTable() :_n(0)
		{
			_table.resize(_stl_next_prime(_table.size()));
		}
 
		~HashTable()
		{
			for (auto e : _table)
			{
				node* cur = e;
				while (cur)//把在桶里的元素删除
				{
					node* next = cur->next;
					delete cur;
					cur = next;
				}
				e = nullptr;
			}
		}
 
		iterator begin()
		{	 
			node* cur = nullptr;
			//找到第一个有元素的桶
			for (size_t hashi = 0;hashi < _table.size();hashi++)
			{
				cur = _table[hashi];
				if (cur)
				{
					break;
				}
			}
			return iterator(cur,this);//传值返回,生命周期就不用管，他会执行一次拷贝构造
			//匿名构造函数
		}
 
		iterator end()
		{
			return iterator(nullptr, this);//传值返回,生命周期就不用管，他会执行一次拷贝构造
		}
 
		const_iterator begin() const
		{
			node* cur = nullptr;
			for (size_t i = 0; i < _table.size(); ++i)
			{
				cur = _table[i];
				if (cur)
				{
					break;
				}
			}
 
			return const_iterator(cur, this);
		}
 
		const_iterator end() const{return const_iterator(nullptr, this);}
 
		std::pair<iterator,bool> insert(const T& data)
		{
			iterator ret = find(koft(data));
			if (ret != end())//有该点的话
			{
				return std::make_pair(ret, true);
			}
			//拉链法中，当负载因子等于1的时候，哈希的冲突就会变大，桶里的元素可能最多，所以负载因子为1就扩容最好
			if (_n == _table.size())//负载因子等于1
			{
				/*HashTable<K, V, keyCon> newHash;*/
				/*newHash._table.resize(_table.size() * 2);*/
				//这种做法很费效率，因为每次插入要重新new一个节点，并释放，所以同样映射的节点就不需要重新new了
				std::vector<node*> newtable;
				/*newtable.resize(_table.size() * 2,nullptr);*/
				//扩容
				newtable.resize(_stl_next_prime(_table.size()));
				//重新映射
				for (auto& e : _table)
				{
					node* cur = e;
					//头插
					while (cur)
					{
						node* next = cur->next;
 
						//哈希重新映射
						size_t hashi = hash(koft(cur->_data)) % newtable.size();
						cur->next = newtable[hashi];//将未插入之前的头插到cur的next
						newtable[hashi] = cur;
						cur = next;
					}
					e = nullptr;
				}
				//现代写法
				_table.swap(newtable);//旧表换新表,只是表新表的内容搬到旧表中
				//新表不用手动释放,生命周期只在当前作用域中，如果出了作用域会自动销毁(调用析构函数)
			}
 
			//这里的kc是实例化后的对象，所以可以kc(kv.first)，但是不能用hash(kv.first)，因为hash不是一个实例化的对象，需要把他实例化
			//之后才能调用
			size_t hashi = hash(koft(data)) % _table.size();
 
			//头插
			node* newnode = new node(data);
			newnode->next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return std::make_pair(iterator(newnode,this),true);
		}
 
		iterator find(const K& key)
		{
			size_t hashi = hash(key) % _table.size();//根据关键值算出哈希值
			node* cur = _table[hashi];
 
			//在桶里寻找
			while (cur)
			{
				if (koft(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				cur = cur->next;
			}
			return iterator(nullptr,this);
		}
 
		bool erase(const K& key)
		{
			size_t hashi = hash(key) % _table.size();
			node* cur = _table[hashi];//找到了桶
			node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//如果是头节点的话
					if (cur->_kv == _table[hashi])
					{
						_table[hashi] = cur->next;
					}
					else//找到的这个key值不是头结点的话
					{
						prev->next = cur->next;
					}
					delete cur;
					--_n;
					return true;
				}
				else//继续找
				{
					prev = cur;
					cur = cur->next;
				}
			}
			return false;
		}
	private:
		std::vector<node*> _table;//每个位置存放hashnode类，里面有指针,存放的是头结点
		size_t _n;
	};
}
//先改造哈希表
 
 
//int main()
//{
//
//	/*txh::HashTable<int,int,> h1;*/
//
//	//h1.insert(std::make_pair(4,1));
//	//h1.insert(std::make_pair(4,1));
//	//h1.insert(std::make_pair(4,1));
//	//h1.insert(std::make_pair(3,1));
//
//	//h1.insert(std::make_pair(7,1));
//
//	/*txh::HashTable<std::string, int,HashFunc<std::string>> h1;
//	h1.insert(std::make_pair("苹果", 1));
//	h1.insert(std::make_pair("香蕉", 1));
//	h1.insert(std::make_pair("梨", 1));
//	h1.insert(std::make_pair("苹果", 1));
//	txh::HashData<std::string, int>* ret = h1.find("苹果");
//	ret->_kv.second++;
//	h1.erase("苹果");*/
//
//	HashBucket::HashTable<int, int, HashFunc<int>> h1;
//
//	h1.insert(std::make_pair(3, 1));
//	h1.insert(std::make_pair(4, 1));
//	h1.insert(std::make_pair(3, 1));
//	h1.insert(std::make_pair(3, 1));
//	h1.insert(std::make_pair(12, 1));
//	h1.insert(std::make_pair(12, 1));
//	return 0;
//}
template<class T>
struct compare
{
	bool operator()(const T& t1,const T& t2)
	{
		return t1 > t2;
	}
};

unordered_map.h

#pragma once
#include "HashTable.h"
#include "unordered_map.h"
#include "unordered_set.h"
#include <iostream>
namespace txh
{
	template<class K,class T,class keyCon = HashFunc<K>>
	class unordered_map
	{
	public:
		struct mapkeyoft
		{
			const K& operator()(const std::pair<K,T>& kv)
			{
				return  kv.first;
			}
		};
		typedef typename HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft>::iterator iterator;
		typedef typename HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft>::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();
		}
 
		std::pair<iterator, bool> insert(const std::pair<K, T>& data)
		{
			return _ht.insert(data);
		}
 
		T& operator[](const K& key)
		{
			std::pair<iterator, bool> ret = insert(std::make_pair(key
				, T));
			return ret.first->second;
			//加->就是得到了data,然后second
		}
 
		iterator find(const K& key)
		{
			return _ht.find(key);
		}
 
		bool erase(const K& key)
		{
			_ht.erase(key);
		}
	private:
		HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft> _ht;
 
	};
}

unordered_set.h

#pragma once
#include "HashTable.h"
#include <iostream>
#include <utility>
namespace txh
{
	template<class K,class keyCon = HashFunc<K>>
	class unordered_set
	{
		struct keyofset
		{
			const K& operator()(const K& data)
			{
				return data;
			}
		};
 
	public:
		typedef typename HashBucket::HashTable<K, K, keyCon, keyofset>::const_iterator iterator;
		typedef typename HashBucket::HashTable<K, K, keyCon, keyofset>::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();
		}
 
		std::pair<iterator, bool> insert(const K& data) 
		{
			return _ht.insert(data);
		}
 
		iterator find(const K& data)
		{
			return _ht.find(data);
		}
 
		bool erase(const K& data)
		{
			return _ht.erase(data);
		}
	private:
		HashBucket::HashTable<K, K, keyCon, keyofset> _ht;
	};
}

test.cpp

#define  _CRT_SECURE_NO_WARNINGS 1
#include "unordered_map.h"
#include "unordered_set.h"
#include "HashTable.h"
#include <iostream>
#include <algorithm>
#include <utility>
int main()
{
	txh::unordered_set<int, HashFunc<int>> s1;
	s1.insert(1);
	return 0;
}