【C++】哈希冲突的解决办法：闭散列 与 开散列

哈希冲突解决

上一篇博客提到了，哈希函数的优化可以减小哈希冲突发生的可能性，但无法完全避免。本文就来探讨一下解决哈希冲突的两种常见方法：闭散列和开散列

1.闭散列

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

1.1线性探测

插入的情况

还是上述这种情况，当我想插入元素13时，通过哈希函数计算出哈希地址为3，但此时该位置已经存放了元素3，发生了哈希冲突。

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

由于下标4、5都有元素存放，此时找到的空位置下标为6，于是在下标6处存放元素13。

但是哈希表中的空间终究是有限的，空间不够时我们需要进行扩容。但如果等到表被填满再进行扩容的话，这样一来搜索的时间复杂度更趋向于O(N)了，因为表中数据存放越满，理论哈希地址与实际哈希地址相隔越远，最坏情况就近乎O(N)。所以我们需要更早地进行扩容。我们规定在什么情况下进行扩容呢？这里要引入一个载荷因子的概念。

散列表的载荷因子： α = 表中的元素个数 / 散列表的长度

载荷因子标记了需要进行扩容的情况。我们可以得知，载荷因子α越大，散列表越满，而散列表越满，产生冲突的可能性越大；反之α越小，产生冲突的可能性越小。但是不是载荷因子越小越好呢，并不是，载荷因子太小，会造成空间的极大浪费，因此对于开放定址法，载荷因子应限制在0.7-0.8 之间。也就是散列表的空间被利用了70%-80%时，就可以进行扩容了。

扩容之后，由于地址数增加了，关键码通过哈希函数求得的哈希地址也随之改变了，所以需要改变映射关系，改变映射关系之后，原先冲突的元素可能就不再冲突了：

原先元素13，元素17分别和元素3，元素7发生冲突，但是扩容之后，映射关系重新调整，它们就不再冲突了，这就是为什么即使哈希结构不能完全保证搜索的时间复杂度为O(1)，但也可以近似于O(1)。

搜索的情况

搜索元素时，同样将关键码通过哈希函数计算出理论上的哈希地址，但是该地址处可能发生哈希冲突，若发生哈希冲突，则需要继续向后探测，当我们遇到空时，探测结束，说明搜索失败。

但是碰到下面这种情况呢：

我们搜索的目标元素是：13，由于13前一个位置的元素25被删除，该位置为空，所以会导致探测失败，但实际上13是存在的。所以我们在采用闭散列处理哈希冲突时，不能随意对已有元素进行物理删除，若直接删除，会影响其他元素的搜索。因此线性探测采用标记的的伪删除法来删除元素。

对哈希表每个空间给个标记：
EMPTY（此位置空）， EXIST（此位置已经有元素）， DELETE（元素已经删除）

enum State{EMPTY, EXIST, DELETE}; 

在删除元素时，只需要把该哈希位置的标记从 EXIST 改成 DELETE 即可；

在搜索元素时，探测到标记为 EMPTY 位置时停止，表示探测失败。

这样一来就完美解决了上述问题。

线性探测的代码实现：

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;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

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

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

		bool Insert(const pair<K, V>& kv)
		{
			// 根据装载因子决定是否扩容
			if (_n * 10 / _table.size() >= 7)
			{
				// 平衡因子>=0.7，需要扩容，扩容后需要重新插入
				size_t newSz = _table.size() * 2;
				HashTable<K, V, HashFunc> newHT;
				newHT._table.resize(newSz);
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
						newHT.Insert(_table[i]._kv);
				}
				_table.swap(newHT._table);
			}
			// 插入过程
			HashFunc hf;
			size_t hashi = hf(kv.first) % _table.size();
			while (EXIST == _table[hashi]._state)
			{
				++hashi;
				hashi %= _table.size();
			}
			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._kv.first == key)
					return &_table[hashi];
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			if (Find(key))
			{
				Find(key)->_state = DELETE;
				return true;
			}
			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._state == EXIST)
					cout << i << " -> " << _table[i]._kv.first << "," << _table[i]._kv.second << endl;
				else
					cout << i << " -> NULL" << endl;
			}
		}

	private:
		vector<HashData<K, V>> _table;
		size_t _n = 0;  // 表中存储数据个数
	};
}

