【C++】哈希表

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

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

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

哈希冲突

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

哈希函数

哈希函数就是把关键字转化为对应哈希地址。引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

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

常用的哈希函数：

1. 直接定址法
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
   优点：简单、均匀
   缺点：需要事先知道关键字的分布情况
   使用场景：适合查找比较小且连续的情况

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

哈希表

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

闭散列

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

怎么找下个空位置呢？

1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
2. 二次探测：线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位
   置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i = 1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

线性探测和二次探测实现方法类似，只有找空位置的地方有点区别，我们以实现线性探测为例。我们使用的是除留余数法。每个Key对表的大小取余，确定对应的哈希地址。

一个位置的状态可能有三种，空、存在、删除，有很多人有一个误区，觉得空状态和删除状态是一样的，其实他们差别挺大的，为什么这么说呢？我们看下面场景

我们把6删除了。

此时如果找44，遇到空就会停止，那44我们就无法找到，所以删除状态是必须的，我们找查找时是遇到空就停止，并且删除44也是无法成功的，与查找同理。

结构
我们需要枚举，来表示三个状态，哈希表本质就是用数组实现的，我们这里可以直接使用vector，我们把状态和需要存储的值用一个结构体封起来，存到vector中就可以了。

enum Status
{
   
	EMP,//空
	DEL,//删除
	EXI//存在
};


template <class K, class V>
struct HashNode
{
   
	//表示状态
	Status _s;
	pair<K, V> _kv;
};

template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
   
private:
	vector<HashNode<K, V>> _v;
	//表示存储了多少个数据
	size_t _n = 0;
	//为了解决不能被取余的值
	Hash hs;
};

插入

首先需要通过哈希映射，所以要对表的大小取余，然后在这个对应的位置去把值放进去，并且把状态改为存在。但是有一个问题，这个位置有可能已经被有的值映射过了，这是就需要使用线性探测，我们要从这个位置开始找到一个状态为空或者删除的位置，然后才能把值放进去。还有一个问题就是，我们什么时候扩容呢？

有一个东西叫做负载因子，负载因子 = 数据的个数 / 表的大小，我们通过控制负载因子来控制扩容的时机，如果负载因子控制的太大，那么出现哈希冲突的概率就太大了，但是如果负载因子太小了，那么对于空间的浪费太多了，所以负载因子的选择对哈希表的影响还是挺大的。闭散列我们一般把负载因子控制在0.7.

那么怎么扩容呢？
我们不能再原表直接扩容，因为扩容会打乱映射关系，所以我们需要建立一个新表，然后把新表的大小初始化成旧表的二倍，然后遍历旧表，把旧表的数据重新插入映射到新表，新表的内容就是我们需要的，所以我们此时可以考虑直接swap两个新旧表中的vector，这样就可以完美的符合我们的需求。

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

	if (_n * 10 / _v.size() == 7)
	{
   
		int newsize = _v.size() * 2;
		HashTable<K, V> newTable;
		newTable._v.resize(newsize);

		for (size_t i = 0; i < _v.size(); i++)
		{
   
			if (_v[i]._s == EXI)
			{
   
				newTable.Insert(_v[i]._kv);
			}
		}

		_v.swap(newTable._v);
	}

	size_t hashi = hs(kv.first) % _v.size();
	//寻找下个是删除或者空的位置
	while (_v[hashi]._s == EXI)
	{
   
		hashi++;
		//防止越界
		hashi %= _v.size();
	}

	_v[hashi]._kv = kv;
	_v[hashi]._s = EXI;
	_n++;
	return true;
}

删除和查找

查找同样需要映射，然后从当前位置开始查找，只要不为空就一直找，如果找到了Key并且状态为存在，我们就可以直接返回当且的节点，如果到空都没找到，就返回nullptr。
删除需要先查找，查找到直接改状态就可以，不然就返回false。

