【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;elsecout << 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;}}elsecout << i << "：-->NULL";cout << endl;}}private:vector<Node*> _table; // 指针数组size_t _n = 0; // 存储了多少个有效数据};
}

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