【DS】哈希表，哈希桶的实现

哈希概念
哈希冲突
哈希函数
负载因子
哈希冲突的解决
- 闭散列
- 开散列
哈希表闭散列的实现
- 哈希表的结构
- 哈希函数
- 构造函数
- 查找
- 插入
- 删除
哈希表开散列的实现
- 哈希表的结构
- 查找
- 插入
- 删除
哈希表的表长建议是素数

平衡二叉树的学习中，学习及模拟实现了AVL树和红黑树，得益于其结构，查找效率可以达到惊人的

O (l o g N)

，但是平衡树中调平衡的开销及学习的成本也是不低的。于是今天再来学习一个同样高效，甚至更优的哈希表（桶），其实现难度也没有AVL树和红黑树高；而且 unordered系列的关联式容器的底层就是采用了哈希结构，unordered系列的关联式容器比inordered系列的关联式容器（map，set，multi…）效率甚至更优；之所以效率比较高，是因为其底层使用了哈希结构。

哈希概念

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

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

例如：

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

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

哈希是一种概念，哈希表（桶）才是数据结构。

如以下例子：

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

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。而且插入操作也简单高效。

既然哈希方法的效率如此高，那么它有什么缺陷吗？

哈希冲突

对于两个数据元素的关键字 $k_i$ 和 $k_j$ (i != j)，有 $k_i$ != $k_j$ ，但有：Hash( $k_i$ ) == Hash( $k_j$ )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

如：

哈希函数

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

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值
域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常用哈希函数——除留余数法

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

p一般为表长，即==m

哈希函数设计的核心就是尽量减少不同值经哈希函数计算后映射在同一哈希地址上，由此基础再尽量符合人们的认知即可。

注意：哈希函数的设计只能降低哈希冲突发生的可能，但是无法避免哈希冲突
借助负载因子，减少哈希冲突。

负载因子

定义：负载因子是指哈希表中已存储元素数量与哈希表总容量之间的比率。
计算公式：负载因子 λ = （已存储元素数量） / （哈希表总容量）。

性能影响：

当负载因子较低时，哈希表相对空闲，有较多的空闲槽位可供使用，这有助于减少哈希冲突，提高查找和插入操作的效率。
当负载因子较高时，哈希表的槽位大部分被占用，这可能会导致哈希冲突的增加，进而影响哈希表的性能。

空间利用率：

负载因子越高，空间利用率越高，但可能牺牲一定的性能。
负载因子越低，空间利用率越低，但性能可能更优。

同时，负载因子也可以是哈希表（桶）扩容的判断标志。不同实现方式的负载因子设定也不同。

哈希冲突的解决

对于哈希冲突这一问题，常用的解决方案有以下两种。

闭散列

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

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

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

还是上述情况，此时再插入一个44，由于哈希地址为4的已经有元素了，此时采用线性探测，一直往后检测寻找可插入位置，最终找到位置并插入。
哈希冲突

在开散列中，使用负载因子来减少哈希冲突的产生，同时使用负载因子来控制表的大小，所以在插入一个元素时，表一定是有空闲位置的。所以不必担心冲突的元素没位置放的情况。
对于开放定址法，负载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing)按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了负载因子为0.75，超过此值将调整表的大小，从而减少哈希冲突。

采用线性探测来解决哈希冲突的元素实际上是一种“摆烂”行为，别人占了我的位置，我就去占别人的位置，长期看来也不是一种解决问题的办法，而且在元素范围集中的时候，会造成局部拥堵；可能会造成大量元素都不在哈希函数映射的位置，那这样实际上也失去了哈希的意义。

不考虑负载因子扩容的情况下：
线性探测

当然你还可以采用别的方案解决哈希冲突的问题，但是基于闭散列这个思想下本质和线性探测是一致的。

开散列

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

哈希桶

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素，因此，有人也把开散列的哈希表叫做哈希桶

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

开散列与闭散列比较

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

哈希表闭散列的实现

哈希表的结构

之后将进行关联式容器的模拟实现，所以直接使用pair存放数据。除此之外：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

所以哈希表的数据类型为类HashData，其中包括一对pair，和状态标志State ；枚举类State 设有三种状态：空（EMPTY），删除（DELETE），存在（EXIST）

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

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

哈希表的底层通常是一个数组，所以直接使用vector。而且库中的哈希表也是这样实现的。再加一个记录存储个数的_size
哈希表stl

template<class K,class V,class Hash = HashFunc<K>>
class HashTable
{
public:
     //function

private:
	vector<HashData<K, V>> _table;
	size_t _size;
};

哈希函数

对于哈希表而言，其实现难度之一就是如何处理数据类型不是整型的问题

哈希表的底层是数组，哈希函数采用除留余数法时，需要K值支持%的操作，从而才能映射出有效的哈希地址（数组的下标只支持整型）

所以，在哈希表结构介绍时模板的第三个参数为一个仿函数，也就是我们所需的哈希函数来解决取整的问题。这个哈希函数只需要将传入的类型强转为整型即可。