HashNode<K,V>* Find(const K& k)
{
   
	size_t  hashi = hs(k) % _v.size();
	while (_v[hashi]._s != EMP)
	{
   
		if (_v[hashi]._s == EXI && _v[hashi]._kv.first == k)
		{
   
			return &_v[hashi];
		}
		hashi++;
		hashi %= _v.size();
	}

	return nullptr;
}

bool Erase(const K& k)
{
   
	HashNode<K, V>* f = Find(k);

	if (f)
	{
   
		f->_s = DEL;
		_n--;
		return true;
	}
	else
	{
   
		return false;
	}
}

以上情况如果我们存储整型的话当然是没问题的，但是如果我们存储的是string等不能直接被取余的类型怎么办？

这是我们就可以传一个仿函数，来把不能不能直接被取余的类型转化为整型。

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

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

一般我们会特化一个string的，因为字符串是最常见的。我们这里字符串转化为整型时BKDR法。

开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。开散列中每个桶中放的都是发生哈希冲突的元素。
这里实现我们直接使用vector就可以，因为每个桶都是哈希冲突的元素，所以结构需要一个链接下一个节点的指针。

结构

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

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

template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
   
	typedef HashNode<K, V> Node;
private:
	vector<Node*> _tables;
	size_t _n;
	Hash hs;
};

这里的插入删除查找都是直接映射然后都是单链表的操作，插入因为哈希本来就是无序的所以我们直接头插就行了，只有扩容时需要我们重点说一下，我们可以跟上面闭散列一样，建立一个新表，然后把节点重新插入一下，但是这里会产生很多的浪费，因为原来表的节点重现插入以后，就会被释放了，有没有一种办法把原来的节点直接拿到新表呢？
我们遍历原表时，再拿到一个节点后直接通过映射把他的链接关系连接到新表中去就可以实现这样的效果，只不过需要我们提前记录一下下一个节点，不然会找不到下一个节点。

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

开散列

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

template<>
struct HashFunc<string>
{
   
	size_t operator()(const string& s)
	{
   
		size_t sum = 0;
		for (auto e : s)
		{
   
			sum = sum * 31 + e;
		}
		return sum;
	}
};
template <class K, class V>
struct HashNode
{
   
	pair<K, V> _kv;
	HashNode* _next;

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

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

	~HashTable()
	{
   
		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;
		}
	}
	bool Insert(const pair<K,V>& kv)
	{
   
		if (Find(kv.first))
		{
   
			return false;
		}

		if (_n == _tables.size())
		{
   
			//需要扩容
			vector<Node*> newtables;
			newtables.resize(2 * _tables.size());

			for (size_t i = 0; i < _tables.size(); i++)
			{
   
				Node* cur = _tables[i];
				while (cur)
				{
   
					Node* next = cur->_next;
					size_t hashi = cur->_kv.first % newtables.size();
					cur->_next = newtables[hashi];
					newtables[hashi] = cur;

					cur = next;
				}
				_tables[i] = nullptr;
			}

			_tables.swap(newtables);
		}

		size_t hashi = hs(kv.first) % _tables.size();
		Node* cur = new Node(kv);
		cur->_next = _tables[hashi];
		_tables[hashi] = cur;
		_n++;
		return true;
	}

	Node* Find(const K& k)
	{
   
		size_t hashi = hs(k) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
   
			if (cur->_kv.first == k)
			{
   
				return cur;
			}

			cur = cur->_next;
		}

		return nullptr;
	}

	bool Erase(const K& k)
	{
   
		size_t hashi = hs(k) % _tables.size();

		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
   
			if (cur->_kv.first == k)
			{
   
				if (prev==nullptr)
				{
   
					_tables[hashi] = cur->_next;
				}
				else
				{
   
					prev->_next = cur->_next;
				}
				delete cur;
				return true;
			}
			cur = cur->_next;
		}

		return false;
	}
private:
	vector<Node*> _tables;
	size_t _n;
	Hash hs;
	};

开散列与闭散列比较

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