【C++】手撕哈希表的闭散列和开散列

2024-03-24 21:52
文章标签 c++ 哈希 闭散列 开散列

本文主要是介绍【C++】手撕哈希表的闭散列和开散列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

> 作者:დ旧言~
> 座右铭:松树千年终是朽,槿花一日自为荣。

> 目标:手撕哈希表的闭散列和开散列

> 毒鸡汤:谁不是一边受伤,一边学会坚强。

> 专栏选自:C嘎嘎进阶

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言

谈到哈希表,大家都做过这样的题目,统计字符串的字母个数,像这样的题目可以创建一个数组,每个字母采用 a['ch']++ 计入数组中,这样的数组我们称之为哈希表,这种哈希表也是最简单的,如果说为了方便直接调用哈希表,那这个哈希表该如何模拟呢?这个问题也是今天我们所探讨的,手撕哈希表。

⭐主体

学习手撕哈希表的闭散列和开散列咱们按照下面的图解:

🌙哈希概念

知识回顾

在顺序结构以及平衡树中,由于元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较;比如顺序表中需要从表头开始依次往后比对寻找,查找时间复杂度为 O(N),平衡树中需要从第一层开始逐层往下比对寻找,查找时间复杂度为 O(logN);即搜索的效率取决于搜索过程中元素的比较次数。

分析探讨

如果构造一种存储结构,可以通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一对一的映射关系,那么在查找时通过该函数就可以很快找到该元素;当向该结构中:

  • 插入元素时:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放;
  • 搜索元素时:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。

总结归纳

该方法即为 哈希 (散列) 方法,哈希方法中使用的转换函数称为哈希 (散列) 函数,构造出来的结构称为哈希表 (Hash Table) (或者称散列表)。

注意事项

我们上面提到的不管是顺序搜索、平衡树搜索还是哈希搜索,其 key 值都是唯一的,也就是说,搜索树中不允许出现相同 key 值的节点,哈希表中也不允许出现相同 key 值的元素,我们下文所进行的所有操作也都是在这前提之上进行的。

🌙哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。

哈希冲突有两种常见的解决办法:

  1. 闭散列 (开放定址法):当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去;
  2. 开散列 (链地址法):首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码 (哈希冲突) 归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中;也就是说,当发生哈希冲突时,把 key 直接链接在该位置的下面。

🌙哈希函数

哈希函数有如下设计原则

  1. 哈希函数的定义域必须包括需要存储的全部关键码,而如果哈希表允许有m个地址时,其值域必须在0到m-1之间;
  2. 哈希函数计算出来的地址要尽量能均匀分布在整个空间中;
  3. 哈希函数应该比较简单。

 💫直接定址法

什么是直接定址法:

直接定址就是根据 key 值直接得到存储位置,最多再进行一个简单的常数之间的转换。

分析:

  • 直接定址法的优点是简单,且不会引起哈希冲突 ,由于直接定址法的 key 值经过哈希函数转换后得到的值一定是唯一的,所以不存在哈希冲突。
  • 直接定址法适用于数据范围集中的情况,这样 key 值映射到哈希表后,哈希表的空间利用率高,浪费的空间较少

图解:

 💫除留余数法

什么是除留余数法:

简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址,将 key 保存到该地址中

分析:

  • 除留余数的优点是可以处理数据范围分散的数据
  • 缺点是会引发哈希冲突

图解:

 💫方法总结

直接定制法–(常用)

  • 取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况使用场景:适合查找比较小且连续的情况

除留余数法–(常用)

  • 设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:**Hash(key) = key% p(p<=m),**将关键码转换成哈希地址

平方取中法–(了解)

  • 假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况

折叠法–(了解)

  • 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况

随机数法–(了解)

  • 选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

数学分析法–(了解)

  • 设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。

🌙闭散列哈希

闭散列也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去;那如何寻找下一个空位置呢?有两种方法 – 线性探测法和二次探测法。

 💫线性探测法

什么是线性探测:

线性探测法是指从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止

图解:

💫哈希表的基本框架

框架搭建步骤:

  • 在哈希表中我们使用了 vector 来存储数据,并增加了一个变量 n 来记录表中有效数据的个数;同时,哈希表的每个下标位置存储的数据都是一个 KV 模型的键值对
  • 当key映射的下标位置被占用时,key会向后寻找下一个空位置进行插入,但如果key走到数组尾都还没找到空位置,那么key就会从数组起始位置重新往后寻找
  • 在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态 (存在、删除、空) 

代码如下:

