【c++】STL容器-哈希概念介绍、哈希冲突的解决——闭散列和开散列_c++ stl hash

小编个人主页详情<—请点击
小编个人gitee代码仓库<—请点击
c++系列专栏<—请点击
倘若命中无此运，孤身亦可登昆仑，送给屏幕面前的读者朋友们和小编自己!

目录

• • 前言
  • 一、哈希概念介绍
  • 二、哈希冲突
  • 三、闭散列
  • • 闭散列（开放定址法）的模拟实现
    • 铺垫
    • 插入
    • 删除、查找
    • • 测试一
      • 测试二
  • 四、开散列
  • • 开散列（链地址法/哈希桶）的模拟实现
    • 铺垫
    • 插入
    • 查找
    • 删除
    • 析构函数
    • • 测试一
      • 测试二
  • 五、源代码
  • • open_address
    • hash_bucket
    • test.cpp
  • 总结

前言

【c++】STL容器——使用红黑树模拟实现map和set（由浅入深逐步完善3w字详解）——书接上文 详情请点击<——
本文由小编为大家介绍——【c++】STL容器-哈希概念介绍、哈希冲突的解决——闭散列和开散列

一、哈希概念介绍

哈希（散列）：不经过任何比较，可以一次直接从表中获取想要的元素。
如果建立一种存储结构，通过某种函数可以使元素的存储位置和它的关键码之间建立某种一一映射关系。那么在查找时，可以通过该函数很快的查找到该元素

1. 插入元素
   根据待插入元素的关键码，通过某种函数计算出元素在表中的存储位置（哈希地址），并且按照此存储位置存储该元素
2. 搜索元素
   根据待搜索元素的关键码，通过某种函数计算出元素在表中的存储位置（哈希地址），在结构中按照此存储位置进行比较，若关键码相同，则搜索成功

1. 上述操作称为哈希（散列）方法
2. 哈希方法中使用的某种可以通过元素的关键码计算元素在表中的存储位置的转换函数称为哈希（散列）函数。常见的哈希函数有直接定址法，除留余数法
3. 构造出来的存储结构称为哈希表（散列表）

二、哈希冲突

哈希冲突（哈希碰撞）：不同的关键字通过相同的哈希函数计算出相同的哈希地址

引起哈希冲突的原因可能是哈希函数设计不够合理

哈希函数的设计原则：

1. 哈希函数的定义域必须包含需要存储的全部的关键码，也就是说如果哈希表（散列表）允许有m个地址，那么其值域必须是0到m-1之间
2. 哈希函数计算出来的地址可以均匀的分布在整个空间中
3. 哈希函数比较简单

但是应该明确一点，哈希函数设计的越精妙，产生哈希冲突的概率越低，但是哈希冲突无法避免

哈希函数（除留余数法）计算：hashi = 关键码key % size，其中hashi计算的结果为哈希地址，即元素使用关键码计算出在表中对应的存储位置

1. 观察这种使用哈希函数计算元素的哈希地址的方式，可以直接定位元素在表中的存储位置，不用经过类似于顺序查找和红黑树方式的进行多次比较，所以通常来讲这种方式的搜索效率要更高
2. 那么接下来小编插入一个15，这个15就会与5产生哈希碰撞，那么应该如何处理哈希冲突呢？

哈希冲突的解决方式是闭散列和开散列

三、闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，那么就说明后面一定还有空位置，那么就将key放到哈希冲突的下一个“空位置”上去

那么我们该如何寻找到下一个“空位置”呢？我们可以采用线性探测的方法进行寻找

1. 线性探测：从发生冲突的位置的开始，依次向后探测，直到寻找到下一个空位置为止

闭散列（开放定址法）的模拟实现

铺垫

