【 C++ 】开散列哈希桶的模拟实现

2026/8/22 7:02:58 拓冰建站浏览量

哈希桶大概框架

根据我们先前对开散列哈希桶的了解，得知其根本就是一个指针数组，数组里每一个位置都是一个链表指针，因此我们要单独封装一个链表结构的类，以此来告知我们哈希表类的每个位置为链表指针结构。

namespace 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 = DefaultHash<K>>class HashTable{typedef HashNode<K, V> Node;public://相关功能的实现……private://指针数组vector<Node*> _tables;size_t _n = 0;//记录有效数据的个数};
}

构建仿函数把数据类型转为整型并特化

此步操作的方法和闭散列哈希表所实现的步骤一致，目的都是为了能够让后续操作中传入的所有数据类型转换为整型数据，以此方便后续建立映射关系，直接看代码：

//利用仿函数将数据类型转换为整型template<class K>struct DefaultHash{size_t operator()(const K& key){return (size_t)key;}};//模板的特化template<>struct DefaultHash<std::string>{size_t operator()(const std::string& key){//BKDR哈希算法size_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来}return hash;}};

哈希桶的插入

哈希桶的插入主要分为这几大步骤

去除冗余
扩容操作
头插操作

下面开始具体展开说明：

1、去除冗余：

复用Find查找函数，去帮助我们查找插入的值是否存在。
若存在，直接返回false 。
不存在，再进行后续的插入操作。

2、扩容操作：

针对哈希桶的扩容，我们有两种方法进行扩容，法一和哈希表扩容的方法一致

法一：

当负载因子==1时扩容。
扩容后重新建立映射关系。
创建一个新的哈希桶对象，扩容到newSize的大小。
遍历旧表，把旧表每个存在的元素插入到新表，此步骤让新表自动完成映射关系，无序手动构建。
利用swap函数把新表交换到旧表那，此时的旧表就是已经扩好容且建立号映射关系的哈希表。

此扩容的方法会存在一个问题：释放旧表会出错！！！

当我们把旧表的元素映射插入到新表的时候，最后都要释放旧表，按照先前哈希表的释放，我们无需做任何处理，但是现在定义的结构是vector，是自定义类型，会自动调用析构函数进行释放，vector存储的数据是Node*，Node*是内置类型，不会自动释放，最后会出现表我们释放了，但是链表结构的数据还没释放，因此，我们还需借助手写析构函数来帮助我们释放。

//析构函数
~HashTable()
{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;//释放后置空}
}

此扩容的方法可以进行优化，见法二。

法二：

这里我们没必要再创建新的节点，相反把扩容前的节点拿过来重新映射到新表中，大体逻辑和前面差不太多，只是这里不需要再创建新节点。直接利用原链表里的节点。

3、头插操作：

借助仿函数找到映射的位置（头插的位置）。
进行头插的操作。
更新有效数据个数。

在这里插入图片描述

//插入
bool Insert(const pair<K, V>& kv)
{//1、去除冗余if (Find(kv.first)){return false;}//构建仿函数，把数据类型转为整型，便于后续建立映射关系HashFunc hf;//2、负载因子 == 1就扩容if (_tables.size() == _n){/*法一size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newHT;//newHT._tables.resize(newSize, nullptr);//遍历旧表，把旧表的数据重新映射到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur)//如果cur不为空，就插入{newHT.Insert(cur->_kv);cur = cur->_next;}}newHT._tables.swap(_tables);*///法二：size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newTable;newTable.resize(newSize, nullptr);for (size_t i = 0; i < _tables.size(); i++)//遍历旧表{Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newSize;//确认映射到新表的位置//头插cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}newTable.swap(_tables);}//3、头插//找到对应的映射位置size_t hashi = hf(kv.first);hashi %= _tables.size();//头插到对应的桶即可Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

哈希桶的查找

遵循下列规则：

先去判断表的大小是否为0，为0直接返回nullptr。
利用仿函数去找到映射的位置。
在此位置往后的一串链表中进行遍历查找，找到了，返回节点指针。
遍历结束，说明没找到，返回nullptr。

//查找
Node* Find(const K& key)
{//防止后续除0错误if (_tables.size() == 0){return nullptr;}//构建仿函数，把数据类型转为整型，便于后续建立映射关系HashFunc hf;//找到对应的映射下标位置size_t hashi = hf(key);//size_t hashi = HashFunc()(key);//匿名对象hashi %= _tables.size();Node* cur = _tables[hashi];//在此位置的链表中进行遍历查找while (cur){if (cur->_kv.first == key){//找到了return cur;}cur = cur->_next;}//遍历结束，没有找到，返回nullptrreturn nullptr;
}

哈希桶的删除

哈希桶的删除遵循这两大思路：

找到删除的值对应哈希桶的下标映射位置。
按照单链表删除节点的方法对该值进行删除。

//删除
bool Erase(const K& key)
{//防止后续除0错误if (_tables.size() == 0){return false;}//构建仿函数，把数据类型转为整型，便于后续建立映射关系HashFunc hf;//找到key所对应的哈希桶的位置size_t hashi = hf(key);hashi %= _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;}prev = cur;cur = cur->_next;}return false;
}

法二：替换法删除

上述的删除是实打实的删除，建立prev作为cur的前指针，以此利用prev和cur->next来建立关系从而删除cur节点，但是我们可以不用借助prev指针，就利用先前二叉搜索树的替换法删除的思想来解决。图示：