1.哈西表的基本概念 

二 哈西函数

2.1直接定值法

2.2除留余数法

2.3几种不太常用的方法

三 哈西冲突

四 开放地址法

4.1线性探测

4.2二次探测

五 拉链法

1.哈西表的基本概念 

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。------来自百度。

生活中有很多用到哈西表的地方比如说：

1.学习英语我们在学习英语的时候遇到不认识的单词总会上网查这个单词：

尽管英语老师非常不建议我们这样，因为电子词典查出来的中文资料太有限，而传统的纸质词典可以查到单词的多种含义、词性、例句等。但是就我个人而言还是更加喜欢这种方式

在我们的程序世界里，往往也需要在内存中存放这样一个「词典」，方便我们进行高效的查询和统计。

例如开发一个学·生管理系统，需要有通过输入学号快速查出对应学生的姓名的功能。这里不必每次都去查询数据库，而可以在内存中建立一个缓存表，这样做可以提高查询效率。

再如我们需要统计一本英文书里某些单词出现的频率，就需要遍历整本书的内容，把这些单词出现的次数记录在内存中。

因为这些需求，一个重要的数据结构诞生了，这个数据结构叫作 散列表也叫做哈西表。

向哈西表中插入和搜索元素的过程如下：

1.插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
2.搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比
较，若关键码相等，则搜索成功。

 二 哈西函数

2.1直接定值法

直接定制法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

1.优点：简单、均匀

2.缺点：需要事先知道关键字的分布情况并且只使用范围比较小的的情况

3.使用场景：适合查找比较小且连续的情况

4.不适用场景：当数据分布比较分散比如1，199847348，90，5这样的数据就不太适合使用这种方法

 2.2除留余数法

**除留余数法：**设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址.

优点：使用范围广，基本不受限制。

缺点：存在哈西冲突，需要解决哈西冲突当哈西冲突很多时效率下降的非常的厉害。

 2.3几种不太常用的方法

1.平方取中法
hash(key)=key*key然后取函数返回值的中间的几位作为哈西地址

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

2.折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

3. 随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。

4.数学分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

三 哈西冲突

哈西冲突是指不同的key通过相同的哈西函数计算出相同的哈西映射地址，这种现象叫做哈西冲突。下面举个例子：

首先我们插入一组 Key 为 002931、Value 为 王五 的键值对。具体该怎么做呢？

第 1 步，通过哈希函数，把 Key 转化成数组下标 5。

第 2 步，如果数组下标5对应的位置没有元素，就把这个 Entry 填充到数组下标 5 的位置。

但是，由于数组的长度是有限的，当插入的 Entry 越来越多时，不同的 Key 通过哈希函数获得的下标有可能是相同的。例如 002936 这个 Key 对应的数组下标是 2；002947 这个 Key 对应的数组下标也是 2。

这种情况，就叫作** 哈希冲突。 哎呀，哈希函数“撞衫”了，这该怎么办呢?
哈希冲突是无法避免的，既然不能避免，我们就要想办法来解决。解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。**

 四 开放地址法

4.1线性探测

开放定址法也叫做闭散列。

开放寻址法的原理很简单，当一个 Key 通过哈希函数获得对应的数组下标已被占用时，我们可以「另谋高就」，寻找下一个空档位置。

以上面的情况为例，Entry6 通过哈希函数得到下标 2，该下标在数组中已经有了其他元素，那么就向后移动 1 位，看看数组下标 3 的位置是否有空。

很不巧，下标 3 也已经被占用，那么就再向后移动 1 位，看看数组下标 4 的位置是否有空。

幸运的是，数组下标 4 的位置还没有被占用，因此把 Entry6 存入数组下标 4 的位置。

我们可以发现当哈西表的数据越多哈西冲突就越厉害。还有就是****散列表是基于数组实现的，那么散列表也要涉及扩容的问题

当经过多次元素插入，散列表达到一定饱和度时，Key 映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响。这时，散列表就需要扩展它的长度，也就是进行 扩容。

那么哈希表什么情况下进行扩容?如何扩容?在这里引入了散列表的载荷因子定义为:α =填入表中的元素个数/散列表的长度α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大;反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子o的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