1. 闭散列（开放定址法）实现哈希表HashTable和开散列（链地址法）实现的哈希表HashTable有命名冲突，所以我们将我们实现的闭散列（开放定址法）放在open_address这个命名空间中
2. 我们要实现的开放定址法是采用模板类实现的key_value结构
3. 由于我们要支持的关键码的类型应该有整形，浮点型，字符串等，那么我们应该使用仿函数的方式，将关键码处理，使关键码可以统统转化为可以支持模%运算的整形，那么我们就应该针对字符串做特殊处理，先处理整形以及浮点型，我们获取到关键码后统统返回size_t类型的，因为vector的下标不能为负数，那么整数的负数形式就得到了很好的处理，同时浮点型也被转化为了size_t类型的也可以支持模%运算
4. 对于字符串我们使用模板类的特化版本进行处理，逐个取出字符串的字符进行累加，采用BKDR算法 详情请点击<—— 进行处理，处理结果采用size_t形式进行返回即可，这样我们在HashTable的模板参数中使用一个HashFunC给一个默认参数DefaultHashFunc，这样就可以达到支持根据关键码的类型匹配处理，当关键码是字符串的时候就去匹配特化版本的DefaultHashFunc进行处理
5. 对于DefaultHashFunc我们应该放置到命名空间的外面，因为后续小编要讲解的开散列（链地址法）也要使用
6. 那么每一个节点HashNode中就应该存储一个kv，以及一个状态，在初始的时候由于我们没有插入任何元素，所以我们对于初始节点的状态我们应该设置为空
7. 对于哈希表的成员变量，应该有一个vector<HashNode>的_table作为哈希表的存储结构，进行存储节点，同时还应该有一个size_t类型的_n用于标识当前哈希表中的空间中有多少个位置上已经存储了有效元素的个数，这个有效元素的个数可以和size比较用于计算载荷因子（负载因子）进而在哈希表进行插入的时候判断当前哈希表是否需要进行扩容
8. 那么接下来是哈希表的构造函数，默认我们是要给_table开10个空间，但是不可以仅仅使用reserve去开空间，因为这样只是开了10个空间，但是使用operator[ ]去访问的空间的时候会直接越界，因为此时size仍然为0，所以我们可以使用resize去开空间，开10个空间，这样使用operator[ ]去访问的时候就不会报错

template<class K>struct DefaultHashFunc{size_t operator()(const K& key){return key;}};template<>struct DefaultHashFunc<string>{size_t operator()(const string str){size_t ret = 0;for (size_t i = 0; i < str.size(); i++){ret *= 131;ret += str[i];}return ret;}};namespace open_address {enum State{EXIST,EMPTY,DELETE};template<class K, class V>struct HashNode{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);}private:vector<HashNode<K, V>> _table;size_t _n = 0;};}

插入

1. 下面是插入逻辑

2. 在梳理插入的时候，最开始我们先不管扩容和判断kv的有效性的问题，我们首先关注的是如何使用开放定址法去插入
3. 那么最开始我们使用哈希函数去计算出hashi哈希地址，元素应该存储的位置，判断这个计算出来的位置上的元素上的状态是否为存在，如果为存在，说明出现了哈希冲突，也就类似上图中插入15的那种情况，那么我们就要向后迭代hashi，同时使用hash去模%size，这样可以确保不越界，同时我们的哈希表中经过一系列扩容后，一定可以找到空的位置去存放，所以当元素的状态是存在的时候我们可以大胆的向后寻找元素状态是空或者删除的位置去插入
4. 那么当找到元素状态是空或者删除的位置的时候，我们将kv存储到位置中对应的节点中存储，并且将节点的状态修改为存在，同时让_n加一即可，表示当前哈希表的有效数据加1
5. 插入逻辑我们研究完成了，接下来我们研究扩容逻辑，如果判断需要进行扩容呢？扩容的判断我们引进了一个载荷因子也就是负载因子（有效数据在哈希表空间中的占比）进行判断是否需要扩容，扩容的时候我们采用的是resize，所以会始终保持size和capacity相等，所以负载因子的计算我们采用(double)_n / _table.size()，计算出来的结果如果大于等于0.7那么我们就进行扩容，因为我们要确保哈希表这个表中不能太满，如果太满，那么当产生哈希冲突比较多后，查找的效率就会变慢，因为查找是默认查找到空结束，但是同时我们也不能为了效率而故意的浪费空间，所以我们综上考虑当负载因子大于等于0.7的时候就扩容
6. 那么接下来如何进行扩容呢？有两种扩容（一种错误，一种正确）方式如下

