哈希

---

一、哈希的基本介绍

---

性能上

查找数据，哈希时间复杂度为O(1)
大量随机数据插入，map和set性能快
大量随机数据删除，map和set性能快

哈希映射方法

1.直接定址法:每个值都有自己唯一的位置
优点:无哈希冲突,简单且均匀
缺点:如果空间分散会有很大的空间浪费
适应于范围小且连续的情况

2,除留余数法
优点:空间合适且不浪费过多的空间
缺点:可能存在有相同的映射地址(哈希冲突)

哈希大部分都围绕着解决哈希冲突

1.闭散列:冲突后占用下一个空位置
缺点：查找效率变低，互相冲突导致插入逻辑复杂
线性探测:线性找下一个空位置,++
二次探测:平方步调找下一个位置,^2

2.开散列(哈希桶)(拉链法):冲突的位置下加上链表(哈希桶),由此STL中并没有双向迭代器
缺点:链表太长有效率问题
优点:冲突不会相互影响

---

二、闭散列的哈希表实现

---

实际中开散列应用情况优于闭散列,点一下

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

template<class K>
struct KeyToCmp //得到可以进行比较的数据
{
	size_t operator()(const K& k)
	{
		return (size_t)k;
	}
};

template<>
struct KeyToCmp<string> //特化一个string的仿函数,使得字符也能有其映射的地址
{
	size_t operator()(const string& k)
	{
		size_t hash = 0;
		for (auto& e : k)
		{
			hash += e;
		}
		return hash;
	}
};


enum State
{
	EMPTY,
	EXIST,
	DELETE
};
	
template<class K,class V>
struct HashData
{
	pair<K,V> _kv;
	State _state = EMPTY; //通过加入状态成员来方便进行增删查改
};
	
template<class K,class V,class Hash = KeyToCmp<int>>
class HashTable
{
public:
	typedef HashData<K,V> Data;

	HashTable() //构造
	{
		_tables.resize(10);
	}


	//负载因子 = 表中数据/表的大小  衡量哈希表满的程度
	//负载因子越大,插入数据越容易发生哈希冲突,冲突越多,效率越低
	//所以哈希表并不是满了才增容,一般负载因子在0.7左右就开始增容
	//控制的太小,会使得空间浪费
	bool Insert(const pair<K,V>& kv)
	{
		if (Find(kv.first) != nullptr) //已经有了
			return false;
		
		if (_num * 10 / _tables.size() >= 7) //负载因子大了,开始增容
		{
			HashTable<K, V, Hash> tmp;
			tmp._tables.resize(2 * _tables.size()); //新创建一个哈希表,将其数组空间扩大至旧哈希表的两倍
			
			for (auto& e : _tables)
			{
				if (e._state == EXIST) //如果有数据
					tmp.Insert(e._kv); //插入,扩容已经在上面完成了,递归时判断增容条件进不去,不会造成死循环
			}
			_tables.swap(tmp._tables);
		}

		Hash get;
		size_t index = get(kv.first) % _tables.size();

		while (_tables[index]._state == EXIST)
		{
			index++;
			index %= _tables.size();
		}

		_tables[index]._kv = kv;
		_tables[index]._state = EXIST;
		_num++;
		
		return true;
	}


	Data* Find(const K& k)
	{
		
		Hash get;
		size_t index = get(k) % _tables.size();

		while (_tables[index]._state != EMPTY)
		{
			if (_tables[index]._state == EXIST && _tables[index]._kv.first == k)
				return &_tables[index];
			index++;
			index %= _tables.size();
		}
		return nullptr; //哈希冲突是连续的,如果第一个后面为空,说明后面也没有冲突的情况,直接返回
	}


	bool Erase(const pair<K, V>& kv)
	{
		Data* ret = Find(kv.first);
		if (ret)
		{
			ret->_state = DELETE;
			--_num;
			return true;
		}
		else
		{
			return false;
		}
	}
	
private:
	vector<Data> _tables;
	size_t _num = 0; //存储当前存储有效数据的个数
};

---

三、开散列模拟实现unordered_xxx

---

unordered_xxx底层都是由开散列实现的

