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

文章目录

  • 哈希冲突解决
    • 闭散列 （开放定址法）
    • 开散列 （链地址法、哈希桶）
      • 开散列实现（哈希桶）
        • 哈希表的结构
        • Insert
        • Find
        • Erase

哈希冲突解决

闭散列 （开放定址法）

发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去

如何寻找“下一个位置”
1、线性探测
发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止

Hi=(H0+i)%m ( i = 1 , 2 , 3 , . . . )

H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过线性探测后得到的存放位置
m：表的大小。

举例：
用除留余数法将序列{1,111,4,7,15,25,44,9}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：

使用除留余数法
1%10 =1 ,111 %10 =1
即111和1发生了哈希冲突 ，所以111找到1的下一个空位置插入
在这里插入图片描述

将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。
介于此，哈希表当中引入了负载因子（载荷因子）：

负载因子 = 表中有效数据个数 / 空间的大小
不难发现：
负载因子越大，产出冲突的概率越高，查找的效率越低
负载因子越小，产出冲突的概率越低，查找的效率越高

负载因子越小，也就意味着空间的利用率越低，此时大量的空间都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下
采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容

线性探测的缺点：一旦发生冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要多次比较（踩踏效应），导致搜索效率降低
2、二次探测

二次探测为了避免该问题，找下一个空位置的方法为

Hi=(H0+i ^2 )%m ( i = 1 , 2 , 3 , . . . )

H0：通过哈希函数对元素的关键码进行计算得到的位置
Hi：冲突元素通过二次探测后得到的存放位置
m：表的大小

相比线性探测而言，二次探测i是平方，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积

template <class K>
struct  DefaultHashFunc
{size_t operator() (const K& key){return (size_t)key;}
};template <>
struct DefaultHashFunc<string>
{size_t  operator() (const string& str){//BKDR,将输入的字符串转换为哈希值size_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}
};namespace open_address 
{enum  STATE{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;STATE _state = EMPTY;};struct StringHashFunc{size_t operator()(const string& str){return str[0];}};//template<class K, class V>template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);}bool insert(const pair<K, V> kv){//扩容 if ((double)_n / (double)_table.size() >= 0.7){HashTable<K, V>  newHT;size_t newSize = _table.size() * 2;newHT._table.resize(newSize);//遍历旧表的数据，将旧表的数据重新映射到新表中for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newHT.insert(_table[i]._kv);//插入的写成kv不行？}}_table.swap(newHT._table);}//线性探测HashFunc hf;size_t  hashi = hf(kv.first) % _table.size();//如果该位置没有元素，则直接插入元素 ，如果该位置有元素，找到下一个空位置，插入新元素while (_table[hashi]._state == EXIST)//不是EMPTY和DELETE这两种情况{++hashi;hashi %= _table.size();}//是EMPTY和DELETE这两种情况_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;}HashData<const K, V>* Find(const K& key){HashFunc hf;//线性探测 //如果该位置没有元素，则直接插入元素 ，如果该位置有元素，找到下一个空位置，插入新元素size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY) //DELETE和EXIST{if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key){return  (HashData<const K, V>*) & _table[hashi];}}return nullptr;}bool Erase(const K& key){//先找到HashData<const K, V>* ret = Find(key);//再删除 if (ret != nullptr){ret->_state = DELETE;_n--;return true;}//没找到 return false;}public:vector<HashData<K, V>> _table;size_t  _n = 0; //存储有效数据的个数};}

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

开散列 （链地址法、哈希桶）

开散列，又叫哈希桶，首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

举例：
用除留余数法将序列{1,111,4,7,15,25,44,9}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的方式进行插入，插入过程如下：
在这里插入图片描述
将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点

闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0, 0.7]

开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：
哈希桶的负载因子可以更大，空间利用率高
哈希桶在极端情况下还有可用的解决方案

开散列实现（哈希桶）

哈希表的结构
struct HashNode{pair<K, V>  _kv;HashNode<K,V>* _next;HashNode(  const pair<K, V> & kv):_kv(kv),_next(nullptr){}};
Insert
	bool Insert(const pair<K,V> & kv){size_t hashi = kv.first % _table.size();//负载因子到1就扩容 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 != nullptr){Node* next = cur->_next;// 重新分配hashisize_t hashi = cur->_kv.first % _table.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}}}//头插 Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;return true;}

在这里插入图片描述

Find
	Node *   Find(const K & key){size_t hashi = key % _table.size();Node* cur = _table[hashi];while (cur != nullptr){if (key == cur->_kv.first){return cur;}cur = cur->_next;}return nullptr;}
Erase

32.png)