7. 并且观察扩容后的哈希表和原来的哈希表，对于扩容的后的哈希表的哈希冲突相较于原来的哈希表会少很多
8. 在进行插入kv前，我们首先调用Find判断，kv是否在哈希表中，开放地址法的Find如果找到了kv返回的是kv位置的指针，如果没有找到kv则返回空nullptr，那么我们就可以进行判断，如果Find去找kv的结果返回的指针不为空，那么就说明kv中的关键码已经存在，所以此时这个kv不能进行插入，我们直接返回false插入失败即可
9. 同时由于我们需要取出kv的关键码，但是由于这个关键码的类型我们无法确定，有可能是整形，也有可能是浮点型，也有可能是字符串，所以在使用元素的关键码去进行模%，使用哈希函数计算出元素的存储地址（哈希地址）前，应该使用仿函数定义的对象hf对kv的关键码进行预处理才行

bool Insert(const pair<K, V>& kv){HashFunc hf;if (Find(kv.first)){return false;}if ((double)_n / _table.size() >= 0.7){size_t newSize = _table.size() * 2;HashTable<K, V> newHash;newHash._table.resize(newSize);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newHash.Insert(_table[i]._kv);}}_table.swap(newHash._table);}size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){hashi++;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;_n++;return true;}

删除、查找

1. 那么我们思考一下如何进行删除，例如小编想要删除5，那么能否删除，例如将5置为0或-1，或者采用挪动数据的方式进行覆盖5，其实上面的方式都不行，如果本来那个位置放的就是0或者-1那么采用将删除位置置为0或-1则不行，或者采用挪动数据的方式覆盖5也不行，因为这会破坏哈希表的结构，那么使用哈希函数计算出来的哈希地址，即元素的存储位置就会错误，所以上述的方法都不行，那么我们应该如何处理呢？
2. 我们可以采用一个伪删除法来删除一个元素，那么就是应用c语言中的枚举enum，分别设置三种状态，空，存在，删除这三种状态来标识这个元素当前的状态，所以在节点中就势必要存储一个_state用于标识元素状态

enum State{EXIST,EMPTY,DELETE};

3. 当我们进行删除的时候同样不能将元素的状态直接置空，试想一下，如果直接将元素的状态置为空，那么我们在进行查找的时候就会出现问题，同样以上图为例，假设我们想要删除5，如果我们将5的状态置为空，此时我们想要查找15，查找的时候是查找到空结束，当状态是存在或者删除的时候仍然要继续向后寻找，那么如果删除5的时候，将5的状态置为空，使用15的关键码通过哈希函数模size10，那么算出的是5的位置，此时5的位置上的元素的状态为空，那么查找会直接结束，没有找到15，但是观察一下图，哈希表中明明有15，所以删除5将5的状态置为空是不可行的
4. 应该将5的状态置为删除，那么此时进行查找15的时候当5位置上的状态为删除的时候，那么就会向后寻找，直到寻找到为空的位置结束，此时就可以逐个向后找状态是存在并且关键码是15的元素，那么就会在8这个位置上找到了15，如果没有找到那么返回空nullptr即可
5. 由于查找返回的是对应kv的位置的指针，所以这里的删除是为数不多的删除函数比插入简单函数，在进行正式删除前，我们使用Find函数查找一下这个kv，使用节点的指针ret接收一下Find的返回值，进行判断一下如果ret为空，那么就说明，kv的关键码不存在，那么kv就无法被删除，这时候我们返回false即可，如果kv的关键码不为空，那么我们使用ret将节点的状态置为删除即可，并且对_n的个数进行减一即可，表示哈希表中的有效数据减一
6. 由于kv中的关键码key不能修改，所以对于Find的返回值的pair中的first即K我们采用const进行修饰

HashNode<const K, V>* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){return (HashNode<const K, V>*)&_table[hashi];}hashi++;hashi %= _table.size();}return nullptr;}bool Erase(const K& key){HashNode<const K, V>* ret = Find(key);if (ret){ret->_state = DELETE;_n--;return true;}return false;}

测试一

1. 小编使用如下代码测试kv关键码为整形的情况

#include #include using namespace std;#include \"HashTable.h\"int main(){open_address::HashTable<int, int> ht;ht.Insert(make_pair(1, 1));ht.Insert(make_pair(11, 11));ht.Insert(make_pair(5, 5));ht.Insert(make_pair(15, 15));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(13, 13));ht.Insert(make_pair(6, 6));ht.Insert(make_pair(16, 16));ht.Insert(make_pair(44, 44));cout << ht.Insert(make_pair(24, 24)) << endl;cout << ht.Insert(make_pair(24, 24)) << endl;cout << ht.Erase(24) << endl;return 0;}