4.2二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为:H, =(Ho+i2 )% m,或者: H, =(Ho -i2 )% m。其中: i=1,2,3...，H是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。对于2.1中如果要插入44，产生冲突，使用解决后的情况为:

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

对应代码：

在这里解释一下哈西表如何查找：
查找 Key 为 002936 的 Entry 在散列表中所对应的值。具体该怎么做呢？下面以链表法为例来讲一下。

1 步，通过哈希函数，把 Key 转化成数组下标 2。

第 2 步，找到数组下标 2 所对应的元素，如果这个元素的 Key 是 002936，那么就找到了；如果这个 Key 不是 002936 也没关系，从下一个位置继续往后找如果下一个位置是空说明没有这个数字如果找到数组的最后一个位置就从头开始继续往后找。

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

namespace CloseHash
{
	enum State
	{
		EMPTY,
		EXITS,
		DELETE,
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;  // 状态
	};

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

	// 特化
	template<>
	struct Hash<string>
	{
		// "int"  "insert" 
		// 字符串转成对应一个整形值，因为整形才能取模算映射位置
		// 期望->字符串不同，转出的整形值尽量不同
		// "abcd" "bcad"
		// "abbb" "abca"
		size_t operator()(const string& s)
		{
			// BKDR Hash
			size_t value = 0;
			for (auto ch : s)
			{
				value += ch;
				value *= 131;
			}

			return value;
		}
	};

	template<class K, class V, class HashFunc = Hash<K>>
	class HashTable
	{
	public:
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}

			// 负载因子大于0.7，就增容
			//if (_n*10 / _table.size() > 7)
			if (_table.size() == 0)
			{
				_table.resize(10);
			}
			else if ((double)_n / (double)_table.size() > 0.7)
			{
				//vector<HashData> newtable;
				// newtable.resize(_table.size*2);
				//for (auto& e : _table)
				//{
				//	if (e._state == EXITS)
				//	{
				//		// 重新计算放到newtable
				//		// ...跟下面插入逻辑类似
				//	}
				//}

				//_table.swap(newtable);

				HashTable<K, V, HashFunc> newHT;
				newHT._table.resize(_table.size() * 2);
				for (auto& e : _table)
				{
					if (e._state == EXITS)
					{
						newHT.Insert(e._kv);
					}
				}

				_table.swap(newHT._table);
			}

			HashFunc hf;
			size_t start = hf(kv.first) % _table.size();
			size_t index = start;

			// 探测后面的位置 -- 线性探测 or 二次探测
			size_t i = 1;
			while (_table[index]._state == EXITS)
			{
				index = start + i;
				index %= _table.size();
				++i;
			}

			_table[index]._kv = kv;
			_table[index]._state = EXITS;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			if (_table.size() == 0)
			{
				return nullptr;
			}

			HashFunc hf;
			size_t start = hf(key) % _table.size();//使用仿函数将key值取出来有可能key不支持取模
			size_t index = start;
			size_t i = 1;
			while (_table[index]._state != EMPTY)//不为空继续找
			{
				if (_table[index]._state == EXITS
					&& _table[index]._kv.first == key)//找到了
				{
					return &_table[index];
				}

				index = start + i;
				index %= _table.size();
				++i;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;
				return true;
			}
		}

	private:
		/*	HashData* _table;
			size_t _size;
			size_t _capacity;*/
		vector<HashData<K, V>> _table;
		size_t _n = 0;  // 存储有效数据的个数
	};

五 拉链法