		bool Erase(const K & key){size_t hashi = key % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur != nullptr){if (key == cur->_kv.first){if(prev==nullptr)//第二种情况 ,prev是nullptr ,就是头删{_table[hashi] = cur->_next;}else//第一种情况 ,cur是头节点{prev->_next = cur->_next;}delete cur;return  true; }prev = cur;cur = cur->_next;}//没找到 return false;}

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 HashTable{public:typedef HashNode<K,V>  Node;//iterator begin()//{//}//iterator end()//{//}//const_iterator begin()//{//}//const_iterator end()//{//}//GetNextPrime()//{//}HashTable(){_table.resize(10, nullptr);}~HashTable(){}//bool Insert(const pair<K, V>  kv)//{//	//负载因子到1就扩容 //	if (_n == _table.size())//	{//		size_t 	newsize = _table.size() * 2;//		vector<Node*> newtable;//		newtable.resize(newsize, nullptr);//	}//	size_t hashi = kv.first % _table.size();//	//头插 //	Node* newnode = new Node(key);//	newnode->_next = _table[hashi];//	_table[hashi] = newnode;//	++_n;//	return true;//}bool Insert(const pair<K,V> & kv){size_t hashi = kv.first % _table.size();//负载因子到1就扩容 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 != nullptr){Node* next = cur->_next;// 重新分配hashisize_t hashi = cur->_kv.first % _table.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}}}//头插 Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;return true;}Node *   Find(const K & key){size_t hashi = key % _table.size();Node* cur = _table[hashi];while (cur != nullptr){if (key == cur->_kv.first){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K & key){size_t hashi = key % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur != nullptr){if (key == cur->_kv.first){if(prev==nullptr)//第二种情况 ,prev是nullptr ,就是头删{_table[hashi] = cur->_next;}else//第一种情况 ,cur是头节点{prev->_next = cur->_next;}delete cur;return  true; }prev = cur;cur = cur->_next;}//没找到 return false;}void Print(){for (size_t i = 0; i < _table.size(); i++){printf("[%d]->", i);Node* cur = _table[i];while (cur != nullptr){cout << cur->_kv.first << "->";cur = cur->_next;}printf("NULL\n");}cout << endl;}private:vector<Node*> _table;//指针数组size_t  _n = 0;//存储有效数据};
}

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2659765.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

【算法刷题】Day26

【算法刷题】Day26

文章目录 1. 买卖股票的最佳时机含冷冻期题干&#xff1a;算法原理&#xff1a;1. 状态表示&#xff1a;2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 代码&#xff1a; 2. 替换所有的问号题干&#xff1a;算法原理&#xff1a;代码&#xff1a; 1. 买卖股票的最佳时机含冷冻…
阅读更多...
组件间的值传递：改进若依框架中的BarChart.vue组件

组件间的值传递：改进若依框架中的BarChart.vue组件

改进前的BarChart 如下是若依(Ruoyi)框架中的BarChart.vue文件&#xff0c;该BarChart.vue无法实现组件间的值传递。到这里您不妨可以试试该如何去传值。如果您不想思考&#xff0c;请看改进后的BarChart。直接拿走使用&#xff01; <template><div :class"cla…
阅读更多...
大量数据的渲染优化-分页渲染方案

大量数据的渲染优化-分页渲染方案

文章目录 直接渲染数据的拆分使用定时器分页渲染 相信有一道耳熟能详的题目&#xff0c;如果前端获取到了 10w 条数据&#xff0c;应该怎么渲染&#xff1f;本文就以此为例&#xff0c;来进行切入&#xff0c;解析大量数据渲染的方案 直接渲染 样式代码比较简单&#xff0c;我就…
阅读更多...
Android原生实现单选

Android原生实现单选

六年前写的一个控件&#xff0c;一直没有时间总结&#xff0c;趁年底不怎么忙&#xff0c;整理一下之前写过的组件。供大家一起参考学习。废话不多说&#xff0c;先上图。 一、效果图 实现思路使用的是radioGroup加radiobutton组合方式。原理就是通过修改RadioButton 的backgr…
阅读更多...
vue3-富文本编辑器（vue-quill）

vue3-富文本编辑器（vue-quill）

官网&#xff1a;VueQuill | Rich Text Editor Component for Vue 3 安装 pnpm add vueup/vue-quilllatest 使用 局部使用 先导包 import { QuillEditor } from vueup/vue-quill import vueup/vue-quill/dist/vue-quill.snow.css; 再使用 <QuillEditor theme"snow…
阅读更多...
想要快速搭建知识付费平台？找明理信息科技！

想要快速搭建知识付费平台？找明理信息科技！

明理信息科技知识付费saas租户平台 一、确定目标群体 首先&#xff0c;你需要明确你的知识付费平台的目标用户是谁。这将帮助你确定所需的内容和功能&#xff0c;以及如何吸引和留住这些用户。例如&#xff0c;如果你的目标群体是职场新人&#xff0c;你的平台可能需要提供…
阅读更多...
MFC工程中无法使用cygwin64的库

MFC工程中无法使用cygwin64的库

文章目录 MFC工程中无法使用cygwin64的库概述在MFC中使用cygwin64的静态库在MFC中使用cygwin64的DLL进行静态包含在MFC中使用cygwin64的DLL进行动态调用唯一可以使用cygwin64的方法是进程隔离来通讯cygwin64的官方用途修正后的启动进程隐藏dos窗口的函数动态载入DLL的实现 - La…
阅读更多...
代码随想录27期|Python|Day29|回溯算法|491.递增子序列|46.全排列|47.全排列 II

代码随想录27期|Python|Day29|回溯算法|491.递增子序列|46.全排列|47.全排列 II

491. 非递减子序列 本题不是单纯的去重题目&#xff0c;而是需要保持数字在原数组的顺序。 比如&#xff1a;[4,5,6,7]和[4,6,5,7]相比&#xff0c;后者就不能选择[5,6,7]这个排列&#xff0c;因为违反了设置的顺序。所以去重的方法就只有哈希表。 需要在每一层设置一个哈希表…
阅读更多...
leaflet学习笔记-初始化vue项目（一）

leaflet学习笔记-初始化vue项目（一）

leaflet简介 Leaflet是一款开源的轻量级交互式地图可视化JavaScript库&#xff0c;能够满足大多数开发者的地图可视化需求&#xff0c;其最早的版本大小仅仅38 KB。Leaflet能够在主流的计算机或移动设备上高效运行&#xff0c;其功能可通过插件进行扩展&#xff0c;拥有易于使用…
阅读更多...
【Linux】指令(本人使用比较少的)——笔记(持续更新)

【Linux】指令(本人使用比较少的)——笔记(持续更新)

文章目录 ps -axj&#xff1a;查看进程ps -aL&#xff1a;查看线程echo $?&#xff1a;查看最近程序的退出码jobs&#xff1a;查看后台运行的线程组fd 任务号&#xff1a;将后台任务提到前台bg 任务号&#xff1a;将暂停的后台程序重启netstat -nltp&#xff1a;查看服务及监听…
阅读更多...
C#中的Attribute详解（下）

C#中的Attribute详解（下）

C#中的Attribute详解&#xff08;下&#xff09; 一、Attribute本质二、Attribute实例化三、Attribute实例化的独特之处四、元数据的作用五、自定义Attribute实例六、Attribute的附着目标七、附加问题 一、Attribute本质 从上篇里我们可以看到&#xff0c;Attribute似乎总跟pu…
阅读更多...
SAP VA01 创建带wbs号的销售订单包 CJ067的错误

SAP VA01 创建带wbs号的销售订单包 CJ067的错误

接口错误提示如下 SAP官方 CJ067 124177 - VA01: CJ067 during WBS acct assgmt with a different business area S4的core 刚好能用上 实施 这个note后成功
阅读更多...
nestjs入门教程系列(一):让项目先跑起来

nestjs入门教程系列(一):让项目先跑起来

nestjs启动基本步骤 Nest (NestJS) 是一个用于构建高效、可扩展的 Node.js 服务器端应用的框架。 它使用渐进式 JavaScript&#xff0c;构建并完全支持 TypeScript&#xff08;但仍然允许开发者使用纯 JavaScript 进行编码&#xff09;并结合了 OOP&#xff08;面向对象编程&am…
阅读更多...
第二节-数据封装+传输介质

第二节-数据封装+传输介质

数据传输的形式&#xff1a; 1.电路交换 2.报文交换&#xff1a; 在数据之外&#xff0c;加上能够标识接收者以及发送者的信息 3.分组交换&#xff1a; 依然进行报文交换&#xff0c;不过讲每个数据的大小进行定义 应用层&#xff08;数据data&#xff09;->传输层&am…
阅读更多...
K8S部署Harbor仓库实战

K8S部署Harbor仓库实战

K8S部署Harbor仓库实战 K8S部署Harbor仓库实战 - 简书 创建文件目录 chartmuseum目录: /var/nfs/data/harbor/chartmuseumdatabase目录: /var/nfs/data/harbor/databasejobservice目录: /var/nfs/data/harbor/jobserviceredis目录: /var/nfs/data/harbor/redisregistry目录:…
阅读更多...
深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第五节 引用类型复制问题及用克隆接口ICloneable修复

深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第五节 引用类型复制问题及用克隆接口ICloneable修复

深入浅出图解C#堆与栈 C# Heaping VS Stacking 第五节 引用类型复制问题及用克隆接口ICloneable修复 [深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈](https://mp.csdn.net/mdeditor/101021023)[深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第二节…
阅读更多...
【头歌实训】kafka-入门篇

【头歌实训】kafka-入门篇

文章目录 第1关&#xff1a;kafka - 初体验任务描述相关知识Kafka 简述Kafka 应用场景Kafka 架构组件kafka 常用命令 编程要求测试说明答案代码 第2关&#xff1a;生产者 &#xff08;Producer &#xff09; - 简单模式任务描述相关知识Producer 简单模式Producer 的开发步骤Ka…
阅读更多...
Python跳动的爱心完整代码

Python跳动的爱心完整代码

文章目录 环境需求完整代码详细分析环境需求 python3.11.4PyCharm Community Edition 2023.2.5pyinstaller6.2.0（可选，这个库用于打包，使程序没有python环境也可以运行，如果想发给好朋友的话需要这个库哦~）【注】 python环境搭建请见：https://want595.blog.csdn.net/arti…
阅读更多...
深入理解Mysql MHA高可用集群搭建：从实验到实战

深入理解Mysql MHA高可用集群搭建：从实验到实战

1. 简介 MHA&#xff08;Master High Availability&#xff09;是一个高效的开源MySQL高可用性解决方案。由日本开发者yoshinorim&#xff08;前DeNA员工&#xff0c;现在Facebook&#xff09;创建&#xff0c;MHA支持MySQL的主从复制架构&#xff0c;自动化主节点故障转移。当…
阅读更多...
支付宝 v3 验签如何实现

支付宝 v3 验签如何实现

上次给大家介绍了 支付宝 v3 自签名如何实现&#xff0c;这次顺便再把验签也写一下。 为什么要验签 说起为什么要验签&#xff0c;如果要详细一点解释的话&#xff0c;可以写很多很多...... 我们就简单一点来解释&#xff1a;验签可以证明接收到的信息是支付宝给我的&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023