测试结果如下，正确

1. 插入值成功，并且删除24将24的对应的状态修改为DELETE删除

测试二

1. 小编使用如下代码测试kv关键码为字符串的情况

int main(){open_address::HashTable<string, string> ht;ht.Insert(make_pair(\"sort\", \"排序\"));ht.Insert(make_pair(\"insert\", \"xxx\"));open_address::HashNode<const string, string>* ret = ht.Find(\"insert\");ret->_kv.second = \"插入\";return 0;}

运行结果如下，正确

四、开散列

开散列（又称链地址法/哈希桶/拉链方法）：首先对关键码集合使用哈希函数计算哈希地址，具有相同地址的关键码归为同一子集合，每一个子集合称为同一个桶，各个桶中的元素采用单链表链接起来，单链表的头节点的地址存储在哈希表中

开散列（链地址法/哈希桶）的模拟实现

铺垫

1. 链地址法（哈希桶）的命名HashTable为了避免和闭散列（开放定址法）产生命名冲突，所以将其放到hash_bucket这个命名空间中
2. 链地址法同样使用模板参数设计为key_value结构
3. 类似的链地址法对于关键码的类型也和开放定址法一样需要对整形，浮点型，字符串进行处理，所以也需要第三个模板参数HashFunC即仿函数进行提取关键码，确保关键码可以被转换为整形进行模%运算，我们同样采用和开放定址法的类似方法，给HashFunC一个缺省参数DefaultHashFunc，使面对不同的关键码的时候可以做出对应的处理
4. 哈希表的每一个节点HashNode中存储_kv和链表的下一个节点的指针，那么每一个节点需要使用new动态开辟进行申请，所以我们希望在开辟的时候就将kv进行初始化，所以我们还需要写一个HashNode构造函数接收kv进行初始化，同时由于动态申请一个节点，对于下一个节点的指针我们并不知道要指向谁，所以我们给下一个节点的指针初始化空nullptr即可
5. 接下来是哈希表HashTable的准备工作，为了便于处理书写节点，在哈希表中HashTable我们将节点的类型HashNode使用typedef重命名为Node，那么对于成员变量，由于哈希表的表中要存储单链表的头节点的指针，所以我们使用一个vector定义一个_table表即可，同时这里仍然需要一个_n标记有效数据的个数用于判断扩容
6. HashTable的构造函数中我们使用resize对_table进行扩容，使size和capacity相等，那么初始时我们扩容size为10即可，同时由于_table表中存储的是节点的指针，对于节点的指针我们初始化为空nullptr即可

template<class K>struct DefaultHashFunc{size_t operator()(const K& key){return key;}};template<>struct DefaultHashFunc<string>{size_t operator()(const string str){size_t ret = 0;for (size_t i = 0; i < str.size(); i++){ret *= 131;ret += str[i];}return ret;}};namespace hash_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 = DefaultHashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_table.resize(10, nullptr);}private:vector<Node*> _table;size_t _n = 0;};}

插入

1. 下面是插入逻辑