#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace BsyOpen
{
	template<class K>
	struct GetWay
	{
		const K& operator()(const K& k)
		{
			return k;
		}
	};

	template<> //特化处理字符串,使得其返回值能够被模
	struct GetWay<string>
	{
		size_t operator()(const string& k)
		{
			size_t way = 0;
			for (size_t i = 0; i < k.size(); ++i)
			{
				way *= 131; //BKDR Hash,使得哈希冲突降低
				way += k[i];
			}
			return way;
		}
	};


	template<class T> //一个哈希表节点
	struct HashNode 
	{
		T _data;
		HashNode<T>* _next;
		//我们自己实现的哈希输出,并非输入的顺序,如果要实现按输入顺序输出就要多指针
		//HashNode<T>* _linknext; //以按顺序输出
		//HashNode<T>* _linkprev; //以删除

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


	// 前置声明一下, 否则在迭代器类中, 无法识别出HashTable是什么
	template<class K, class T, class TheKey, class GetWayy> //哈希表
	class HashTable; 

	template<class K,class T,class TheKey,class GetWayy> //哈希表迭代器
	struct __HashIterator
	{
		typedef __HashIterator< K, T, TheKey, GetWayy> Self;
		typedef HashTable<K, T, TheKey, GetWayy> HT;
		typedef HashNode<T> Node;
		Node* _node;
		HT* _pht; //以便在后续operator++中起到作用

		__HashIterator(Node* node,HT* pht)
			:_node(node)
			,_pht(pht)
		{}

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

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

		Self operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next; //如果桶没走完接着往下走
			}
			else
			{
				TheKey thekey;
				GetWayy getway;
				//计算数值应该位于哪个头节点
				size_t i = getway(thekey(_node->_data)) % _pht->_tables.size();
			  //size_t i = GetWayy()(TheKey()(_node->_data)) % _pht->_tables.size();
				i++; //现在i就是下一个需要验证是否为空的数组下标
				for (; i < _pht->_tables.size(); ++i)
				{
					Node* cur = _pht->_tables[i];
					if (cur)
					{
						_node = cur;
						return *this;
					}
				}
				//此时说明没有下一个节点了
				_node = nullptr;
			}
			return *this;
		}

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


	template<class K,class T,class TheKey,class GetWayy> //哈希表
	class HashTable
	{
	public:
		friend struct __HashIterator< K, T, TheKey, GetWayy>;
		typedef HashNode<T> Node;
		typedef __HashIterator< K, T, TheKey,GetWayy> iterator;

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

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

		~HashTable() //销毁完桶之后,,析构自动销毁this,即vector会随着析构函数销毁
		{
			Clear();
		}

		void Clear()
		{
			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; //使得无法访问每个头节点
			}
		}

		size_t GetNextPrime(size_t num) //这是一种算法,使得可以减小哈希冲突
		{
			const int primecount = 28;
			const size_t primelist[primecount] = //二倍关系质数表
			{
				53,97,193,389,769,
				1543,3079,6151,12289,24593,
				49157,98317,1996613,393241,786433,
				1572869,3145739,6291469,12582917,25165843,
				50331653,100663319,201326611,402653189,805306457,
				1610612741,3221225473,4294967291
			};

			for (size_t i = 0; i < primecount; ++i)
			{
				if (primelist[i] > num)
				{
					return primelist[i];
				}
			}
			return primelist[primecount - 1]; //如果还大,就一直返回最后一个
		}

		pair<iterator,bool> Insert(const T& data)
		{
			TheKey thekey;
			GetWayy getway;

			if (_num == _tables.size()) //此时负载因子为1,避免以后造成大量冲突,增容
			{
				vector<Node*> newtable;
				size_t newsize = GetNextPrime(_num);
				newtable.resize(newsize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i]; //取每个头
					while (cur)
					{
						//旧表取下重新计算新表中的位置
						Node* next = cur->_next;
						size_t index = getway(thekey(cur->_data)) % newtable.size(); //新表中的位置
						cur->_next = newtable[index]; //头插进去
						newtable[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr; 
				}
				_tables.swap(newtable);
			}


			size_t index = getway(thekey(data)) % _tables.size();

			Node* cur = _tables[index];
			while (cur)
			{
				if (thekey(cur->_data) == thekey(data)) //重复了,不插入,结束
					return make_pair(iterator(cur,this),false);
				else
					cur = cur->_next;
			}

			//检验完后走到这里说明可以插入了
			//选择头插,因为有头节点的位置,不用找尾
			Node* newnode = new Node(data);
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_num;
			return make_pair(iterator(newnode, this), true);
		}

		Node* Find(const K& k)
		{
			TheKey thekey;
			GetWayy getway;
			size_t index = getway(k) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (thekey(cur->_data) == k)
					return cur;
				else
					cur = cur->_next;
			}
			return nullptr;
		}


		bool Erase(const K& k)
		{
			TheKey thekey;
			GetWayy getway;
			size_t index = getway(k) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index]; //找到需要找到数据的头
			while (cur)
			{
				if (thekey(cur->_data) == k)//找到了
				{

					if (prev == nullptr) //说明要删除的对象就是第一个节点
						_tables[index] = cur->_next;
					else
						prev->_next = cur->_next;
					
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

	private:
		vector<Node*> _tables;
		size_t _num = 0;
	};
}

---

1.unordered_set

#pragma once
#include"Open_Hash.hpp"

namespace Bsy
{
	template<class K, class GetWayy = BsyOpen::GetWay<K>>
	class unordered_set
	{
		struct TheKeyOfSet
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};


	public:
		typedef typename BsyOpen::HashTable<K, K, TheKeyOfSet, GetWayy>::iterator iterator;

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

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

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

	private:
		BsyOpen::HashTable<K, K, TheKeyOfSet,GetWayy> _ht;
	};

	void test_unordered_set1()
	{
		unordered_set<int> s;
		s.insert(1);
		s.insert(5);
		s.insert(6);
		s.insert(2);

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

}

---

2.unordered_map

#pragma once
#include"Open_Hash.hpp"

namespace Bsy
{
	template<class K,class V, class GetWayy = BsyOpen::GetWay<K>>
	class unordered_map
	{
		struct TheKeyOfMap
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename BsyOpen::HashTable<K, pair<K,V>, TheKeyOfMap, GetWayy>::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& k)
		{
			//pair<iterator, bool> ret = _ht.Insert(make_pair(k, V()));
			//return ret.first->second;
			return _ht.Insert(make_pair(k, V())).first->second;
		}

	private:
		BsyOpen::HashTable<K, pair<K, V>, TheKeyOfMap,GetWayy> _ht;
	};


	void test_unordered_map1()
	{
		unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "paixu"));
		dict.insert(make_pair("left", "zuo"));
		dict.insert(make_pair("long", "chang"));
		dict["left"] = "you";
		dict["hash"] = "haxi";

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