[数据结构与算法]C++【数据结构】 —— 哈希表 （ 闭散列、开散列的深度理解）

前言

• 在C++98中的关联式容器，底层为红黑树结构，其中包括map、set、multimap、multiset
• 而今天学习提到的哈希，便是C++11中，新增关联式容器的unorder_map、unorder_set、unorder_multimap、unorder_multiset的底层结构——哈希结构

1、哈希概念

• 哈希，即** 不经过任何比较，一次直接从表中得到要搜索的元素 。 如果构造一种存储结构，通过某种函数(hashFunc) ** 使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
• 而其的插入删除的时间复杂度皆为O（1） ；
• 而对于这种数据结构的插入和搜索都与关键码 息息相关，其中哈希方法使用的转换函数为哈希（散列）函数，构造出的结构为哈希（散列表）表，

• 例如，将一arr数组数据{2，3，1，6，8，4，7}；
  设定 哈希函数：hash（哈希表的下标）=arr[i]%capacity capacity=8;
  

而此时的查找和删除操作，便可通过设定的哈希函数规则操作！！！

2、哈希冲突

例如在上述的实例，则原有数组的基础上，增添一个元素9，那么通过该哈希函数，元素1和9，便都会在哈希表下标为1的位置，发生冲突， 那么这种情况就叫做哈希冲突。

1. 引起哈希冲突的主要原因便是，哈希函数设计的不够合理
2. 而哈希设计的原则：
   1. 哈希函数的值域一定要在表格的范围内；
   2. 哈希函数产生的哈希地址一定要均匀；
   3. 哈希函数设计要尽可能简单；

3、哈希函数

常见的哈希函数

3.1、 直接定制法 —（常用）

• 简单点说，就是哈希函数是一种一次线性函数，Hash=A*key+B的形式，根据其具有的单调性，达到一一对应的特性
• 但缺点是，设计哈希函数前，得了解关键码，即被分配的元素数据的分布情况，来设计合适线性函数，且数据量较大，难度也会攀升
• 使用场景：适用于查找比较小且连续的情况

3.2、 除留余数法–(常用)

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

3.3、 平方取中法–(了解)

• 就是对关键码进行平方处理，然后去关键码的中间几位数作为哈希地址，例如关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
• 适用环境：不知道关键字的分布，但是位数又不是很大的情况

3.4、 折叠法–(了解)

• 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为哈希地址。例如12345，每段两个数字，累加和51，作为哈希地址
  -适用环境：不知道关键字的分布，但是位数又不是很大的情况

3.5、随机数法–(了解)

• 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
• 适用情况：通常应用于关键字长度不等

3.6、 数学分析法–(了解)

-即对于大量多位的数据，这些数据在某些位上分布不均匀只有某几种符号经常出现，还可能在某些位上分布均匀，每种符号出现的机会均等，例如某地区内的电话号，根据散列表大小，选取其中这些符号分布均匀的若干位作为散列表的地址，若出现冲突，可采用左右位移调整数据

• 适用环境：适用数据较长，但已知数据部分存在数据分布均匀的现象

以上均为一些解决,降低哈希冲突可能性的哈希函数设计，但需要注意的是无法避免哈希冲突

4、解决哈希冲突

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

4.1、闭散列

4.1.1、闭散列的概念

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

那么如何去寻找下一个空位置呢？

4.1.2、线性探测法

4.1.2.1、插入方式

首先通过哈希函数确定哈希表中的位置，若无元素，直接插入，反之存在，则发生哈希冲突，使用线性探测逐个查找空位置；

注意：

1. 将数据存于内存中，我们该如何判断哈希表中的对应哈希位置是否存在元素？

• 哈希表中的每一个位置维护两种状态EXIT和EMPTY,来判断是否存在元素；

2. 当对哈希表中的数据进行删除时，是否在删除元素后，直接将该状态设置为EMPTY?

• 答案当然也是哒咩啦，若删除元素B的哈希位置之前发生哈希冲突，有元素A存于后面的空闲哈希位置，那么设置EMPTY之后，该元素A则无法找到；

• 因而面对此情况，需要在前一种解决方法的基础上，增添一种状态DELETE;