2. 同样的我们在编写开散列（链地址法）的时候，首先忽略扩容和查找检查，先看如何进行插入
3. 那么取出kv中的关键码，使用仿函数确保它转换为size_t类型之后可以进行模%操作，那么使用哈希函数算出哈希地址，对应表中，无论哈希地址上的节点的指针是否为空，我们都进行头插，头插完成后对_n进行加加，表示单链表中的有效数据加一，同时返回true即可
4. 这里的结构是单链表进行的头插，因为单链表的进行头插的效率高，其实这里我们也可以使用容器list进行替代，但是容器list的底层是带头双向循环链表，可以进行任意位置的插入和删除，这里没有必要使用带头双向循环链表，因为我们不确定单链表中的元素究竟是哪一个要被访问，所以对于插入顺序没有要求，同时也不需要在任意位置进行插入，同时容器list中的一个节点中存储了两个指针，两个指针相对于单链表的一个指针消耗较大，使用单链表的消耗比较小，占用空间较小，所以综合考虑这里我们使用单链表，那么同时单链表中的元素也就是元素的关键码经过哈希函数计算后的哈希地址（元素的存储的位置）相同，即产生了哈希冲突的元素，头插过程如上图
5. 那么接下来这里就是在正式插入前判断是否需要进行扩容，那么这里同样是使用_n和size进行判断是否需要进行扩容，由于开散列（链地址法）当出现哈希冲突的时候是采用的单链表头插的形式进行处理，不会去影响其它哈希地址（元素的存储位置），并且进行查找的时候只需要遍历计算出的哈希地址上的单链表即可判断出元素是否存在，也就是说这里对于哈希表中的存储结构这张表中的空要求并不高，所以我们可以_n等于size的时候进行扩容，也就是说理想情况下，平均每一个哈希地址（元素的存储位置）上会有一个有效数据，实际情况中并不会这样，实际情况下可能是某些地址上有两三个节点，有些地址上没有节点，思考一下如果极端情况，某些地址上的节点很长，那么就会影响查找效率，那么我们应该如何处理
6. 我们可以将地址上节点数量超过8个的单链表转换成红黑树进行处理，当然这里小编并不会带领大家写出这样的结构，这里小编进行讲解哈希只是为了更好的学习哈希的底层，并不是为了去造一个更好的轮子
7. 回归正题，那么接下来我们探究如何进行扩容，思考这里能否仿造闭散列（开放定址法）创建对象进行复用Insert，其实是可以的，但是没有必要，小编在闭散列中创建对象，复用Insert主要原因是闭散列的插入代码行数比较多，而这里就两行代码，进行头插即可，同时这里小编不创建新对象复用Insert主要原因还是消耗太大，因为在新的对象中复用Insert需要重新使用new申请节点，并且源对象中的旧节点为了避免内存泄漏，我们还需要手动释放，消耗太大了，所以小编不采用类似于闭散列的方式创建新对象进行插入
8. 这里的扩容那么我们直接创建一个vector类型的变量newtable，使用resize将其size大小扩增至原size的2倍即可，那么接下来我们遍历原表_table，当当前哈希地址上的节点的指针不为空的时候，那么我们遍历这个单链表将其中的每一个元素头插至newtable中即可，进行头插前应该提前保存一下cur的下一个节点的地址next，并且根据cur的关键码使用仿函数确保它被转换为size_t类型，确保可以进行模%操作，那么我们使用哈希函数算出cur的关键码的哈希地址，在newtable的对应的位置上进行头插即可，头插完成后将next给给cur进行迭代，直到cur为空，当cur为空的时候，这一个哈希地址上的单链表已经被遍历头插完成，我们将这一个原哈希表中位置上保存的单链表的头节点的指针置空即可
9. 那么当对_table遍历完成之后，_table中的所有的元素已经链接头插到新扩容完成的newtable，此时newtable中就为我们想要的，此时我们复用vector中的swap进行交换两者即可，并且出了作用域之后vector类还会自动调用析构函数将原_table中的数据进行析构释放
10. 在进行扩容之前，我们应该进行使用Find进行检查是否这个kv的关键码已经存在，如果存在那么插入失败返回false即可

bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}HashFunC hf;if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = hf(kv.first) % _table.size();Node* cur = new Node(kv);cur->_next = _table[hashi];_table[hashi] = cur;_n++;return true;}

查找

1. 查找的逻辑其实比较简单，根据关键码key使用仿函数确保它可以被模%，使用哈希函数（除留余数法）计算出哈希地址，当哈希地址上存储的节点的指针为空的时候表示没有这个关键码，返回空表示查找失败即可
2. 当节点的指针不为空，代表这个哈希地址上有存储的单链表的头节点的地址，那么遍历这个单链表判断关键码是否存在即可，如果存在，返回这个关键码对应的节点的指针即可，指针之间是可以相互随便转换的，所以将节点的类型HashNode转化为HashNode返回即可，这里加上const修饰主要是为了确保关键码key不被修改

HashNode<const K, V>* Find(const K& key){HashFunC hf;size_t hashi = hf(key) % _table.size();if (_table[hashi]){Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return (HashNode<const K, V>*)cur;}cur = cur->_next;}}return nullptr;}

删除