//标识每个存储位置的状态--空、存在与删除
enum State {EMPTY,EXIST,DELETE
};//哈希表每个下标位置存储的数据的结构
template<class K, class V>
struct HashData {pair<K, V> _kv;State _state = EMPTY;  //默认为空
};template<class K, class V>
class HashTable {typedef HashData<K, V> Data;
private:vector<Data> _tables;size_t _n;  //记录表中有效数据的个数
};

💫哈希表的插入删除与查找

插入:

通过哈希函数得到余数即数组下标,如果该下标的状态为删除或为空则插入,如果为存在则向后寻找下一个状态为删除/空的位置进行插入。

查找:

通过哈希函数得到余数即数组下标,取出小标位置的key与目标key进行比较,相等就返回该位置的地址,不相等就继续往后查找,如果查找到状态为空的下标位置就返回 nullptr。

删除:

复用查找函数,查找到就通过查找函数的返回值将小标位置数据的状态置为 删除,找不到就返回 false。

代码实现:

#pragma once#include <vector>
#include <utility>
using std::pair;
using std::vector;//标识每个存储位置的状态--空、存在与删除
enum State {EMPTY,EXIST,DELETE
};//哈希表每个下标位置存储的数据的结构
template<class K, class V>
struct HashData {pair<K, V> _kv;State _state = EMPTY;  //默认为空
};//哈希表
template<class K, class V>
class HashTable {typedef HashData<K, V> Data;public:HashTable(): _n(0){//将哈希表的大小默认给为10_tables.resize(10);}bool insert(const pair<K, V>& kv) {if (find(kv.first))return false;//除留余数法 && 线性探测法//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置,如果该位置被占用往后放size_t hashi = kv.first % _tables.size();//不能放在EXIST的位置,DELETE和EMPTY都能放while (_tables[hashi]._state == EXIST) {++hashi;if (hashi == _tables.size()) hashi = 0;  //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}//将find的返回值定义为Data的地址,可以方便我们进行删除以及修改VData* find(const K& key) {Hash hash;  //仿函数对象size_t hashi = hash(key) % _tables.size();//记录hashi的起始位置,避免哈希表中元素全为EXIST和DELETE时导致死循环size_t starti = hashi;//最多找到空while (_tables[hashi]._state != EMPTY) {//key相等并且state为EXIST才表示找到if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)return &_tables[hashi];++hashi;//如果找到尾还没找到,就从0重新找if (hashi == _tables.size()) hashi = 0;//如果找一圈还没找到,就跳出循环if (hashi == starti) break;}return nullptr;}bool erase(const K& key) {//找不到就不删,找到就把状态置为DELETE即可Data* ret = find(key);if (ret) {ret->_state = DELETE;return true;}return false;}private:vector<Data> _tables;size_t _n;  //记录表中有效数据的个数
};

💫哈希表的扩容

哈希表的扩容和普通顺序表容器的扩容不同,它不是容器满了才扩容,而是会有一个负载因子,也叫载荷因子,当载荷因子超过一定大小时就立即扩容。

代码如下:

bool insert(const pair<K, V>& kv) {if (find(kv.first))return false;//如果大于标定的载荷因子就扩容,这里我们将载荷因子标定为0.7//扩容现代写法--复用insert接口if ((1.0 * _n / _tables.size()) >= 0.7) {HashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (auto& e : _tables)newHT.insert(e._kv);_tables.swap(newHT._tables);}//除留余数法 && 线性探测法//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置,如果该位置被占用往后放size_t hashi = kv.first % _tables.size();//不能放在EXIST的位置,DELETE和EMPTY都能放while (_tables[hashi]._state == EXIST) {++hashi;if (hashi == _tables.size()) hashi = 0;  //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}

💫哈希表的仿函数

模板参数是一个仿函数,仿函数分为设计者提供的默认仿函数和用户提供的仿函数,系统默认的仿函数可以将一些常见的 key 的类型全部转化为整形,比如字符串、指针、整数;而用户提供的仿函数则可以根据用户自己的 key 类型将其转化为整形,比如 People 类 (身份证号)、Date 类 等等

代码如下:

template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t sum = 0;for (auto ch : key)sum += ch;return sum;}
};

细节分析:

有了仿函数,解决了传字符串的问题