//此时完善的查找方法
 		int Find(const K& key)
 {
 		size_t hashAddr = HashFunc(key);
 		while(_ht[hashAddr]._state != EMPTY)
 	{
 		if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key)
 		return hashAddr;
 		hashAddr++;
	}
	 return hashAddr;
 }

4.1.2.2、扩容方法

• 由于随着元素的插入，哈希表中的元素，也将越来越来多，这也说明发生哈希冲突的概率也越来越高，但是，哈希表中绝对不会放满元素，进而就涉及到扩容
• ！！！！！但是，扩容不能直接不能把原哈希表元素，直接拷贝至新空间！！！！因为拷贝之后，元素所在位置不符合哈希函数的对应条件！！
• 因而需重新原状态为EXIT的哈希元素，逐个按照哈希函数条件和插入方式，插入新的哈希表空间中

注意：那么待哈希桶中是何种状态的时候，才需要扩容呢？？？
那么这就涉及到一个概念——负载因子（又名负荷因子）

哈希表中的负载因子定义为：α=填入表中元素个数 / 散列表的长度

• 当α越大时，即填入表中数据越多，发生哈希冲突的概率就越大，反之，α越小，表明填入表中的数据越少，产生冲突的概率就越小
• 对于线性探测法（开放定址法），负载因子应严格限制在0.7~0.8以下。进统计，超过0.8，查表时的CPU缓存不命中按照指数曲线上升。因此，例如java库中，限制了负载因子为0.75；

4.1.2.3、优缺点

• 优点：线性探测的实现方法，非常简单
  我相信细心的铁铁，一定发现了，当发生哈希冲突后，可能存在连片的数据发生哈希冲突，而这对于数据查找的效率也将大大折扣；
• 缺点：一旦发生哈希冲突，所有冲突连在一片，容易产生数据的堆积，即不同的关键码占据着可用的位置，降低搜索效率；
  如下图所示
  
  那么将如何缓解呢？？？二次探测

4.1.3、二次探测

二次探测方式的出现，是为了解决线性探测中发生哈希冲突堆积的情况，而导致此缺点，与寻找“下一个位置”的方式有很大的关系！！！

因此二次探测为避免此问题,找下一个空位置的方法改进为：

• Hi=(H0+i^2 )%capacity 或者 Hi=(H0 - i^2)%capacity; （i=1,2,3…）
• 其中H0为关键码经哈希函数计算的结果；i表示第i次探测；

• 图中所述，二次探测优点解决了线性冲突堆积的现象，但缺点是降低空间利用率同时当空位置较少时搜寻下一个空位的次数也增加！！！
• 同时对于扩容，二次探测扩容时机的负载因子也会小于线性探测，一般不超过0.5；

4.2、开散列

4.2.1、概念

• 开散列法，又名链地址法或开链法
• 实则就是先将关键码通过哈希函数，确定其哈希地址，而具有相同哈希地址的元素集合，又称为一个桶，每一个桶都是单链表的形式，而链表的头节点存于哈希表中；

4.2.2、代码实现