1. 进行删除，首先我们应该先使用Find查找一个key，如果key不存在，那么说明这个关键字key没有对应的元素，也就是无法进行删除，那么此时就是删除失败，我们直接返回false即可
2. 那么接下来进行删除这个位置，同样的，我们需要使用仿函数确保关键字可以进行模%操作，使用哈希函数计算出关键字对应的哈希地址，那么接下来遍历哈希地址上的单链表进行指定位置的删除即可，单链表不同于双向链表，单链表无法回头，所以单链表的删除需要知道删除节点的上一个节点的指针prev，prev的初始化为空，这样删除需要删除的节点才可以将单链表链接起来，否个就会出现节点丢失的情况
3. 当找到了要删除的元素的时候，这里需要分情况进行讨论，单链表如果只有一个元素，那么此时prev一定为空，那么这个元素就是我们要删除的元素，也就是进行头删，那么我们可不能仅仅头删就完了，还应该将_table位置上存储的这个要删除的头节点的地址给置空，这样才行，所以我们应该使用一个cur标记保存一下要删除的元素，第二种情况，同时如果要删除的节点不位于头上，那么此时prev一定不为空，那么我们将上一个元素prev的下一个节点的指针指向cur节点的下一个即可，此时我们使用delete将cur进行删除释放，同时使_n减减，使有效数据的个数减一即可，同时需要注意当cur没有找到删除节点的时候，在每次遍历迭代单链表的时候不要忘记将cur给给prve这样才可以找到cur的前一个节点。同时让cur向后走继续寻找即可，最后删除成功后跳出循环返回true即可

bool Erase(const K& key){if (Find(key) == nullptr){return false;}HashFunC hf;size_t hashi = hf(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_table[hashi] = nullptr;}else{prev->_next = cur->_next;}delete cur;_n--;break;}prev = cur;cur = cur->_next;}return true;}

析构函数

1. 观察上图，这里由于_table表中存储的是单链表的头节点的指针，如果我们不主动去写析构函数，那么单链表中动态开辟申请的节点就没有被释放，那么就会出现内存泄漏，所以我们需要主动写开散列（链地址法/哈希桶）析构函数
2. 思考一下为什么我们对于闭散列（开放定址法）不需要显示写析构函数，因为闭散列（开放定址法）中存储的是节点，那么进行释放vector的时候，由于节点就存储在vector中，那么vector会自动调用编译器默认生成的析构函数去对vector这块空间进行释放
3. 那么开散列（链地址法/哈希桶）析构函数进行的操作是遍历_table，当_table上存储的节点的指针不为空的时候，说明这个哈希地址上存储有单链表的头节点的指针，那么我们遍历这个单链表，需要提前保存cur的下一个节点的指针，对这个单链表的节点逐一释放cur，迭代将next给给cur直到cur为空，代表单链表中的节点已经全部释放完成，之后对这个哈希地址上存储节点的指针置为空即可

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

测试一

1. 小编使用如下代码测试kv关键码为整形的情况

#include #include using namespace std;#include \"HashTable.h\"int main(){hash_bucket::HashTable<int, int> ht;ht.Insert(make_pair(1, 1));ht.Insert(make_pair(11, 11));ht.Insert(make_pair(5, 5));ht.Insert(make_pair(15, 15));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(43, 43));ht.Insert(make_pair(133, 133));ht.Insert(make_pair(53, 53));ht.Insert(make_pair(73, 73));ht.Insert(make_pair(13, 13));ht.Insert(make_pair(132, 132));cout << ht.Erase(1) << endl;cout << ht.Erase(11) << endl;cout << ht.Find(1) << endl;cout << ht.Find(15) << endl;cout << ht.Find(5) << endl;return 0;}

运行结果如下，正确

测试二

1. 小编使用如下代码测试kv关键码为字符串的情况

