概述
文章目录
- 哈希桶的整体结构交代
- 迭代器的封装与实现
- 查找接口的实现
- 插入接口的实现
- 删除接口的实现
- hpp文件代码展示
开散列也称链地址法，与闭散列不同，开散列解决哈希冲突的方式是：将冲突的数据用链表维护起来，或者说开散列中不存在哈希冲突，没有了闭散列那样的“你占用我的空间，我占用他的空间”的情况，反而是用一个单链表维护发生冲突的数据，开散列还有一个形象的名字：哈希桶，单链表维护的一串数据是具有相同key值的键值对，也是桶的一块木板。当然哈希桶也有弊端，可能会发生哈希桶的某一块木板过长，或者所有的木板太长，我们知道单链表（木板）越长查找效率越低，所以哈希桶也需要维护负载因子，使负载因子处于一个均衡的状态，从而使哈希桶的查找效率处于一个稳定的状态。当然了在极端情况下，我们可以用红黑树代替单链表，使查找相同哈希值数据的时间复杂度为O(logN)
哈希桶的整体结构交代
首先哈希桶的本质是一个数组，一个存储节点地址的数组，可以认为数组的每个元素是一个单链表的头指针，其次同样重要的是需要维护的负载因子，所以至少要有一个变量记录哈希桶中的节点数量。接着的问题是哈希桶中的数组存储的是什么类型的变量？刚才说了数组的每个成员都是单链表的头指针，所以数组成员的类型是一个指针类型，指针指向的是什么类型？答案是一个节点类型，拥有指针域和数据域，数据域存储一个泛型，指针域存储下一个节点的地址。至此我们把梳理的结构声明出来
template <class T>
struct HashBucketData
{
// 节点的数据域和指针域
T _data;
HashBucketData* _next;
};
template <class K, class T，class KeyOfT>
class HashBucket
{
typedef HashBucketData<T> Data;
private:
vector<Data*> _bucket; // 存储指针的数组
size_t _n; // 用来维护负载因子的变量
};
解释一下它们的模板参数，节点的模板参数T，表示一个泛型，因为哈希桶作为unordered_set和unordered_map的底层结构，存储的可能是一个键值对还可能只是一个key值，为了模板的通用性，这里使用T接收上层结构的类型，并且需要上层提供仿函数以提取出泛型T中的key值。所以HashBucket有一个KeyOfT的模板参数，至于为什么还需要一个模板参数K接收key的类型，这是因为一些成员函数需要使用K作为形参的类型
实现了整体结构，接下来就是容器的操作接口，增删查改
插入函数需要接收泛型T类型的数据，将其插入然后返回bool值表示插入是否成功
删除函数只需要接收一个key值，根据key值查找对应的泛型是否存在，最后返回fool表示删除是否成功
查找函数也是只要接收一个key值，根据key值查找对应的泛型是否存在，最后返回的是一个指向该泛型的迭代器
修改函数可以不用特地的设置接口，用户通过接收查找函数返回的迭代器就能修改容器的值
template <class K, class T, class KeyOfT, class HashTrans>
class HashBucket
{
typedef HashBucketData<T> Data;
public:
bool Insert(const T& data); // 增
bool Erase(const K& key); // 删
iterator Find(const K& key); // 查
private:
vector<Data*> _bucket; // 存储指针的数组
size_t _n = 0; // 用来维护负载因子的变量
};
当用户传入一个泛型值，我们需要用这个泛型值构造一个节点，将其存储到节点的数据域并将其指针域置空，构造节点就需要调用HashBucketData类的构造函数，注意需要调用有形参的构造函数，将数据传入节点。无参的构造函数是针对vector的resize写的，数组需要扩容时，会调用数组成员的默认构造函数，虽然不知道指针类型的默认构造是否会初始化为空指针，但我们还是显式的写一下，因为指针是否为空是该节点是否指向了下一个节点的表征，就算插入节点时我们会将指针置空，但还是严谨一些好
template <class T>
struct HashBucketData
{
// 节点的数据域和指针域
T _data;
HashBucketData* _next;
HashBucketData(T data)
:_data(data)
,_next(nullptr)
{}
HashBucketData()
:_next(nullptr)
{}
};
至于HashBucket需不需要构造函数与析构？答案是不需要构造，但需要析构函数，解释一下为什么：HashBucket不写构造函数，编译器会生成一个默认构造函数，对于其vector成员，因为它是自定义类型，所以默认构造函数会调用它的默认构造函数，因为它又是STL中的容器，我们不用当心它的默认构造是否有问题，对于内置类型变量_n，我们给了它初始值0，所以编译器生成的默认构造会用0初始化这个变量。总结一下，因为vector的默认构造函数已经写好了，内置类型的默认值我们也给了，所以用编译器生成的默认构造函数不会有问题
那为什么要写析构函数呢？对于自定义类型成员_bucket，默认析构函数会调用_bucket的析构函数，对于内置类型_n默认构造函数不会管他，因为出了作用域其空间随着栈帧自动释放。但是_bucket的析构只会析构自己申请的资源，也就是存储指针的数组资源，但是对于vector的成员Data*，它可没有默认析构函数，因为它是内置类型，资源会自动释放，但是它是一个指向堆区资源的指针啊，存储了节点的数据，它的资源也需要释放啊，编译器可不知道一个指针指向的资源是不是动态开辟的。所以对于指针类型，我们需要根据其指向的资源决定是否要为它实现析构函数。由于Data节点的资源是new出来的，所以我们需要释放指针指向的资源。
但是我们不能在HashBucketData类中实现析构函数，释放自己（delete this），这会导致无限递归析构函数，最终栈溢出（或者二次释放使得程序崩溃）。我们应该要在封装了HashBucketData的HashBucket类中实现对HashBucketData类的对象的资源释放，这个析构函数主要是释放节点的资源，对于存储节点的数组资源就由vector自己释放（调用完自己的析构函数，由于其成员的生命周期也结束了，所以vector的析构函数也会被调用，存储节点的数组资源也会被释放）
这些都是类和对象的基础知识点，属于是学起来简单，真正用起来却绕来绕去。这里实现一下HashBucket类的析构，遍历所有单链表的头指针，进而遍历所有单链表，将所有的节点释放即可
template <class K, class T, class KeyOfT, class HashTrans>
HashBucket<K, T, KeyOfT, HashTrans>::~HashBucket()
{
for (size_t i = 0; i < _bucket.size(); ++i)
{
Data* cur = _bucket[i];
// 当头指针不为空，进入单链表遍历
while (cur)
{
Data* next = cur->_next;
delete cur;
cur = next;
}
// 释放后记得置空，虽然没什么必要，但是好习惯
_bucket[i] = nullptr;
}
}
迭代器的封装与实现
除了上面这些，我们还需要先定义一个迭代器，将节点的地址进行封装，使迭代器解引用后得到节点的数据域引用，并且支持比较，自增++等等功能。先交代迭代器的整体结构：首先迭代需要封装节点的地址，所以这里需要一个Data类型的指针变量，然后因为迭代器需要++，当遍历完一个单链表后，要怎么遍历下一个单链表？所以我们需要封装一下哈希桶的指针，当一个单链表遍历完，通过哈希桶的指针查找下一个单链表的头指针，也就是数组的下一个元素所保存的数据。当然如果单链表没有遍历完，将迭代器指向下一个节点就可以了
下面是迭代器的封装与接口定义，因为哈希桶的迭代器是一个单向迭代器，只支持++操作，并且++也是迭代器中最重要的操作，具体实现就不再阐述，注释已经很详细了
template <class K, class T, class KeyOfT, class HashTrans>
class __HashIterator
{
typedef HashBucketData<T> Data;
typedef HashBucket<K, T, KeyOfT, HashTrans> Bucket;
typedef __HashIterator<K, T, KeyOfT, HashTrans> Self;
public:
__HashIterator(Data* pnode, Bucket* pbucket) :_pnode(pnode), _pbucket(pbucket) {}
Data& operator*() { return _pnode->_data; }
Data* operator->() { return &(_pnode->_data); }
Self& operator++(); // 先声明，在类外实现
bool operator==(const Self& v) { return _pnode == v._pnode };
bool operator!=(const Self& v) { return _pnode != v._pnode };
private:
Data* _pnode; // 封装的节点的地址
Bucket* _pbucket; // 封装的哈希桶的地址
};
// 迭代器的++迭代操作
template <class K, class T, class KeyOfT, class HashTrans>
typename __HashIterator<K, T, KeyOfT, HashTrans>::Self& __HashIterator<K, T, KeyOfT, HashTrans>::operator++()
{
Data* cur = _pnode;
if (cur == nullptr) // 当迭代器指向空时，直接返回
{
return *this;
}
// 仿函数对象的定义，key取出泛型的key值，trans将key值转换成哈希值
KeyOfT key;
HashTrans trans;
if (cur->_next == nullptr) // 当前迭代器指向链表的最后一个节点，需要使迭代器指向下一个链表的头指针
{
// 先计算当前迭代器在数组中的位置
size_t hashi = trans(key(_pnode->_data)) % _pbucket->_bucket.size();
// 找一个有节点的位置
while (++hashi < _pbucket->_bucket.size() && _pbucket->_bucket[hashi] == nullptr){ }
// 如果遍历完整个桶还没有找到节点，修改迭代器为空再返回
if (hashi == _pbucket->_bucket.size())
{
_pnode = nullptr;
return *this;
}
// 走到这说明找到了，修改迭代器并将其返回
_pnode = _pbucket->_bucket[hashi];
return *this;
}
// 如果迭代器没有指向链表的尾部，遍历到下一个节点就行
_pnode = _pnode->_next;
return *this;
}
查找接口的实现
插入接口需要调用查找接口以避免键值冗余，删除接口也需要调用查找接口先查找数据再删除数据，所以我们先实现查找接口。我们知道哈希桶的本质是一个指针数组，如果数组成员为空，说明该哈希值下没有节点，如果数组成员不为空，那么我们就遍历这个单链表，查找是否有相同key值的节点
template <class K, class T, class KeyOfT, class HashTrans>
typename HashBucket<K, T, KeyOfT, HashTrans>::iterator HashBucket<K, T, KeyOfT, HashTrans>::Find(const K& key)
{
// 如果桶中没有数据直接返回
if (_bucket.size() == 0)
{
return iterator(nullptr, this);
}
// 仿函数对象的定义，将key值转换成整数
HashTrans trans;
// 先计算当前迭代器在数组中的位置
size_t hashi = trans(key) % _bucket.size();
Data* cur = _bucket[hashi];
while (cur) // 遍历这个单链表查找key值对应的节点
{
if (cur->_data == key)
{
// 用当前节点的地址构造一个迭代器
return iterator(cur, this);
}
cur = cur->_next;
}
// 遍历完单链表还是没有找到，说明节点不存在，返回空迭代器
return iterator(nullptr, this);
}
插入接口的实现
插入接口要额外考虑的就是负载因子的维护了，插入前先检查负载因子是否超过了指定的值，如果超过了就需要对数组进行扩容，扩容就涉及到重新映射新的哈希数组的问题了。容易实现的重新映射方式呢，就是再创建一个新的哈希桶，然后遍历旧哈希桶的所有值，将它们重新插入到新的哈希桶中，插入完成将新哈希桶的数组与旧哈希桶的数组进行交换，此时旧的哈希桶旧完成了数组的扩容。其中重新插入节点时，不应该根据data数据重新new一个节点插入，而应该移动原有的节点，能少调用该new就少调用，因为new会消耗程序的性能，直接移动可以提高程序的运行效率。
在检查扩容前还需要检查键值冗余，如果key值存在，函数直接返回不进行插入
template <class K, class T, class KeyOfT, class HashTrans>
bool HashBucket<K, T, KeyOfT, HashTrans>::Insert(const T& data)
{
// 仿函数对象的定义
KeyOfT key;
HashTrans trans;
iterator it = Find(key(data));
if (it._pnode) // 出现了键值冗余
{
return false;
}
if (_bucket.size() == 0 || _n * 10 / _bucket.size() >= 7) // 负载因子的维护，扩容
{
// 计算新桶的大小
size_t new_size = _bucket.size() == 0 ? 10 : 2 * _bucket.size();
// 新桶的创建与空间开辟
HashBucket new_bucket;
new_bucket._bucket.resize(new_size);
// 遍历旧表完成节点转移
for (size_t i = 0; i < _bucket.size(); ++i)
{
Data* cur = _bucket[i];
// 当头指针不为空，进入遍历单链表
while (cur)
{
Data* next = cur->_next;
// 获取新的哈希值
size_t new_hashi = trans(key(cur->_data)) % new_size;
// 头插操作
cur->_next = new_bucket._bucket[new_hashi];
new_bucket._bucket[new_hashi] = cur;
// 更新遍历旧表的cur
cur = next;
}
_bucket[i] = nullptr; // 好习惯，但这里不置空是真的会出问题
}
// 交换完成后将新旧表交换
_bucket.swap(new_bucket._bucket);
}
// 获取哈希值
size_t hashi = trans(key(data)) % _bucket.size();
// 构造节点
Data* new_node = new Data(data);
// 将节点头插
new_node->_next = _bucket[hashi];
_bucket[hashi] = new_node;
// 记得负载因子的维护
++_n;
return true;
}
删除接口的实现
因为节点的资源是通过new得到的，所以删除节点时我们需要用delete归还资源。那这里可以复用Find函数吗？可以是可以，就是Find函数已经写死，单链表的删除需要记录prev，cur，next三个节点，这样会比较简单，只有cur和next节点也可以，拷贝next的data值到cur中，将next删除就行，只是这样的话还需要考虑要删除的节点cur是最后一个节点的问题（可以拷贝链表的第一个节点的data值到cur上，然后做一个链表的头删，但这又需要计算当前节点的哈希值，因为Find函数只返回一个迭代器，我们只知道要删除节点的地址）。所以记录prev节点的删除较为简单，读者可以自行实现，我这里实现较复杂的拷贝删除
template <class K, class T, class KeyOfT, class HashTrans>
bool HashBucket<K, T, KeyOfT, HashTrans>::Erase(const K& key)
{
HashTrans trans;
iterator dele_it = Find(key);
// 要删除的值不存在，函数直接返回
if (dele_it._pnode == nullptr)
{
return false;
}
// 删除节点的保存
Data* dele_node = dele_it._pnode;
if (dele_node->_next) // 删除的节点不是链表的尾节点
{
// 要删除dele_node节点，转而删除其下一个节点，但在删除之前要维护好链表结构
// 使当前节点指向下一个节点的下一个节点，并且拷贝下一个节点的值给自己
// 最后删除下一个节点
Data* next = dele_node->_next; // 保存下一个节点
Data* next_next = next->_next; // 保存下下个节点
dele_node->_data = next->_data; // 值的拷贝
dele_node->_next = next_next;
delete next;
}
else
{
// 删除的节点是链表的尾节点
// 计算该节点在哈希桶中的哈希值
size_t hashi = trans(key) % _bucket.size();
// 要删除的节点是链表的唯一成员，需要修改头指针
if (_bucket[hashi] == dele_node)
{
delete dele_node;
_bucket[hashi] = nullptr;
}
else
{
// 不是唯一成员，将第一个节点的值拷贝给自己，然后头删
dele_node->_data = _bucket[hashi]->_data;
// 头删
Data* second = _bucket[hashi]->_next;
delete _bucket[hashi];
_bucket[hashi] = second;
}
}
// 记得负载因子的维护
--_n;
return true;
}
主要的逻辑已经通过注释解释清楚，这里不再赘述。至于修改接口的实现，用户可以调用查找函数，通过其返回的迭代器修改数据，这里也不再单独实现，至此开散列的大致结构实现完成
hpp文件代码展示
这个模拟实现的开散列结构经过测试是可以使用的，没有严重的bug，这里把所有代码展示出来，需要注意的一点是将迭代器声明为HashBucket的友元类，使迭代器可以访问HashBucket的私有成员
至于HashBucket的后两个模板参数，分别是提取key值的KeyOfT和将其他类型转换成可以取模的整数的HashTrans，两个参数都有默认参数，如果存储的值不是int这样的整数，那么就需要自己写两个仿函数并传入模板参数了
#include <iostream>
#include <vector>
using namespace std;
template <class T>
struct HashBucketData
{
// 节点的数据域和指针域
T _data;
HashBucketData* _next;
HashBucketData(T data)
:_data(data)
,_next(nullptr)
{}
HashBucketData()
:_next(nullptr)
{}
};
// 迭代器的声明
template <class K, class T, class KeyOfT, class HashTrans>
struct __HashIterator;
template <class K, class T, class KeyOfT, class HashTrans>
class HashBucket
{
template <class K, class T, class KeyOfT, class HashTrans>
friend struct __HashIterator;
typedef HashBucketData<T> Data;
typedef __HashIterator<K, T, KeyOfT, HashTrans> iterator;
public:
pair<iterator, bool> Insert(const T& data); // 增
bool Erase(const K& key); // 删
iterator Find(const K& key); // 查
~HashBucket(); // 析构的声明
iterator begin();
iterator end() { return iterator(nullptr, this); }
private:
vector<Data*> _bucket; // 存储指针的数组
size_t _n = 0; // 用来维护负载因子的变量
};
template <class K, class T, class KeyOfT, class HashTrans>
struct __HashIterator
{
typedef HashBucketData<T> Data;
typedef HashBucket<K, T, KeyOfT, HashTrans> Bucket;
typedef __HashIterator<K, T, KeyOfT, HashTrans> Self;
__HashIterator(Data* pnode, Bucket* pbucket) :_pnode(pnode), _pbucket(pbucket) {}
T& operator*() { return _pnode->_data; }
T* operator->() { return &(_pnode->_data); }
Self& operator++(); // 先声明，在类外实现
bool operator==(const Self& v) { return _pnode == v._pnode; }
bool operator!=(const Self& v) { return _pnode != v._pnode; }
Data* _pnode; // 封装的节点的地址
Bucket* _pbucket; // 封装的哈希桶的地址
};
// 迭代器的++迭代操作
template <class K, class T, class KeyOfT, class HashTrans>
typename __HashIterator<K, T, KeyOfT, HashTrans>::Self& __HashIterator<K, T, KeyOfT, HashTrans>::operator++()
{
Data* cur = _pnode;
if (cur == nullptr) // 当迭代器指向空时，直接返回
{
return *this;
}
// 仿函数对象的定义，key取出泛型的key值，trans将key值转换成哈希值
KeyOfT key;
HashTrans trans;
if (cur->_next == nullptr) // 当前迭代器指向链表的最后一个节点，需要使迭代器指向下一个链表的头指针
{
// 先计算当前迭代器在数组中的位置
size_t hashi = trans(key(_pnode->_data)) % _pbucket->_bucket.size();
// 找一个有节点的位置
while (++hashi < _pbucket->_bucket.size() && _pbucket->_bucket[hashi] == nullptr){ }
// 如果遍历完整个桶还没有找到节点，修改迭代器为空再返回
if (hashi == _pbucket->_bucket.size())
{
_pnode = nullptr;
return *this;
}
// 走到这说明找到了头指针，修改迭代器并将其返回
_pnode = _pbucket->_bucket[hashi];
return *this;
}
// 如果迭代器没有指向链表的尾部，遍历到下一个节点就行
_pnode = _pnode->_next;
return *this;
}
template <class K, class T, class KeyOfT, class HashTrans>
HashBucket<K, T, KeyOfT, HashTrans>::~HashBucket()
{
for (size_t i = 0; i < _bucket.size(); ++i)
{
Data* cur = _bucket[i];
// 当头指针不为空，进入单链表遍历
while (cur)
{
Data* next = cur->_next;
delete cur;
cur = next;
}
// 释放后记得置空，虽然没什么必要，但是好习惯
_bucket[i] = nullptr;
}
}
template <class K, class T, class KeyOfT, class HashTrans>
typename HashBucket<K, T, KeyOfT, HashTrans>::iterator HashBucket<K, T, KeyOfT, HashTrans>::Find(const K& key)
{
// 如果桶中没有数据直接返回
if (_bucket.size() == 0)
{
return iterator(nullptr, this);
}
// 仿函数对象的定义
KeyOfT get_key;
HashTrans trans;
// 先计算当前迭代器在数组中的位置
size_t hashi = trans(key) % _bucket.size();
Data* cur = _bucket[hashi];
while (cur) // 遍历这个单链表查找key值对应的节点
{
if (get_key(cur->_data) == key)
{
// 用当前节点的地址构造一个迭代器
return iterator(cur, this);
}
cur = cur->_next;
}
// 遍历完单链表还是没有找到，说明节点不存在，返回空迭代器
return iterator(nullptr, this);
}
template <class K, class T, class KeyOfT, class HashTrans>
pair<typename HashBucket<K, T, KeyOfT, HashTrans>::iterator, bool> HashBucket<K, T, KeyOfT, HashTrans>::Insert(const T& data)
{
// 仿函数对象的定义
KeyOfT get_key;
HashTrans trans;
iterator it = Find(get_key(data));
if (it._pnode) // 出现了键值冗余
{
return make_pair(it, false);
}
if (_bucket.size() == 0 || _n * 10 / _bucket.size() >= 7) // 负载因子的维护，扩容
{
// 计算新桶的大小
size_t new_size = _bucket.size() == 0 ? 10 : 2 * _bucket.size();
// 新桶的创建与空间开辟
HashBucket new_bucket;
new_bucket._bucket.resize(new_size);
// 遍历旧表完成节点转移
for (size_t i = 0; i < _bucket.size(); ++i)
{
Data* cur = _bucket[i];
// 当头指针不为空，进入遍历单链表
while (cur)
{
Data* next = cur->_next;
// 获取新的哈希值
size_t new_hashi = trans(get_key(cur->_data)) % new_size;
// 头插操作
cur->_next = new_bucket._bucket[new_hashi];
new_bucket._bucket[new_hashi] = cur;
// 更新遍历旧表的cur
cur = next;
}
_bucket[i] = nullptr; // 好习惯，这里不置空是真的会出问题
}
// 交换完成后将新旧表交换
_bucket.swap(new_bucket._bucket);
}
// 获取哈希值
size_t hashi = trans(get_key(data)) % _bucket.size();
// 构造节点
Data* new_node = new Data(data);
// 将节点头插
new_node->_next = _bucket[hashi];
_bucket[hashi] = new_node;
// 记得负载因子的维护
++_n;
return make_pair(iterator(new_node, this), true);
}
template <class K, class T, class KeyOfT, class HashTrans>
bool HashBucket<K, T, KeyOfT, HashTrans>::Erase(const K& key)
{
HashTrans trans;
iterator dele_it = Find(key);
// 要删除的值不存在，函数直接返回
if (dele_it._pnode == nullptr)
{
return false;
}
// 删除节点的保存
Data* dele_node = dele_it._pnode;
if (dele_node->_next) // 删除的节点不是链表的尾节点
{
// 要删除dele_node节点，转而删除其下一个节点，但在删除之前要维护好链表结构
// 使当前节点指向下一个节点的下一个节点，并且拷贝下一个节点的值给自己
// 最后删除下一个节点
Data* next = dele_node->_next; // 保存下一个节点
Data* next_next = next->_next; // 保存下下个节点
dele_node->_data = next->_data; // 值的拷贝
dele_node->_next = next_next;
delete next;
}
else
{
// 删除的节点是链表的尾节点
// 计算该节点在哈希桶中的哈希值
size_t hashi = trans(key) % _bucket.size();
// 要删除的节点是链表的唯一成员，需要修改头指针
if (_bucket[hashi] == dele_node)
{
delete dele_node;
_bucket[hashi] = nullptr;
}
else
{
// 不是唯一成员，将第一个节点的值拷贝给自己，然后头删
dele_node->_data = _bucket[hashi]->_data;
// 头删
Data* second = _bucket[hashi]->_next;
delete _bucket[hashi];
_bucket[hashi] = second;
}
}
// 记得负载因子的维护
--_n;
return true;
template <class K, class T, class KeyOfT, class HashTrans>
typename HashBucket<K, T, KeyOfT, HashTrans>::iterator HashBucket<K, T, KeyOfT, HashTrans>::begin()
{
if (_n == 0) // 空桶直接返回
{
return iterator(nullptr, this);
}
for (size_t i = 0; i < _bucket.size(); ++i)
{
if (_bucket[i]) // 当头指针不为空，将其返回
{
return iterator(_bucket[i], this);
}
}
return iterator(nullptr, this);
}
}
最后
以上就是无语春天为你收集整理的C++ | 哈希 | 开散列结构的模拟实现 | 迭代器和泛型的封装的全部内容，希望文章能够帮你解决C++ | 哈希 | 开散列结构的模拟实现 | 迭代器和泛型的封装所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复