哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素即：时间复杂度为O(1)。 如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立 一 一 映射的关系，那么在查找时通过该函数可以很快找到该元素。

当该结构当中插入和搜索元素过程如下：

插入元素： 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)

例如：

例如：数据集合{1，7，6，4，5，9}； 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索只需要判断哈希函数位置是否是待查找元素即可，并不需要进行多次关键值得比较，因此搜索的速度比较快 

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

例：

哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数

1. 直接定址法--(常用)

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

优点：简单、均匀，效率高，它可以通过哈希函数直接定位到你需要查找值的位置

缺点：需要事先知道关键字的分布情况，只适用于数据范围比较集中的场景

2. 除留余数法--(常用)

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

优点：使用场景广泛，不受限制，通常使用在数据的范围比较分散的场景

缺点：存在哈希冲突问题，多个值可能被映射到一个位置，哈希冲突越多，效率下降越快

3. 平方取中法

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

使用场景：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按散列表表长，取后几位作为散列地址。

使用场景：折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法

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

使用场景：应用于关键字长度不等时采用此法

6. 数学分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希(散列)地址

如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列（开放定址法）

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有 空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

寻找下一个位置方法很多，常见的就以下两种：

一. 线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

线性探测的插入：

1.通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素

2.如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素

线性探测的删除：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。比如删除元素8，如果直接删除掉，25查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

例：

所以我们采取了伪删除法给哈希表每个空间来个标记

EMPTY此位置空

EXIST此位置已经有元素

DELETE元素已经删除

其实通过对上图的分析，我们将数据插入到有限的空间中时，当空间中的元素越多，插入元素时产生冲突的概率就越大，，冲突多次才插入到表中的元素，在查找时，效率也必然会降低，

所以介于此问题，在使用开放定址法实现哈希表时，我们需要引入负载因子（载荷因子）

散列表负载因子（载荷因子）的定义为：

负载因子 = 装载进哈希表的有效长度 / 哈希表长度

负载因子越大表示哈希表空间使用率越高，哈希表产生哈希冲突的概率就越高

负载因子越小表示哈希表空间使用率越低（空间浪费越多），哈希表产生哈希冲突的概率就越低

对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，超过0.8会导致在查表时CPU缓存不命中（cache missing）按照指数曲线上升。
因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容

增容：

而且增容会在一定程度上缓解哈希冲突/碰撞，因为原表部分产生哈希碰撞的值，映射到新表后可能不会产生哈希碰撞（从上图的正常映射可以看出）

线性探测优点：实现非常简单

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同 关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

二. 二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位 置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法 为：H_i = (H_0 + i^2 )% m

其中：

H_i是冲突元素通过二次探测后得到的存放位置

H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置

i = 1,2,3…，

m是表的大小

例：以下是图片演示

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

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

开散列（拉链法/哈希桶）

开散列法又叫链地址法(拉链法或哈希桶)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

和闭散列不同，闭散列是如果我们起了冲突，我就换一个地方，抢占本该属于别人的位置，开散列则是我们起了冲突，好！，那我就挂在你下面

与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。

闭散列的开放定址法，负载因子不能超过1，一般建议控制在 0.0~0.8 之间。
开散列的哈希桶，负载因子可以等于1，一般建议控制在 0.0~1.0 之间。

在实际中，我们一般使用开散列来实现哈希表

主要原因有两点：

1.负载因子可以更大，空间利用率高，哈希冲突概率还是有，但已经得到可观的改善

2.遇到极端情况也有可解决的方法

哈希桶的极端情况：

遇到这种情况的解决方法：

我们可以将哈希桶的单链结构转换为红黑树结构，将红黑树的根结点储存在哈希表中

将单链表改变为红黑树之后，就算一个桶中装了10亿数据，也只需要30次，查找的时间复杂度：O(logN)，这就是我们俗称的 “ 桶里种树”

为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构，比如在JAVA中比较新一点的版本中，当桶当中的数据个数超过8时，就会将该桶当中的单链表结构换成红黑树结构，而当该桶当中的数据个数减少到8或8以下时，又会将该桶当中的红黑树结构换回单链表结构。

但有些地方也会选择不做此处理，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大。

哈希表闭散列的实现

开放定址法：线性探测

namespace open_oddr
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashTableData
	{
		pair<K, V> _data; //存放的数据
		State _state = EMPTY; //状态值
	};

	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_table.resize(10);
		}

		bool insert(const pair<K, V>& data)
		{
            if (Find(data.first) != nullptr)
			{
				return false;
			}

			HashFunc kot;
			//使用负载因子控制什么时机扩容
			//if((double)_n / (double)_table.size() != 0.7)
			if (_n * 10 / _table.size() >= 7)
			{
				size_t newSize = _table.size() * 2;
				HashTable<K, V, HashFunc> newtable;
				newtable._table.resize(newSize);
				size_t hashi = 0;
				while (hashi < _table.size())
				{
					//复用insert，因为newtable已经被扩容了，不需要担心负载因子引发的扩容问题
					//重新映射
					newtable.insert(_table[hashi]._data);
					++hashi;
				}

				//新旧表交换
				_table.swap(newtable._table);
			}

			size_t hashi = kot(data.first) % _table.size();
			//状态值为EMPTY/DELETE，循环结束
			while (_table[hashi]._state == EXIST)
			{
				hashi = hashi % _table.size();
				hashi++;
			}
			_table[hashi]._data = data;
			_table[hashi]._state = EXIST;
			++_n;
			return true;
		}

		//参数K给上const，禁止修改K
		pair<const K, V>* Find(const K& key)
		{
			HashFunc kot;
			size_t hashi = kot(key) % _table.size();
			while (_table[hashi]._state == EXIST
				|| _table[hashi]._state == DELETE)
			{
				if(_table[hashi]._data.frist == key)
					return &_table[hashi]._kv;

				hashi = hashi % _table.size();
				hashi++;
			}
			return nullptr;
		}

		bool erase(const K& key)
		{
			size_t pos = Find(key);
			if (_table[pos]._state == EXIST
				|| _table[pos]._state == EMPTY)
			{
				//下一个插入的数据直接覆盖即可，你放入其他值没有意义，将状态值修改为DLETE
				_table[pos]._state == DELETE;
				--_n;
			}

			return _table[pos]._state == DELETE
				|| _table[pos]._state == EMPTY;
		}

	private:
		vector<HashTableData<K, V>> _table;
		size_t _n; //哈希表中有效符号的个数
	};
}