只要K值能映射出有效的哈希地址（返回一个整型）即可进行映射插入操作，如：浮点数经哈希函数处理后只会保留整数部分，虽然不是原原本本地按K值映射（浮点数也不能映射），但是起码可以将浮点数转为接近的整型先映射到表中。查找时是会进行比对的，所以不需要的担心能否找回对应的K值。
这里的整型为无符号整型：数组下标也不支持负数。

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

template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto& e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

string可以视为常用类型，所以这里走个模板特化，当K类型为string时匹配这个string特化版的哈希函数

字符串的哈希算法具体可以参考——字符串哈希算法
开散列的哈希表的哈希函数也是如此。

构造函数

哈希表的成员为一个vector和一个在声明时给了默认值的内置类型，理论上来说是不需要手写构造函数的，这里我们手写一个的目的是开空间。哈希表的的底层是数组，实现时我们直接使用了一个vector会更加省事。那么哈希表的大小是用vector的size还是capacity呢？答案是size，因为vector的[]访问元素的下标的只能访问有效的数据个数，即size，所以使用size作为表的大小。

闭散列中负载因子设为0.7，达到0.7时则进行扩容

	HashTable()
	{
		_table.resize(10);//初始大小为10（是vector的size，不是capacity）
	}

查找

查找操作为其他操作的基础，所以还是很重要的；其实现步骤如下：

将查找的值通过除留余数法计算出对应的哈希地址
由于哈希冲突的原因，哈希地址上的值不一定就是查找的值，需要借助一个循环往后检测
先确认_state的状态，只有标签为EXIST的值才是存在的，再通比对K值检测是否存在，存在则返回其地址；最后找不到则返回nullptr

注意：由于是按照线性探测的方式解决哈希冲突的问题，所以冲突的值一定会在计算出的哈希地址的下一个空位置（即状态为EMPTY）。

	HashData<K, V>* Find(const K& key)//返回数据类型
	{
		Hash hs;//哈希函数取K
		size_t hashi = hs(key) % _table.size();//计算哈希地址
		while (_table[hashi]._state != EMPTY)//闭散列，真正的值可能在后面
		{
			//如果状态为delete，则不存在
			if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
			{
				return &_table[hashi];
			}
			++hashi;
			hashi %= _table.size();
		}
		return nullptr;
	}

插入

插入步骤如下：

去重，不支持重复的元素。
检测是否需要扩容，扩容则需要将旧表中的元素重新映射到新表。
- 扩容后可能可以缓解哈希冲突，所以需要重新映射到已经扩容的新表。
- 这个重新映射和插入操作是一致的。
插入新元素
1. 除留余数法计算哈希地址
2. 检测对应位置是否已存在元素（_state == EXIST），存在则往后推，直到找到空位置
3. 在表中插入对应元素，并把状态设为EXIST
4. _size记得++

以下实现的一个妙点就是在扩容时，直接开个已扩好容的新表，此时将旧表的元素重新映射到新表的方法是：调用新表的Insert，也就是复用了下面的插入逻辑，最后交换新旧两表即可。


	bool Insert(const pair<K, V>& kv)
	{
		//去重
		if (Find(kv.first))
		{
			return false;
		}

		//检查是否需要扩容
		if (_size * 10 / _table.size() >= 7)//负载因子设为0.7；
		{
			//扩容，需要重新映射。
			HashTable<K, V> newtable;
			newtable._table.resize(_table.size() * 2);//二倍扩
			for (const auto& e : _table)//将旧的移到新的。
			{
				if (e._state == EXIST)
				{
					newtable.Insert(e._kv);//插入逻辑和下面一致
				}
			}
			_table.swap(newtable._table);//交换新旧两表
		}

		Hash hs;//取K
		size_t hashi = hs(kv.first) % _table.size();//除留余数法算出下标
		while (_table[hashi]._state == EXIST)//若对应位置已有，则往后推
		{
			++hashi;
			hashi %= _table.size();
		}
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_size;
		return true;
	}

删除

注意：上面的查找函数的返回值为K值对应节点的地址，所以可以直接借助查找函数实现删除操作。
步骤如下：

调用Find并接受其返回值
若节点存在，则直接将该节点中的_state改为DELETE即算完成删除。
记得_size- -

闭散列的哈希表的增删查操作对数据的状态的处理都是接洽的，所以可以直接使用改变状态来进行伪删除从而达到删除效果。

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

哈希表开散列的实现

开散列的哈希表也有称为哈希桶的

哈希表的结构

在开散列的哈希表中，哈希表的每个位置实际上存储的是一个节点，即每个哈希桶中存储的数据实际上是一个节点类型，该节点类型除了存储所给数据之外，还需要存储一个节点指针用于指向下一个节点。也可以理解为vector中的每一个元素都为一串单链表。

template<class K, class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	HashNode(const pair<K,V>& kv)
		:_next(nullptr)
		,_kv(kv)
	{}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashBucket
{
public:
	//function

private:
	vector<Node*> _bucket;
	size_t _size;
};

开散列的哈希函数，构造函数和上面闭散列的实现是一致的。