template <class T>
struct HashBucketNode
{
	HashBucketNode<T>* _next;
	T _value;
	HashBucketNode(const T& value=T())
		:_value(value)
		,_next(nullptr)
	{
	}
};
template <class T>
class HashBucket
{
	typedef HashBucketNode<T> Node;
public:
	HashBucket(size_t size=10)
		:_table(size)
		, _size(0)
	{
	}
	//不考虑重复元素
	bool insertUnique(const T& value)
	{
		size_t bucketnum = HashFunc(value);
			Node* cur = _table[bucketnum];
			while (cur != nullptr)
			{
				if (cur->_value == value)
				{
					return false;
				}
				cur = cur->_next;
			}
			Node* newnode = new Node(value);
			newnode->_next = _table[bucketnum];
			_table[bucketnum] = newnode;
			_size++;
		   return true;
	}
	//不考虑重复元素
	bool EaseUnique(const T& value)
	{
		size_t bucketnum = HashFunc(value);
		Node* prev = nullptr;
		Node* cur = _table[bucketnum];
		size_t oldsize = _size;
		while (cur)
		{
			
			if (cur->_value == value)
			{
				if (prev == nullptr)
				{
					_table[bucketnum] = cur ->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				_size--;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}

		}
		return false;
	}
	//可重复元素
	bool insertEqual(const T& value)
	{
		size_t bucketnum = HashFunc(value);
		Node* cur = _table[bucketnum];
		Node* newnode = new Node(value);
		newnode->_next = cur;
		_table[bucketnum] = newnode;
		++_size;
		return true;
	}
	//可重复元素
	bool EaseEqual(const T& value)
	{
		size_t bucketnum = HashFunc(value);
		Node* cur = _table[bucketnum];
		Node* prev = nullptr;
		size_t oldsize = _size;
		while (cur != nullptr)
		{
			if (cur->_value == value)
			{
				if (prev == nullptr)
				{
					_table[bucketnum] = cur->_next;
					delete cur;
					cur = _table[bucketnum];
				}
				else
				{
					prev->_next = cur->_next;
					delete cur;
					cur = prev->_next;
				}
				_size--;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return oldsize!=_size;
	}
	//查找元素
	Node* Find(const T& value)
	{
		size_t bucketnum = HashFunc(value);
		Node* cur = _table[bucketnum];
		while (cur != nullptr)
		{
			if (cur->_value == value)
			{
				return cur;
			}
		}
		return nullptr;
	}
	//哈希表元素数目大小
	size_t Size()const
	{
		return _size;
	}
	//打印数据
	void print()
	{
		int i = 0;
		while(i<_table.size())
		{
			Node* cur = _table[i];
			while (cur != nullptr)
			{
				std::cout << cur->_value << "-->";
				cur = cur->_next;
			}
			std::cout << "NULL" << std::endl;
			i++;
	    } 
	}
private:
	size_t HashFunc(const T& value)
	{
		return value % _table.capacity();
	}
	std::vector<Node*> _table;
	size_t _size;
};

4.2.3、开散列增容

由于哈希桶的桶数一定，随着元素的逐渐插入，每一个桶中的元素个数越来越多，一定情况下，会严重影响哈希表的性能，因而便一定存在扩容操作；

那么在什么情况下，进行扩容呢?

• 其实对于哈希表的开散列法，理想状态，每一个桶中元素只有一个的时候，此时的插入和删除都是最佳的；
• 因而当哈希表中元素个数达到，哈希桶的容量时，则就应当扩容；

那么如何进行扩容呢？

• 扩容方式理念，实则和闭散列扩容方式相同，都是将哈表中的每一个元素，重新根据新的哈希函数，确定其地址，之后重新插入，而非单纯的将数据直接拷贝于新空间

那么扩容的大小如何确定呢？

• 对于除留余数法，这一哈希函数，容量的选择，当然也不是随随便便的啦，据统计，当容量设置为素数的时候，发生哈希冲突的概率是相对较低的，同时扩容的大小也得近似二倍的关系

对于上述要求，便有了以下代码

//对于扩容大小选择的函数封装
const int PRIMECOUNT = 28;
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 GetNextPrime(size_t prime)
{
 	size_t i = 0;
 	for(; i < PRIMECOUNT; ++i)
 {
 	if(primeList[i] > primeList[i])
 	return primeList[i];
 }
 	return primeList[i];
}

• 此外，我相信有铁子也疑惑过，那要是一直扩容，对于空间的浪费又会很大！！！
• 关于这一点的解释，可参照java中HashMap的底层实现
  1. 当桶中元素个数大于8时，桶的数据结构会由链表转为红黑树；
  2. 当桶的数据结构为红黑树时，桶中元素个数小于6时，桶又会由红黑树转为链表；

4.3、开散列和闭散列比较

• 应用开散列法处理哈希冲突，其中需要设置链接指针；
• 关于闭散列的线性探测以及二次探测，其的负载因子均分别需要控制在0.7和0.5以内，都必须保持大量空闲的空间以确保搜索效率；
• 而表项的空间又比指针大的多，因而也可理解为开散列法比闭散列法节省存储空间；

附加：

• 以上哈希桶的实现数据，被限制为int类型，对于string类型的哈希函数设计，感兴趣的铁子可研究此篇博客字符串哈希算法