💫闭散列整体代码实现

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;// 哈希表的仿函数 ,通过上层容器提供的仿函数获取到元素的键值
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 e : key){hash += e;hash *= 131;}return hash;}
};// 闭散列哈希表
namespace open_address
{enum State{EMPTY,  // 空EXIST,  // 存在DELETE  // 删除};// 哈希表每个下标的位置存储的数据的结构template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY; // 默认为空};// 哈希表template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:// 默认开辟 10 个空间HashTable(size_t size = 10){_tables.resize(size);}// 查找HashData<K, V>* Find(const K& key){// 仿函数对象Hash hs;// 线性探测size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){// key相等并且state为EXIST(存在)才能表示找到if (key == _tables[hashi]._kv.first&& _tables[hashi]._state == EXIST){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}// 插入bool Insert(const pair<K, V>& kv){// 为空就返回if (Find(kv.first))return false;// 扩容if (_n * 10 / _tables.size() >= 7){// 扩容HashTable<K, V, Hash> newHT(_tables.size() * 2);// 遍历旧表,插入到新表for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}// 交换_tables.swap(newHT._tables);}// 仿函数对象Hash hs;// 线性探测,找需要插入的地方size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}// 删除bool Erase(const K& key){// 查找HashData<K, V>* ret = Find(key);if (ret){_n--; // 元素减一ret->_state = DELETE;// 状态改为删除return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;  // 实际存储的数据个数};// 测试一void TestHT1(){int a[] = { 1,4,24,34,7,44,17,37 };// 创建哈希表HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e)); // 插入元素}for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":E" << endl;}else{cout << ret->_kv.first << ":D" << endl;}}cout << endl;ht.Erase(34);ht.Erase(4);for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":E" << endl;}else{cout << e << ":D" << endl;}}cout << endl;}// 测试二struct Date{int _year;int _month;int _day;};struct HashFuncDate{// 2024/6/3// 2024/3/6size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 131;hash += d._month;hash *= 131;hash += d._day;hash *= 131;return hash;}};void TestHT2(){HashTable<string, string> dict;dict.Insert(make_pair("sort", "排序"));dict.Insert(make_pair("string", "字符串"));HashTable<Date, string, HashFuncDate> DateHash;}}

🌙开散列哈希

什么是开散列哈希:

开散列法又叫 链地址法 (开链法),首先对关键码集合用散列函数计算散列地址,即 key 映射的下标位置,具有相同地址的关键码 (哈希冲突) 归于同一子集合,每一个子集合称为一个桶 (哈希桶),各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中;也就是说,当发生哈希冲突时,把 key 作为一个节点直接链接到下标位置的哈希桶中。

图解:

 💫开散列的节点结构

由于开散列的不同冲突之间不会互相影响,所以开散列不再需要 state 变量来记录每个下表位置的状态;同时,因为开散列每个下标位置链接的都是一个哈希桶,所以 vector 中的每个元素都是一个节点的指针,指向单链表的第一个元素,所以 _tables 是一个指针数组;最后,为了是不同类型的 key 都能够计算出映射的下标位置,所以我们这里也需要传递仿函数。

代码如下:

//开散列
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>struct HashFunc {size_t operator()(const K& key) {return key;}};//类模板特化template<>struct HashFunc<string> {size_t operator()(const string& key) {//BKDR字符串哈希算法size_t sum = 0;for (auto ch : key)sum = sum * 131 + ch;return sum;}};//哈希表template<class K, class V, class Hash = HashFunc<K>>class HashTable {typedef HashNode<K, V> Node;private:vector<Node*> _tables;  //指针数组size_t _n;  //表中有效数据的个数};
}

