【C++】哈希表 ---开散列版本的实现

1 前言

上一篇文章，我们介绍了哈希表的基本概念：
哈希表（Hash Table）是一种数据结构，它通过哈希函数将键映射到表中的一个位置来访问记录，支持快速的插入和查找操作。

我们可以通过对key值的处理快速找到目标。如果多个key出现相同的映射位置，此时就发生了哈希冲突，就要进行特殊处理：闭散列和开散列。

1. 闭散列：也叫做开放定址法，其核心是出现哈希冲突，就从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
2. 开散列：又叫链地址法(开链法)，其核心是每个位置是以链表结构储存，遇到哈希冲突就将数据进行头插。

我们已经实现了闭散列版本的哈希表，今天我们来实现开散列版本的哈希表（哈希桶）！

2 开散列版本的实现

我们先来分析一下，我们要实现哈希桶需要做些什么工作。开散列本质上是一个数组，每个位置对于了一个映射地址。开散列解决哈希冲突的本质是将多个元素以链表进行链接，方便我们进行寻找。既然使用到了链表我们可以直接使用list，但是list底层是双向循环链表，对于我们这样简单的情景大可不必这么复杂，使用简单的单向不循环链表即可，并且可以节省一半的空间！

2.1 节点设计

因为我们要实现单链表结构，肯定要来先设计一下节点：

	//节点设计template<class K, class V>struct HashNode{//储存的数据pair<K, V> _kv;//下一个节点的指针HashNode<K, V>* _next;//构造函数HashNode(pair<K, V> kv):_kv(kv),_next(nullptr){}};

节点里面使用pair来储存数据，并储存一个指向下一个节点的指针。这样就能实现链表结构

2.2 框架搭建

设计好了节点，就要进行整体框架的搭建，哈希桶的底层是一个指针数组，还需要一个变量来记录有效个数，方便检测何时扩容。我们简单实现最基本的工作：插入 ， 删除和查找就可以。
需要注意的是，我们需要通过对应的哈希函数来将不同类型的数据转换为size_t类型，这样才能映射到数组中

//仿函数！
template<class K>
struct HashFunc
{//可以进行显示类型转换的直接转换！！！size_t operator()(const K& k){return (size_t)k;}
};
//string不能进行直接转换，需要特化
template<>
struct HashFunc<string>
{//可以进行显示类型转换的直接转换！！！size_t operator()(const string& k){size_t key = 0;for (auto s : k){key *= 131;key += s;}return key;}
};//开散列的哈希表//       key           value      仿函数（转换为size_t）template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:typedef HashNode<K, V> Node;//构造函数HashTable(){_table.resize(10, nullptr);_n = 0;}//插入数据bool insert(const pair<K, V> kv){}//删除bool erase(const K& key){}//查找Node* find(const K& key){}private://底层是一个指针数组vector<Node*> _table;//有效数量size_t _n;//仿函数Hash hs;};

2.3 插入函数

实现插入函数，需要进行以下步骤：

1. 检查当前key是否存在，不存在才插入
2. 根据负载因子检查是否需要扩容
3. key 通过仿函数得到 hashi，找到映射位置
4. 创建一个新节点，并将其头插到映射位置的链表中

扩容的逻辑需要注意一下：最容易想到的是遍历一遍原先的哈希表，将数据重新插入到新的哈希表中，然后释放原先的节点，这样顺畅就可以做到，但是这样其实做了多余的动作，我们不需要将原本的节点释放，直接将原本节点移动到新的哈希表中即可！

//插入数据
bool insert(const pair<K, V> kv)
{if ( find(kv.first) ) return false;//扩容if (_n == _table.size() * 0.7){//直接把原本的节点移动到新的table中即可vector<Node*> newtable(2 * _table.size());//遍历整个数组for (int i = 0; i < _table.size(); i++){if (_table[i]){Node* cur = _table[i];while (cur){//获取数据Node* next = cur->_next;//计算新的映射int hashi = hs(cur->_kv.first) % newtable.size();//进行头插cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}}}_table.swap(newtable);}//首先寻找到合适下标int hashi = hs(kv.first) % _table.size();//进行头插Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;
}

2.4 删除函数

删除的逻辑是根据key值找到对应的位置，在该位置的链表中检索是否有相等的数值。如果有就进行删除，否则返回false

	//删除bool erase(const K& key){//根据key找到对应位置int hashi = hs(key) % _table.size();//在当前位置的链表中寻找目标Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){//找到该位置//分类讨论情况--_n;//如果删除的是第一个if (prev == nullptr){_table[hashi] = cur->_next;}//其他情况else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}

这样简单的删除就写好了！其实就是链表操作加上一步检索的操作。

2.5 查找操作

查找的逻辑和删除类似，根据key值找到映射位置，再在该链表中进行检索，找到返回节点指针，反之返回空指针。

	Node* find(const K& key){//根据key找到对应位置int hashi = hs(key) % _table.size();//在当前位置的链表中寻找目标Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}

2.6 测试

我写好了插入，删除和查找。接下来就来测试一下：
实践是检验真理的唯一标准！

	//测试void test_HT1(){vector<int> arr = { 0 , 1 , 1 , 11 , 111 , 2 , 22 , 21 , 32 , 51 };HashTable<int, int> HT;for (int i = 0; i < arr.size(); i++){HT.insert(make_pair(arr[i], arr[i]));}for (int i = 0; i < arr.size(); i++){HT.erase(arr[i]);}}void test_HT2(){vector<int> arr = { 0 , 1 , 1 , 11 , 111 , 2 , 22 , 21 , 32 , 51 };HashTable<int, int> HT;for (int i = 0; i < arr.size(); i++){HT.insert(make_pair(arr[i], arr[i]));}if (HT.find(1)){std::cout << HT.find(1)->_kv.first << ':' << HT.find(1)->_kv.second << endl;}}void test_HT3(){vector<string> arr = { "sort" , "hello" , "JLX" , "Hi" };HashTable<string, string> HT;for (int i = 0; i < arr.size(); i++){HT.insert(make_pair(arr[i], arr[i]));}if (HT.find("sort")){std::cout << HT.find("sort")->_kv.first << ':' << HT.find("sort")->_kv.second << endl;}}}

这里我们分别测试插入删除，插入寻找，字符串的处理：
我进入调试来看看是否正常：

通过对监视窗口的查看，我们可以验证我们的代码正常运行的！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！