1.2二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式是挨个往后去找。二次探测就避免了这个问题，在二次探测中，若初始哈希位置 Hash(Key) = h 已被占用，则探测下一个位置的公式为：h(i) = (h + i^2) % m（其中i = 1,2,3,...）。

插入元素13时，与元素3产生冲突，通过二次探测，找到新的哈希位置7进行插入。 

2. 开散列

概念

开散列法又叫链地址法(开链法)，它解决哈希冲突的办法是：将具有相同哈希地址的元素通过单链表链接，而哈希表中存放的是各链表的头节点。

插入的情况：

初始哈希表中存放都是空指针。需要进行元素插入时，首先根据哈希函数计算出对应的哈希地址，然后为该元素开辟一块地址空间（存放元素数据_data 以及_next指针用于链接冲突的元素）

如果该哈希地址为空，则存放元素节点指针：

如果当前地址发生哈希冲突，则使用头插的方法，即新节点的_next指针指向旧节点，哈希表中更新头结点指针：

与开散列不同的是，由于插入的元素通过单链表的方式进行链接，哈希表中只需要存放各链表头结点指针，所以哈希表不需要扩容就可以实现任意元素的插入。但是不要忘记我们的初衷，哈希表是为了提高数据的搜索效率的，因此我们需要控制链表的长度（链表越长，搜索效率越低下），原理和闭散列一样，也是通过对哈希表扩容，实现元素的分散存储。

在开散列中，我们通常将载荷因子定为1 ，即表中元素个数等于散列表长度时，进行扩容。扩容之后需要更新哈希地址，重新进行存储。

下面是扩容后的情况（仅演示地址更新情况，其实该散列还不需要扩容）：

删除的情况：

删除指定元素时，我们需要对该元素存放节点进行空间释放，释放后要注意更新链表的链接情况 

代码实现

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

// 哈希函数采用除留余数法
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;
	}
};

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

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

	template<class K, class V, class HashFunc = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_table.resize(10, nullptr); // 显式初始化
		}

		~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;
			}
			_n = 0;
		}

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

			HashFunc hf;
			// 根据装载因子决定是否扩容
			if (_n == _table.size())
			{
				size_t newSz = _table.size() * 2;
				vector<Node*> newTB ;
				newTB.resize(newSz, nullptr);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						// 头插到新表
						size_t newi = hf(cur->_kv.first) % newSz;
						cur->_next = newTB[newi];
						newTB[newi] = cur;

						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newTB);
			}
			// 插入操作
			size_t hashi = hf(kv.first) % _table.size();
			Node* newNd = new Node(kv);
			newNd->_next = _table[hashi];
			_table[hashi] = newNd;
			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			if (!cur)
				return false;
			if ( cur->_kv.first == key)
			{
				_table[hashi] = cur->_next;
				return true;
			}
			Node* prev = _table[hashi];
			cur = cur->_next;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					prev->_next = cur->_next;
					delete cur;
					cur = nullptr;
					return true;
				}
				cur = cur->_next;
				prev = prev->_next;
			}
			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					cout << i << "：";
					Node* cur = _table[i];
					while (cur)
					{
						cout << "-->(" << cur->_kv.first << "," << cur->_kv.second << ")";
						cur = cur->_next;
					}
				}
				else
					cout << i << "：-->NULL";
				cout << endl;
			}
		}

	private:
		vector<Node*> _table; // 指针数组
		size_t _n = 0; // 存储了多少个有效数据
	};
}

以上就是对哈希冲突的两种常见解决办法的介绍，欢迎在评论区留言，码文不易，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