【C++】哈希表模拟：开散列技术与哈希冲突处理

在这里插入图片描述

C++语法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
命名空间	缺省参数与函数重载	C++相关特性	类和对象-上篇	类和对象-中篇
类和对象-下篇	日期类	C/C++内存管理	模板初阶	String使用
String模拟实现	Vector使用及其模拟实现	List使用及其模拟实现	容器适配器Stack与Queue	Priority Queue与仿函数
模板进阶-模板特化	面向对象三大特性-继承机制	面向对象三大特性-多态机制	STL 树形结构容器	二叉搜索树
AVL树	红黑树	红黑树封装map/set	哈希-开篇	闭散列-模拟实现哈希

在上篇中，我们使用闭散列技术解决了哈希冲突并实现了哈希表。然而，我们发现闭散列并不理想，因此本篇将探讨如何通过开散列方法来处理哈希冲突。

请添加图片描述
Alt
🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏：初阶数据结构
🌈高阶数据结构专栏：高阶数据结构
🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志我自踏雪至山巅请添加图片描述

文章目录

一、开散列(哈希桶)
二、实现哈希表
- 2.1 哈希表基本构架
- 2.2 哈希表插入数据
- 2.3 哈希表析构函数
- 2.4 哈希表扩容
- 2.5 哈希表删除数据
- 2.6 哈希桶中查找
三、HashTable.h

一、开散列(哈希桶)

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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素

二、实现哈希表

2.1 哈希表基本构架

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 ch : key){hash *= 131;hash += ch;}return hash;}
};
namespace hash_buck
{template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V> _next;};template<class K, class V,class Hash = HashFunc<K>>class HashTable{public:typedef HashNode<K, V> Node;HashTable(){_tables.resize(10，nullptr);}private:vector<Node*> _tables;//vector<list<..>> _tables;size_t _n = 0;};
}

这里如果想实现哈希桶结构，可以使用一个个节点连接起来或者直接套上一个链表容器。这里为了更好地实现迭代器，我们选择第一种方式，第二种方式实现迭代器有一丝麻烦。

开散列中每个桶中放的都是发生哈希冲突的元素，并没有顺序之分。

2.2 哈希表插入数据

在这里插入图片描述

bool Insert(const pair<K, V>& kv)
{Hash hs;size_t hashi = hs(kv.first) % _tables.size();//进行头插操作Node* newnode = new Node(kv);_tables[hashi]->_next = newnode;_tables[hashi] = newnode;
}

这里链表节点只需要单纯地存储数据，那么只需要设计单链表即可，没有必要设双向链表。对于单链表插入数据，一般推荐采用头插，由于尾插需要找尾比较麻烦。

2.3 哈希表析构函数

这里涉及堆上空间资源的开辟，一般需要涉及析构函数进行资源处理。

由于vector容器元素为内置类型，析构函数对内置类型不进行处理，那么就导致指向空间没有得到释放，需要显式写析构函数，完成资源释放。

~HashTable()
{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}}
}

2.4 哈希表扩容

由于哈希桶去解决哈希冲突对于哈希表空间需要相对比较小，不同于开发定址法去解决哈希冲突占用表内空间，而是表中一个指针指向一个空间。

【负载因子满足1即可扩容】:_n == _tables.size()

【第一个方案】:复用Insert完成CV操作

//扩容逻辑if (_n == _tables.size()){//这里可以忽略类型HashTable NewTable;NewTable._tables.resize(n * 10);//CV工作for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){NewTable.Insert(_tables[i]._kv);cur = cur->_next;}}_tables.swap(NewTable);}

【缺陷】:如果存在一万个节点，意味着需要复制一万个节点又要释放一万个节点，显得很浪费

【第二个方案】:直接将节点拿下来

在这里插入图片描述

if (_n == _tables.size())
{vector<Node*> NewTable(n * 10, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;cur->_next = _tables[i];_tables[i] = cur;cur = cur->_next;}_tables[i] = nullptr;}_tables.swap(NewTable);
}

关于这段代码是比较难懂，每个指针指向一块空间，先cur->next = newTables[hashi]抓住新表的位置，newTables[hashi] = cur新表将旧表节点拿下来，可以好好理解拿下来的逻辑，得到了这个地址，这个地址指向一块节点。

这里会导致newTables[hashi]和_tables[i]共同指向一块空间，虽然不会去使用旧表去影响到新表，为了保险起见，可以将旧表这块位置指针置空。

2.5 哈希表删除数据

bool Erase(const K& key)
{Hash hs;size_t hashi = hs(kv.first) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;
}

这里删除数据，无非需要考虑两种情况的删除，一种是删除第一个节点，另一种是删除其他节点prev->_next = cur->_next。在删除节点需要前后兼顾，保存下前驱指针指向节点。

2.6 哈希桶中查找

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

三、HashTable.h

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 ch : key){hash *= 131;hash += ch;}return hash;}
};namespace hash_bucket
{template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V> _next;};template<class K, class V,class Hash = HashFunc<K>>class HashTable{public:typedef HashNode<K, V> Node;HashTable(){_tables.resize(10,nullptr);}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}}}bool Insert(const pair<K, V>& kv){Hash hs;size_t hashi = hs(kv.first) % _tables.size();//扩容逻辑//if (_n == _tables.size())//{//	//这里可以忽略类型//	HashTable NewTable;//	NewTable._tables.resize(n * 10);//	//	//CV工作//	for (size_t i = 0; i < _tables.size(); i++)//	{//		Node* cur = _tables[i];//		while (cur)//		{//			NewTable.Insert(_tables[i]._kv);//			cur = cur->_next;//		}//	}//	_tables.swap(NewTable);//}if (_n == _tables.size()){vector<Node*> NewTable(n * 10, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插新表的位置size_t hashi = hs(kot(cur->_data)) % NewTable.size();cur->_next = NewTable[hashi];NewTable[hashi] = cur;cur = cur->_next;}_tables[i] = nullptr;}_tables.swap(NewTable);}//进行头插操作Node* newnode = new Node(kv);_tables[hashi]->_next = newnode;_tables[hashi] = newnode;++_n;}Node* Find(const K& key){Hash hs;size_t hashi = hs(kv.first) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return &cur->_kv.first;}else{cur = cur->_next;}}return nullptr;}bool Erase(const K& key){Hash hs;size_t hashi = hs(kv.first) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;size_t _n = 0;};
}