网站建设项目清单价格,大安网站建设,什么情况下需要建设网站,seo的概念哈希冲突解决
上一篇博客提到了#xff0c;哈希函数的优化可以减小哈希冲突发生的可能性#xff0c;但无法完全避免。本文就来探讨一下解决哈希冲突的两种常见方法#xff1a;闭散列和开散列
1.闭散列
闭散列也叫开放定址法#xff0c;发生哈希冲突时#xff0c;如果哈…哈希冲突解决
上一篇博客提到了哈希函数的优化可以减小哈希冲突发生的可能性但无法完全避免。本文就来探讨一下解决哈希冲突的两种常见方法闭散列和开散列
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 位置时停止表示探测失败。
这样一来就完美解决了上述问题。
线性探测的代码实现
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 哈希表中支持字符串的操作
template
struct HashFuncstring
{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};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class V, class HashFunc HashFuncKclass HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pairK, V kv){// 根据装载因子决定是否扩容if (_n * 10 / _table.size() 7){// 平衡因子0.7需要扩容扩容后需要重新插入size_t newSz _table.size() * 2;HashTableK, 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;}HashDataK, 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:vectorHashDataK, 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
#includeiostream
using namespace std;
#includestring
#includevector// 哈希函数采用除留余数法
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 哈希表中支持字符串的操作
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};namespace hash_bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass K, class V, class HashFunc HashFuncKclass HashTable{typedef HashNodeK, 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 pairK, V kv){if (Find(kv.first))return false;HashFunc hf;// 根据装载因子决定是否扩容if (_n _table.size()){size_t newSz _table.size() * 2;vectorNode* 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:vectorNode* _table; // 指针数组size_t _n 0; // 存储了多少个有效数据};
}
以上就是对哈希冲突的两种常见解决办法的介绍欢迎在评论区留言码文不易觉得这篇博客对你有帮助的可以点赞收藏关注支持一波~