1. 开散列概念
   开散列法又叫链地址法(拉链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。拉链法与开放定址法不同，拉链法中数组的每一个元素不仅是一个 Entry 对象，还是一个链表的头节点。每一个 Entry 对象通过next指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。

下面来看一下拉链法中如何查找：

查找 Key 为 002936 的 Entry 在散列表中所对应的值。具体该怎么做呢？下面以链表法为例来讲一下。第 1 步，通过哈希函数，把 Key 转化成数组下标 2。第 2 步，找到数组下标 2 所对应的元素，如果这个元素的 Key 是 002936，那么就找到了；如果这个 Key 不是 002936 也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与 Key 相匹配的节点。

当然开散列也需要扩容：

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

扩容的步骤如下：

1.扩容，创建一个新的 Entry 空数组，长度是原数组的 2 倍。
2.重新 Hash，遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组中。为什么要重新 Hash 呢？因为长度扩大以后，Hash 的规则也随之改变。经过扩容，原本拥挤的散列表重新变得稀疏，原有的 Entry 也重新得到了尽可能均匀的分配。

扩容前：

扩容后：

在拉链法中如果某一条链冲突的非常的厉害，此时可以选择在对应位置挂红黑树。

对于代码

template<class K>
		struct Hash
		{
			size_t operator()(const K& key)
			{
				return key;
			}
		};
	
		// 特化
		template<>
		struct Hash < string >
		{
			// "int"  "insert" 
			// 字符串转成对应一个整形值，因为整形才能取模算映射位置
			// 期望->字符串不同，转出的整形值尽量不同
			// "abcd" "bcad"
			// "abbb" "abca"
			size_t operator()(const string& s)
			{
				// BKDR Hash
				size_t value = 0;
				for (auto ch : s)
				{
					value += ch;
					value *= 131;
				}
	
				return value;
			}
		};
	
		template<class K, class V>
		struct HashNode
		{
			HashNode<K, V>* _next;
			pair<K, V> _kv;
	
			HashNode(const pair<K, V>& kv)
				:_next(nullptr)
				, _kv(kv)
			{}
		};
	
		template<class K, class V, class HashFunc = Hash<K>>
		class HashTable
		{
			typedef HashNode<K, V> Node;
		public:
			size_t GetNextPrime(size_t prime)
			{
				const int PRIMECOUNT = 28;
				static const size_t primeList[PRIMECOUNT] =
				{
					53ul, 97ul, 193ul, 389ul, 769ul,
					1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
					49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
					1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
					50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
					1610612741ul, 3221225473ul, 4294967291ul
				};
	
				size_t i = 0;
				for (; i < PRIMECOUNT; ++i)
				{
					if (primeList[i] > prime)
						return primeList[i];
				}
	
				return primeList[i];
			}
	
			bool Insert(const pair<K, V>& kv)
			{
				if (Find(kv.first))
					return false;
	
				HashFunc hf;
				// 负载因子到1时，进行增容
				if (_n == _table.size())
				{
					vector<Node*> newtable;
					//size_t newSize = _table.size() == 0 ? 8 : _table.size() * 2;
					//newtable.resize(newSize, nullptr);
					newtable.resize(GetNextPrime(_table.size()));
	
					// 遍历取旧表中节点，重新算映射到新表中的位置，挂到新表中
					for (size_t i = 0; i < _table.size(); ++i)
					{
						if (_table[i])
						{
							Node* cur = _table[i];
							while (cur)
							{
								Node* next = cur->_next;
								size_t index = hf(cur->_kv.first) % newtable.size();
								// 头插
								cur->_next = newtable[index];
								newtable[index] = cur;
	
								cur = next;
							}
							_table[i] = nullptr;
						}
					}
	
					_table.swap(newtable);
				}
	
				size_t index = hf(kv.first) % _table.size();
				Node* newnode = new Node(kv);
	
				// 头插
				newnode->_next = _table[index];
				_table[index] = newnode;
				++_n;
	
				return true;
			}
	
			Node* Find(const K& key)
			{
				if (_table.size() == 0)
				{
					return false;
				}
	
				HashFunc hf;
				size_t index = hf(key) % _table.size();
				Node* cur = _table[index];
				while (cur)
				{
					if (cur->_kv.first == key)
					{
						return cur;
					}
					else
					{
						cur = cur->_next;
					}
				}
	
				return nullptr;
			}
	
			bool Erase(const K& key)
			{
				size_t index = hf(key) % _table.size();
				Node* prev = nullptr;
				Node* cur = _table[index];
				while (cur)
				{
					if (cur->_kv.first == key)
					{
						if (_table[index] == cur)
						{
							_table[index] = cur->_next;
						}
						else
						{
							prev->_next = cur->_next;
						}
	
						--_n;
						delete cur;
						return true;
					}
					
					prev = cur;
					cur = cur->_next;
				}
	
				return false;
			}
	
		private:
			vector<Node*> _table;
			size_t _n = 0;         // 有效数据的个数
		};