int main(){hash_bucket::HashTable<string, string> ht;ht.Insert(make_pair(\"sort\", \"排序\"));ht.Insert(make_pair(\"insert\", \"xxx\"));hash_bucket::HashNode<const string, string>* ret = ht.Find(\"insert\");ret->_kv.second = \"插入\";return 0;}

运行结果如下，正确

五、源代码

open_address

#pragma oncetemplate<class K>struct DefaultHashFunc{size_t operator()(const K& key){return key;}};template<>struct DefaultHashFunc<string>{size_t operator()(const string str){size_t ret = 0;for (size_t i = 0; i < str.size(); i++){ret *= 131;ret += str[i];}return ret;}};namespace open_address {enum State{EXIST,EMPTY,DELETE};template<class K, class V>struct HashNode{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pair<K, V>& kv){HashFunc hf;if (Find(kv.first)){return false;}if ((double)_n / _table.size() >= 0.7){size_t newSize = _table.size() * 2;HashTable<K, V> newHash;newHash._table.resize(newSize);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newHash.Insert(_table[i]._kv);}}_table.swap(newHash._table);}size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){hashi++;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;_n++;return true;}HashNode<const K, V>* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){return (HashNode<const K, V>*)&_table[hashi];}hashi++;hashi %= _table.size();}return nullptr;}bool Erase(const K& key){HashNode<const K, V>* ret = Find(key);if (ret){ret->_state = DELETE;_n--;return true;}return false;}private:vector<HashNode<K, V>> _table;size_t _n = 0;};}

hash_bucket

#pragma oncetemplate<class K>struct DefaultHashFunc{size_t operator()(const K& key){return key;}};template<>struct DefaultHashFunc<string>{size_t operator()(const string str){size_t ret = 0;for (size_t i = 0; i < str.size(); i++){ret *= 131;ret += str[i];}return ret;}};namespace hash_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 = DefaultHashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_table.resize(10, nullptr);}~HashTable(){for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while(cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}HashFunC hf;if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = hf(kv.first) % _table.size();Node* cur = new Node(kv);cur->_next = _table[hashi];_table[hashi] = cur;_n++;return true;}HashNode<const K, V>* Find(const K& key){HashFunC hf;size_t hashi = hf(key) % _table.size();if (_table[hashi]){Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return (HashNode<const K, V>*)cur;}cur = cur->_next;}}return nullptr;}bool Erase(const K& key){if (Find(key) == nullptr){return false;}HashFunC hf;size_t hashi = hf(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_table[hashi] = nullptr;}else{prev->_next = cur->_next;}delete cur;_n--;break;}prev = cur;cur = cur->_next;}return true;}private:vector<Node*> _table;size_t _n = 0;};}

test.cpp

#include #include using namespace std;#include \"HashTable.h\"//int main()//{//open_address::HashTable ht;////ht.Insert(make_pair(1, 1));//ht.Insert(make_pair(11, 11));//ht.Insert(make_pair(5, 5));//ht.Insert(make_pair(15, 15));//ht.Insert(make_pair(3, 3));//ht.Insert(make_pair(13, 13));//ht.Insert(make_pair(6, 6));//ht.Insert(make_pair(16, 16));//ht.Insert(make_pair(44, 44));//cout << ht.Insert(make_pair(24, 24)) << endl;//cout << ht.Insert(make_pair(24, 24)) << endl;////cout << ht.Erase(24) << endl;////return 0;//}//int main()//{//open_address::HashTable ht;////ht.Insert(make_pair(\"sort\", \"排序\"));//ht.Insert(make_pair(\"insert\", \"xxx\"));////open_address::HashNode* ret = ht.Find(\"insert\");////ret->_kv.second = \"插入\";////return 0;//}//int main()//{//hash_bucket::HashTable ht;////ht.Insert(make_pair(1, 1));//ht.Insert(make_pair(11, 11));//ht.Insert(make_pair(5, 5));//ht.Insert(make_pair(15, 15));//ht.Insert(make_pair(3, 3));//ht.Insert(make_pair(43, 43));//ht.Insert(make_pair(133, 133));//ht.Insert(make_pair(53, 53));//ht.Insert(make_pair(73, 73));//ht.Insert(make_pair(13, 13));//ht.Insert(make_pair(132, 132));////cout << ht.Erase(1) << endl;//cout << ht.Erase(11) << endl;////cout << ht.Find(1) << endl;//cout << ht.Find(15) << endl;//cout << ht.Find(5) << endl;////return 0;//}int main(){hash_bucket::HashTable<string, string> ht;ht.Insert(make_pair(\"sort\", \"排序\"));ht.Insert(make_pair(\"insert\", \"xxx\"));hash_bucket::HashNode<const string, string>* ret = ht.Find(\"insert\");ret->_kv.second = \"插入\";return 0;}

总结

以上就是今天的博客内容啦,希望对读者朋友们有帮助
水滴石穿，坚持就是胜利，读者朋友们可以点个关注
点赞收藏加关注，找到小编不迷路！