[C++][数据结构]哈希2:开散列/哈希桶的介绍和简单实现

前言

接着上一篇文章,我们知道了闭散列的弊端是空间利用率比较低,希望今天学习的开散列可以帮我们解决这个问题

引入

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

实现

基本结构

template<class K, class V>
struct HashNode
{HashNode<K, V>* _next;pair<K, V> _kv;
};
template<class K,class V>
class HashTable
{using Node = HashNode<K, V>;public://构造HashTable(size_t size = 10){_tables.resize(size, 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;}}private:vector<Node*> _tables;size_t _n = 0;
}

插入

在这里插入图片描述

这就是头插

		bool Insert(const pair<K, V>& kv){size_t hashi = kv.first % _tables.size();	//找到关键码Node* newnode = new Node(kv);				//创建新节点newnode->_next = _tables[hashi];			//先链接上_tables[hashi] = nuwnode;					//再更新头节点}

扩容

(可以参考set和map的扩容,都使用了提供的swap函数)

			if (_n == _tables.size()){vector<Node*> newTable(_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 = cur->_kv, first% newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}tables[i] = nullptr;}_tables.swap(newTables);}//扩容机制

删除

删除,删的是_key是key的这个桶,

返回值:
可以是bool也可以是下一个桶的指针

		bool Erase(const K& key){Hash hs;																//取出key的value值,//可以是仿函数、lambda,看传入的是什么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);//桶的平均大小}

补充

当某个桶数据过多时,我们可以把这个桶指向的节点变成红黑树,但什么时候变目前不去考虑

结语

文章写到这里有点戛然而止的感觉,不过本文主要是为了介绍概念、只实现了插入和删除。

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

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

相关文章

【HMWeb】HTML使用Leaflet实现本地离线地图Gis应用

下载Leaflet 官网下载&#xff1a;https://leafletjs.com/reference.html CSDN&#xff1a;https://download.csdn.net/download/hmxm6/89291989 选择版本号 添加html文件 加入代码 <!DOCTYPE html> <html lang"en"> <head><meta charset&qu…

富士Apeos 2350 NDA复印机报062 360代码故障

故障描述&#xff1a; 富士Apeos 2350 NDA复印机新机器刚拆箱安装&#xff0c;开机正常&#xff0c;自检扫描头一卡一卡的往前动几下就不动了、扫描灯也不亮扫描头也不能正常复位&#xff1b;按机器的复印键直接报062 360代码&#xff1b; 解答&#xff1a; 此代码为扫描故障&a…

聊天室项目思路

发起群聊&#xff1a; 从好友表选取人发送到服务器&#xff0c;服务器随机生成不重复的群号&#xff0c;存储在数据库&#xff0c;同时建立中间表&#xff0c;处理用户与群聊的关系 申请入群&#xff1a; 输入群号&#xff0c;发消息给服务器&#xff0c;服务器查询是否存在…

笔试强训week4

day1 Q1 难度⭐⭐ 小易的升级之路_牛客题霸_牛客网 (nowcoder.com) 题目&#xff1a; 小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 如果遇到的怪物防…

17 【Aseprite 作图】参考图和颜色

参考图 Aseprite 作图&#xff0c;“打开 - 一张参考图”&#xff0c;再把参考图拉到右边&#xff0c;就可以得到参考图和缩略图 取消选区 通过“选择 - 取消选择”&#xff0c;可以 取消选区 复制参考图的颜色 打开参考图后&#xff0c;参考图的调色板就会出现参考图所有的…

[Linux_IMX6ULL驱动开发]-GPIO子系统和Pinctrl子系统

目录 Pinctrl子系统的概念 GPIO子系统的概念 定义自己的GPIO节点 GPIO子系统的函数 引脚号的确定 基于GPIO子系统的驱动程序 驱动程序 设备树修改 之前我们进行驱动开发的时候&#xff0c;对于硬件的操作是依赖于ioremap对寄存器的物理地址进行映射&#xff0c;以此来达…

【智能优化算法】蜜獾优化算法(Honey Badger Algorithm,HBA)

蜜獾优化算法(Honey Badger Algorithm,HBA)是期刊“MATHEMATICS AND COMPUTERS IN SIMULATION”&#xff08;IF 3.6&#xff09;的2022年智能优化算法 01.引言 蜜獾优化算法(Honey Badger Algorithm,HBA)受蜜獾智能觅食行为的启发&#xff0c;从数学上发展出一种求解优化问题的…

Jetpack Compose一:初步了解Compose

Intellij IDEA构建Android开发环境 IntelliJ IDEA 2023.2.1 Android开发变化 IDEA配置使用Gradle 新建Compose工程&#xff0c;取名ComposeStudy 可以看到的是IDEA为项目初始化了部分代码 使用Compose开发不再需要使用xml文件来设计布局了 Compose中的Text也不同于Android V…

Flutter笔记:Widgets Easier组件库(13)- 使用底部弹窗

Flutter笔记 Widgets Easier组件库&#xff08;13&#xff09;使用底部弹窗 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this …

Android解放双手的利器之ViewBinding

文章目录 1. 背景2. ViewBinding是什么3. 开启ViewBinding功能4. 生成绑定类5. 使用ViewBinding5.1Activity 中使用5.2 Fragment 中使用5.3 ViewHolder 中使用 6. ViewBinding的优点7. 与 dataBinding 对比 1. 背景 写代码最繁琐的是什么&#xff1f;重复的机械操作。我们刚接…

【计算机毕业设计】springboot国风彩妆网站

二十一世纪我们的社会进入了信息时代&#xff0c; 信息管理系统的建立&#xff0c;大大提高了人们信息化水平。传统的管理方式对时间、地点的限制太多&#xff0c;而在线管理系统刚好能满足这些需求&#xff0c;在线管理系统突破了传统管理方式的局限性。于是本文针对这一需求设…

自动驾驶系统中的数据闭环:挑战与前景

目录 自动驾驶概况 1.1自动驾驶分级 1.2自动驾驶国内发展 ​1.3自动驾驶架构模型 数据闭环的意义 2.1 搜集corner case的数据 2.2 提高模型的泛化能力 2.3 驱动算法迭代 数据闭环落地的痛点及对策 3.1 数据采集和使用的合规性问题 3.2 数据确权问题 3.3 数据采集…

Vue3知识总结-1

前面学习一段时间的前端&#xff0c;但是没有进行过太多的练习&#xff0c;并且对于里面一些重要的知识点也没有去着重的记忆&#xff0c;所以打算在学习Vue3的时候&#xff0c;做一些笔记&#xff0c;方便后面翻看。这个笔记会对于学习一些做一些&#xff0c;而不是一个整体的…

利用AI提高内容生产效率的五个方案

目录 如何利用AI提高内容生产效率? ​编辑方向一&#xff1a;自动化内容生成 方向二&#xff1a;内容分发与推广 方向三&#xff1a;内容分析与优化 方向四&#xff1a;图像和音频处理 方向五&#xff1a;自动编辑和校对 如何利用AI提高内容生产效率? 简介&#xff1a…

智慧公厕,小民生里的“大智慧”!

公共厕所是城市社会生活的基础设施&#xff0c;而智慧公厕则以其独特的管理模式为城市居民提供更优质的服务。通过智能化的监测和控制系统&#xff0c;智慧公厕实现了厕位智能引导、环境监测、资源消耗监测、安全防范管理、卫生消杀设备、多媒体信息交互、自动化控制、自动化清…

AzureDataFactory 表选项之自动创建表

接上篇, 该篇里表与表之间采取了提前mapping的方式&#xff0c;通过Import schemas的方式将源和目标的表的schemas做了一对一的匹配 但如果我的应用场景是将D365的表数据推送到外部数据源&#xff0c;需要原表clone&#xff0c;如果我去先建表建字段再做mapping未免过于繁琐&am…

JDK1.8的安装及环境变量的配置(超详细图文)

0.JDK 简介 JDK&#xff0c;全称Java Development Kit&#xff0c;是Java语言的软件开发工具包&#xff0c;主要用于Java程序的开发。 1.首先下载JDK安装包 下载安装jdk1.8或jdk17(可以去官方下载) 这里提供一份网盘下载地址&#xff0c;大家按需自取&#xff1a;点击这里下…

CTF例题和知识点

[ACTF2020 新生赛]Include 打开靶机发现一个超链接&#xff0c;点击之后出现一段话 “Can you find out the flag?” 查看源码注入&#xff0c;无果 仔细看url&#xff0c;发现有flag.php 根据题目提示&#xff0c;该题应该是文件包含漏洞&#xff0c;因此可以判断出此题是PH…

FreeRTOS标准库例程代码

1.设备STM32F103C8T6 2.工程模板 单片机: 部分单片机的程序例程 - Gitee.comhttps://gitee.com/lovefoolnotme/singlechip/tree/master/STM32_FREERTOS/1.%E5%B7%A5%E7%A8%8B%E6%A8%A1%E6%9D%BF 3.代码 1-FreeRTOS移植模板 #include "system.h" #include "…

基础算法,贪心算法,贪心策略,OJ练习

文章目录 一、概念二、OJ练习2.1 区间选点2.2 区间合并2.3 区间2.4 合并果子2.5 排队接水2.6 货仓选址2.7 防晒2.8 畜栏预定2.9 雷达设备2.10 国王游戏2.11 耍杂技的牛2.12 给树染色2.13 任务2.14 能量石 三、总结 一、概念 贪心是一种在每次决策时采取当前意义下最优策略的算…