 💫开散列的插入删除与查找

开散列的插入

开散列插入的前部分和闭散列一样,根据 key 与哈希表大小得到映射的下标位置,与闭散列不同的是,由于哈希表中每个下标位置都是一个哈希桶,即一个单链表,那么对于发现哈希冲突的元素我们只需要将其链接到哈希桶中即可,这里显然是选择将冲突元素进行头插,因为尾插还需要找尾,会导致效率降低:

// 插入函数
bool Insert(const pair<K, V>& kv)
{// 查看元素是否存在if (Find(kv.first))return false;// 仿函数对象Hash hs;// 负载因子到1就扩容if (_n == _tables.size()){// 扩容vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){// 取出旧表中节点,重新计算挂到新表桶中Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插到新表size_t hashi = hs(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}// 调用仿函数的匿名对象来将key转换为整数size_t hashi = hs(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

开散列的查找

开散列的查找也很简单,根据余数找到下标,由于下标位置存储的是链表首元素地址,所以我们只需要取出首元素地址,然后顺序遍历单链表即可:

// 查找
Node* Find(const K& key)
{// 仿函数对象Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

开散列的删除

和闭散列不同的是,开散列的删除不能直接通过查找函数的返回值来进行删除,因为单链表在删除节点时还需要改变父节点的指向,让其指向目标节点的下一个节点,所以我们需要通过遍历单链表来进行删除:

// 删除
bool Erase(const K& key)
{// 仿函数对象Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){// 删除还要分是否为头节点if (cur->_kv.first == key){// 删除if (prev){prev->_next = cur->_next;}else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}// 下一个结点prev = cur;cur = cur->_next;}return false;
}

💫开散列整体代码实现

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;// 哈希表的仿函数 ,通过上层容器提供的仿函数获取到元素的键值
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 e : key){hash += e;hash *= 131;}return hash;}
};// 开散列哈希表
namespace hash_bucket
{// 哈希表的节点结构 -- 单链表template<class K, class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;// 初始化列表HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}};// 哈希表template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:// 构造函数HashTable(){_tables.resize(10, nullptr); // 开空间_n = 0;}// 析构函数~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;}}// 插入函数bool Insert(const pair<K, V>& kv){// 查看元素是否存在if (Find(kv.first))return false;// 仿函数对象Hash hs;// 负载因子到1就扩容if (_n == _tables.size()){// 扩容vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){// 取出旧表中节点,重新计算挂到新表桶中Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插到新表size_t hashi = hs(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}// 调用仿函数的匿名对象来将key转换为整数size_t hashi = hs(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}// 查找Node* Find(const K& key){// 仿函数对象Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}// 删除bool Erase(const K& key){// 仿函数对象Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){// 删除还要分是否为头节点if (cur->_kv.first == key){// 删除if (prev){prev->_next = cur->_next;}else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}// 下一个结点prev = cur;cur = cur->_next;}return false;}// 测试void Some(){size_t bucketSize = 0;size_t maxBucketLen = 0;size_t sum = 0;double averageBucketLen = 0;for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){++bucketSize;}size_t bucketLen = 0;while (cur){++bucketLen;cur = cur->_next;}sum += bucketLen;if (bucketLen > maxBucketLen){maxBucketLen = bucketLen;}}averageBucketLen = (double)sum / (double)bucketSize;printf("load factor:%lf\n", (double)_n / _tables.size());printf("all bucketSize:%d\n", _tables.size());printf("bucketSize:%d\n", bucketSize);printf("maxBucketLen:%d\n", maxBucketLen);printf("averageBucketLen:%lf\n\n", averageBucketLen);}private:vector<Node*> _tables; // 指针数组size_t _n; // 元素个数};// 测试一void TestHT1(){HashTable<int, int> ht;int a[] = { 1,4,24,34,7,44,17,37 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(5, 5));ht.Insert(make_pair(15, 15));ht.Insert(make_pair(25, 25));ht.Erase(5);ht.Erase(15);ht.Erase(25);ht.Erase(35);for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":E" << endl;}else{cout << ret->_kv.first << ":D" << endl;}}cout << endl;HashTable<string, string> dict;dict.Insert(make_pair("sort", "排序"));dict.Insert(make_pair("string", "字符串"));}// 测试二void TestHT2(){const size_t N = 30000;unordered_set<int> us;set<int> s;HashTable<int, int> ht;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; ++i){//v.push_back(rand()); // N比较大时,重复值比较多v.push_back(rand() + i); // 重复值相对少//v.push_back(i); // 没有重复,有序}size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert:" << end1 - begin1 << endl;size_t begin2 = clock();for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert:" << end2 - begin2 << endl;size_t begin10 = clock();for (auto e : v){ht.Insert(make_pair(e, e));}size_t end10 = clock();cout << "HashTbale insert:" << end10 - begin10 << endl << endl;size_t begin3 = clock();for (auto e : v){s.find(e);}size_t end3 = clock();cout << "set find:" << end3 - begin3 << endl;size_t begin4 = clock();for (auto e : v){us.find(e);}size_t end4 = clock();cout << "unordered_set find:" << end4 - begin4 << endl;size_t begin11 = clock();for (auto e : v){ht.Find(e);}size_t end11 = clock();cout << "HashTable find:" << end11 - begin11 << endl << endl;cout << "插入数据个数:" << us.size() << endl << endl;ht.Some();size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase:" << end5 - begin5 << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "unordered_set erase:" << end6 - begin6 << endl;size_t begin12 = clock();for (auto e : v){ht.Erase(e);}size_t end12 = clock();cout << "HashTable Erase:" << end12 - begin12 << endl << endl;}
}

🌟结束语

       今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。

这篇关于【C++】手撕哈希表的闭散列和开散列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/842902

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现