【C++】哈希表模拟：开散列技术与哈希冲突处理
| C++语法 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 命名空间 | 缺省参数与函数重载 | C++相关特性 | 类和对象-上篇 | 类和对象-中篇 |
| 类和对象-下篇 | 日期类 | C/C++内存管理 | 模板初阶 | String使用 |
| String模拟实现 | Vector使用及其模拟实现 | List使用及其模拟实现 | 容器适配器Stack与Queue | Priority Queue与仿函数 |
| 模板进阶-模板特化 | 面向对象三大特性-继承机制 | 面向对象三大特性-多态机制 | STL 树形结构容器 | 二叉搜索树 |
| AVL树 | 红黑树 | 红黑树封装map/set | 哈希-开篇 | 闭散列-模拟实现哈希 |
在上篇中，我们使用闭散列技术解决了哈希冲突并实现了哈希表。然而，我们发现闭散列并不理想，因此本篇将探讨如何通过开散列方法来处理哈希冲突。
🌈个人主页：是店小二呀
🌈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;
};
}
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！