查找

步骤：

计算得出哈希地址
查看该哈希地址上的单链表是否为空
单链表不为空，则遍历并比对K值

实现逻辑和闭散列是相同的，由于不需要状态标识符，实现起来更简单。

	Node* Find(const K& key)//返回数据类型
	{
		Hash hs;
		size_t hashi = hs(key) % _bucket.size();
		Node* cur = _bucket[hashi];
		while (cur)//存在则进行比对
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr;
	}

插入

步骤：

去重，不支持相同K值的元素
检查是否需要扩容
- 开散列的负载因子设为1，即插入元素等于桶数时才扩容
- 现在哈希表下挂的是单链表，扩容时直接将单链表的每一个节点重新映射到新表中的做法效率会更优，这样可以减少新表重新开节点和旧表释放节点这样多此一举的事情，直接将原有节点拿过来挂在新表上。
插入新节点，_size记得++

这里的插入为头插，尾插也行，看个人喜好。该过程比较重要的点就是在重新映射到新表时直接将旧表中的节点挂去新表，减少了重新开/释放节点的消耗。其余的就是单链表相关的操作，不熟悉的可参考——单链表的实现

bool Insert(const pair<K, V>& kv)
	{
		//去重
		if (Find(kv.first))
		{
			return false;
		}

		//检查是否需要扩容
		if (_size == _bucket.size())//负载因子为1；
		{
			//扩容，需要重新映射。
			vector<Node*> newbucket;//此时开的是vector
			newbucket.resize(_bucket.size() * 2);//扩容
			for (size_t i = 0; i < _bucket.size(); i++)
			{
				if (_bucket[i])//非空说明有数据
				{
					Node* cur = _bucket[i];//获取当前节点
					Node* next = nullptr;
					Hash hs;
					size_t newhashi;
					while (cur)
					{
						next = cur->_next;//先记录旧表的下一个节点
						newhashi = hs(cur->_kv.first) % newbucket.size();//计算在新表的位置
						cur->_next = newbucket[newhashi];//串联新表的下一节点
						newbucket[newhashi] = cur;//头插
						cur = next;//遍历旧表
					}
				}
			}
			_bucket.swap(newbucket);//交换新旧两表
		}
		//插入过程
		Hash hs;
		size_t hashi = hs(kv.first) % _bucket.size();
		Node* newnode = new Node(kv);
		//头插
		newnode->_next = _bucket[hashi];
		_bucket[hashi] = newnode;
		++_size;
		return true;
	}

了解过哈希表的插入之后，可以知道哈希表是无法保证表中元素是有序的，这也就是为什么unordered系列容器是无法保证容器中元素是有序的原因，因为其底层就是哈希表。无法做到像红黑树那样保证元素是有序的。

删除

步骤：

计算获取哈希地址
查找并判断节点是否为哈希表中桶的第一个节点
- 若删除节点为桶的第一个节点，需要改动表中的节点
- 若不是，直接让prev指向cur的next。
删除节点，_size- -

    bool Erase(const K& key)
	{
		Hash hs;
		size_t hashi = hs(key) % _bucket.size();
		Node* prev = nullptr;//前一节点
		Node* cur = _bucket[hashi];//当前节点
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				//需要检测是不是当前桶的头节点
				if (prev == nullptr)//为头节点
				{
					_bucket[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}

哈希表的表长建议是素数

减少冲突概率:

均匀分布：当哈希表的长度（即模数）为素数时，能够更均匀地分布哈希值，减少不同键产生相同哈希值的概率，即减少冲突。这是因为素数在取模运算中具有较少的因子，使得哈希值在哈希表中分布更加均匀。
避免周期性：质数作为除数可以减少哈希值的周期性，避免哈希值在某些位置上过于集中，从而进一步减少冲突

如：
假设有一个数列A: 1, 3, 5, 7, 9, 11, 13, 15，如果采用除留余数法构造哈希函数，并选取8作为模数，则这些数的哈希值将分别为1, 3, 5, 7, 1, 3, 5, 7，可以看出有明显的周期性，且由于2是8的因子，这些数之间的间隔（2）也导致了哈希值的冲突。而如果选取7作为模数（7是素数），则哈希值将分别为1, 3, 5, 0, 2, 4, 6，分布更加均匀，冲突减少

表长为8：

0	1	2	3	4	5	6	7
	1		3		5		7
	9		11		13		15

表长为7：

0	1	2	3	4	5	6
7	1	9	3	11	5	13
	15

所以为了提高哈希表的效率，在扩容时就不能简单的扩两倍了，这样的表长就不是素数了，所以提前存好一个间隔差距近似两倍的素数数组。如以下数组，其成员都为素数，且都以近似二倍的增长。

		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)
	{
		//素数序列
		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 i = 0;
		for (size_t i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		//return primeList[i];//理论上一定会在循环中有结果
	}

使用时在resize中调用即可。

		//newbucket.resize(_bucket.size() * 2);//二倍增长
		newbucket.resize(GetNextPrime(_bucket.size()));//素数数组