哈希表开散列的实现

哈希桶 / 拉链法

使用哈希桶实现哈希表，我们需要一个结点类，以便于后面链表的实现，与开放定址法不同的是

哈希桶的实现不需要使用状态值，我们知道在开放地址法中我们引入状态值是因为在进行查找，插入等操作时，我们需要遍历树组，直到下一个地址为空结束，在进行删除行为时，直接删除数据会影响到前面接口遍历数组的行为，但在哈希桶中删除数据并不会影响其他接口进行工作，由于它的数据结构为链表，每个数据都是链接起来的，进行删除工作时直接删除就可以了

结点类

template<class K, class V>
struct HashNode
{
	pair<K, V> _data;
	HashNode<K, V>* next;

	HashNode(const pair<K, V>& data)
		:_data(data)
		,next(nullptr)
	{}
};

namespace Hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _data;
		HashNode<K, V>* next;

		HashNode(const pair<K, V>& data)
			:_data(data)
			,next(nullptr)
		{}
	};

	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		HashTable(const HashTable<K, V, HashFunc>& H)
		{
			HashFunc kot;
			size_t n = H._table.size();
			_table.resize(n);

			for (size_t i = 0; i < n; ++i)
			{
				Node* cur = H._table[i];
				while (cur)
				{
					size_t Hashi = kot(cur->_data.first) % n;
					Node* newnode = new Node(H._table[Hashi]->_data);
					//头插
					newnode->next = _table[i];
					_table[i] = newnode;

					cur = cur->next;
				}
			}

		}

		~HashTable()
		{
				for (size_t i = 0; i < _table.size(); ++i)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->next;
						delete cur;
						cur = next;
					}

					_table[i] = nullptr;
				}
		}

		bool insert(const pair<K, V>& data)
		{
			if (Find(data.first))
				return false;
			//负载因子处理扩容
			//为1进行扩容
			if (_n == _table.size())
			{
				HashFunc kot;
				size_t newSize = _table.size() * 2;
				vector<Node*> newtable;
				newtable.resize(newSize, nullptr);
				
				//哈希桶上链接的结点位置是任意的，头插，尾插都可以
				for(size_t i = 0; i < _table.size(); ++i)
				{
					Node* cur = _table[i];
					//将cur上哈希桶的每个结点都给链接到_table上
					//将旧哈希桶上的元素重新映射到新哈希表上
					while (cur)
					{
						Node* next = cur->next;
						size_t Hashi = kot(cur->_data.first) % newSize;

						//头插操作，将cur理解为一个新结点头插到这个newtable上
						cur->next = newtable[Hashi];
						newtable[Hashi] = cur;

						cur = next;
					}
				}
				_table.swap(newtable);
			}

			HashFunc kot;
			size_t hashi = kot(data.first) % _table.size();

			//头插
			Node* newnode = new Node(data);
			newnode->next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			
			return true;
		}

		Node* Find(const K& key)
		{
			HashFunc kot;
			size_t Hashi = kot(key) % _table.size();

			Node* cur = _table[Hashi];
			while (cur != nullptr)
			{
				Node* next = cur->next;

				if (cur->_data.first == key)
					return cur;

				cur = next;
			}

			return nullptr;
		}

		bool erase(const K& key)
		{
			if (Find(key) == nullptr)
				return false;

			HashFunc kot;
			size_t Hashi = kot(key) % _table.size();

			Node* cur = _table[Hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (cur->_data.first == key)
				{
					if (prev == nullptr)
					{
						_table[Hashi] = cur->next;
					}
					else
					{
						prev->next = cur->next;
					}
					delete cur;
					return true;
				}

				prev = cur;
				cur = cur->next;
			}

			return false;	

	private:
		vector<Node*> _table;
		size_t _n;
	};
}

两个方法需要使用的部分

//确保取余运算符两边是正整数，下标不能是负整数
template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


//模板的特化
//string是特殊处理，这样哈希表就可以使用string
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			//使用上一个ASCII码乘以131，避免得到相同的值，注意并不能完全避免，如果数据量大还是会有相同的数
			hash = hash * 131 + ch;
		}

		return hash;
	}
};

有人说除留余数法，最好模一个素数，在vs环境下它并没有模素数，但是在g++的环境下它模了素数，但是并没有很好的科学依据，在使用除留余数法时模一个素数是最好的

如何每次快速取一个类似两倍关系的素数？

size_t GetNextPrime(size_t prime)
{
	const int PRIMECOUNT = 28;
	static const size_t primeList[PRIMECOUNT] =
	{
	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
	};
	size_t i = 0;
	for (; i < PRIMECOUNT; ++i)
	{
		if (primeList[i] > prime)
			return primeList[i];
	}
	return primeList[i];
}

开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。