哈希表Hash table

哈希表是根据关键码的值而直接进行访问的数据结构。

数组就是⼀张哈希表。

哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素,如下图所示:

那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断⼀个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n),但如果使用哈希表的话,只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里,在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

哈希函数

哈希函数,把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于哈希表的大小了,也就是大于tableSize了,怎么办呢?

此时为了保证映射出来的索引数值都落在哈希表上,我们会在再次对数值做一个取模的操作,就要我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了,哈希表我们刚刚说过,就是一个数组。

如果学生的数量大于哈希表的大小怎么办,此时就算哈希函数计算的再均匀,也避免不了会有几位学生的名字同时映射到哈希表同⼀个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示,小李和小王都映射到了索引下标 1 的位置,这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法,拉链法和线性探测法。

拉链法

刚刚小李和小王在索引 1 的位置发生了冲突,发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了

(数据规模是dataSize,哈希表的大小为tableSize)

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法,⼀定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置,放了小李,那么就向下找⼀个空位放置小王的信息。所以要求tableSize⼀定要⼤于dataSize,要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示:

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

1.数组

2.set(集合)

3.map(映射)

这里数组就没啥可说的了,我们来看⼀下set和map。

std::unordered_set底层实现为哈希表,std::set和std::multiset的底层实现是红黑树,红黑树是⼀种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

std::unordered_map底层实现为哈希表,std::map和std::multimap的底层实现是红黑树。同理,std::map和std::multimap的key也是有序的

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map,在map是一个key value的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset的底层实现是红黑树,不是哈希表,std::set、std::multiset使用红黑树来索引和存储,不过给我们的使用方式,还是哈希法的使用方式,即key和value。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。map也是⼀样的道理。

有效的字母异位词

就是判断 s 和 t 是否是由相同的字符组成

数组其实就是⼀个简单哈希表,而且这道题目中字符串只有小写字符,那么就可以定义一个数组,来记录字符串 s 里字符出现的次数。

定义⼀个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上,因为字符a到字符z的ASCII是26个连续的数值,所以字符a映射为下标0,相应的字符z映射为下标25

再遍历字符串s的时候,只需要将s[i] - ‘a’所在的元素做+1操作即可,并不需要记住字符a的ASCII,只要求出一个相对数值就可以了。这样就将字符串s中字符出现的次数,统计出来了。

那看一下如何检查字符串 t 中是否出现了这些字符,同样在遍历字符串t的时候,对 t 中出现的字符映射哈希表索引上的数值再做 -1 的操作。

那么最后检查一下,record数组如果有的元素不为零0,说明字符串 s 和 t 一定是谁多了字符或者谁少了字符,return false。

class solution
{
public:bool cmp(string s, string t){int record[26] = { 0 };for (int i = 0; i < s.size(); ++i){record[s[i] - 'a']++;}for (int i = 0; i < t.size(); ++i){record[t[i] - 'a']--;}for (int i = 0; i < 26; ++i){if (record[i] != 0){return false;}}return true;}
};

两个数组的交集

题意:给定两个数组,编写一个函数来计算它们的交集。

这道题目,主要要学会使用一种哈希数据结构:unordered_set,这个数据结构可以解决很多类似的问题。

注意题目特意说明:输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的,同时可以不考虑输出结果的顺序

思路如图所示:

代码:

# include <iostream>
# include <vector>
# include <unordered_set>
using namespace std;int main()
{vector<int> nums1;vector<int> nums2;int n;int m;cin >> n >> m;int x;for (int i = 0; i < n; ++i){cin >> x;nums1.push_back(x);}for (int i = 0; i < m; ++i){cin >> x;nums2.push_back(x);}unordered_set<int> result;unordered_set<int> nums(nums1.begin(), nums1.end());for (int num : nums2){if (nums.find(num) != nums.end())result.insert(num);}}

快乐数

# include <iostream>
# include <vector>
# include <unordered_set>
using namespace std;int made(int x)
{int sum = 0;while (x > 0){sum = sum + (x % 10) * (x % 10);x = x / 10;}return sum;
}bool cmp(int x)
{unordered_set<int> last;int s = x;while (1){s = made(s);if (last.find(s) == last.end()){if (s == 1)return true;last.insert(s);}else{return false;}}
}int main()
{int n;cin >> n;cout << bool(n);
}

两数之和

首先我在强调一下什么时候使用哈希法,当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。

本题呢,我就需要一个集合来存放我们遍历过的元素,然后在遍历数组的时候去询问这个集合,某元素是否遍历过,也就是是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本地,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用key value结构来存放,key来存元素,value来存下标,那么使用map正合适。

再来看⼀下使用数组和set来做哈希法的局限。

1.数组的大小是受限制的,而且如果元素很少,而哈希值太大会造成内存空间的浪费。

2.set是⼀个集合,里面放的元素只能是⼀个key,而两数之和这道题目,不仅要判断y是否存在,而且还要记录y的下标位置,因为要返回x和y的下标。所以set也不能用

此时就要选择另⼀种数据结构:map,map是⼀种key value的存储结构,可以用key保存数值,用value在保存数值所在的下标。

这道题目中并不需要key有序,选择std::unordered_map效率更高!

接下来需要明确两点:

        1.map用来做什么

        2.map中key和value分别表示什么

map用来存放我们访问过的元素

数组中的元素作为key,有key对应的就是value,value用来存下标。

# include <iostream>
# include <vector>
# include <unordered_map>
using namespace std;int main()
{int num[100];int n;int target;cin >> n >> target;unordered_map<int, int> map;for (int i = 0; i < n; ++i){cin >> num[i];}for (int i = 0; i < n; ++i){if (map.find(target - num[i]) != map.end()){auto iter = map.find(target - num[i]);cout << i << iter->second;}map.insert(pair<int, int>{ num[i], i });}
}

四数相加II

例如:

输⼊:

A = [1,  2]

B = [ -2, -1]

C = [-1, 2]

D = [ 0, 2]

输出:

2

本题是使用哈希法的经典题目,这道题目是四个独立的数组,只要找到A[i] + B[j] + C[k] + D[l] = 0就可以,不用考虑有重复的四个元素相加等于0的情况。

# include <iostream>
# include <vector>
# include <unordered_map>
using namespace std;int main()
{int n;cin >> n;int a[500];int b[500];int c[500];int d[500];for (int i = 0; i < n; ++i){cin >> a[i];}for (int i = 0; i < n; ++i){cin >> b[i];}for (int i = 0; i < n; ++i){cin >> c[i];}for (int i = 0; i < n; ++i){cin >> d[i];}unordered_map<int, int>map;for (int i : a){for (int j : b){map[i + j]++;}}int count = 0;for (int i : c){for (int j : d){if (map.find(0 - i - j) != map.end())count = count + map[0 - i - j];}}cout << count;
}

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

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

相关文章

Git Bash和Git GUI设置中文的方法

0 前言 Git是一个分布式版本控制系统&#xff0c;可以有效、高速地处理从很小到非常大的项目版本管理。一般默认语言为英文&#xff0c;本文介绍修改Git Bash和Git GUI语言为中文的方法。 1 Git Bash设置中文方法 &#xff08;1&#xff09;鼠标右键&#xff0c;单击“Git B…

redis深入理解之实战

1、SpringBoot整合redis 1.1 导入相关依赖 <dependency><groupId>redis.clients</groupId><artifactId>jedis</artifactId> </dependency> <dependency><groupId>org.springframework.boot</groupId><artifactId&g…

HTML标签快速入门

文章目录 一、HTML语法规范1.1 基本语法概述1.2 标签关系 二、HTML基本结构标签2.1 第一个HTML网页2.2 基本结构标签总结 三、网页开发工具3.1 文档类型声明标签3.2 lang 语言种类3.3 字符集3.4 总结 四、HTML常用标签4.1 标签语义4.2 标题标签\<h1> - \<h6>&#…

[Linux][网络][数据链路层][一][以太网][局域网原理]详细讲解

目录 0.对比理解"数据链路层"和网络层1.以太网1.认识以太网2.以太网帧格式3.认识MAC地址4.以太网帧格式如何封装/解包&#xff1f;5.以太网帧格式如何分用&#xff1f; 2.重谈局域网通信原理0.如何形象的理解&#xff1f;1.理解局域网通信2.在发送数据的时候&#xf…

STC8增强型单片机开发【LED呼吸灯(PWM)⭐⭐】

目录 一、引言 二、硬件准备 三、PWM技术概述 四、电路设计 五、代码编写 EAXSFR&#xff1a; 六、编译与下载 七、测试与调试 八、总结 一、引言 在嵌入式系统开发中&#xff0c;LED呼吸灯是一种常见的示例项目&#xff0c;它不仅能够展示PWM&#xff08;脉冲宽度调制…

STM32快速入门(总线协议之I2C一主多从(软件实现 硬件实现))

STM32快速入门&#xff08;总线协议之I2C一主多从&#xff08;软件实现 & 硬件实现&#xff09;&#xff09; 前言 支持一对多&#xff08;一主多从&#xff09;、多对多传输&#xff08;多主多从&#xff09;&#xff0c;只支持半双工&#xff0c;一般有两根数据线&…

使用Baidu Comate五分钟 , 工作时间摸鱼8小时

Baidu Comate&#xff1a;引领智能编码新时代 文章目录 Baidu Comate&#xff1a;引领智能编码新时代一、明日工具&#xff0c;今日领先——百度Comate智能编码助手二、万变不离其宗——适配场景需求三、功能研究3.1 指挥如指掌——指令功能3.2 助手增援——插件功能使用3.3 实…

8个免费无版权视频素材网站,高清无水印视频任性下载

在数字化时代&#xff0c;优质的视频素材成为各种项目不可缺少的元素&#xff0c;从短片制作到商业广告&#xff0c;高品质的视频能显著提高作品的吸引力和传播效果。然而&#xff0c;寻找既免费又无版权问题的高清视频素材并非易事。以下介绍几个优秀的免费视频素材网站&#…

猜猜歇后语

页面 在输入框中填写你猜的答案&#xff0c;点击“显示答案”按钮&#xff0c;显示正确答案。 页面代码 function showAnswer(element){var elem$(element);elem.next().show();} //# // 初始化DataGrid对象 $(#dataGrid).dataGrid({searchForm: $(#searchForm),columnModel:…

k8s 数据流向 与 核心概念详细介绍

目录 一 k8s 数据流向 1&#xff0c;超级详细版 2&#xff0c;核心主键及含义 3&#xff0c;K8S 创建Pod 流程 4&#xff0c;用户访问流程 二 Kubernetes 核心概念 1&#xff0c;Pod 1.1 Pod 是什么 1.2 pod 与容器的关系 1.3 pod中容器 的通信 2&#xff0c; …

Sping源码(七)—ConfigurationClassPostProcessor ——@PropertySources解析

序言 先来简单回顾一下ConfigurationClassPostProcessor大致的一个处理流程&#xff0c;再来详细的讲解PropertySources注解的处理逻辑。 详细的步骤可参考ConfigurationClassPostProcessor这篇帖子。 流程图 从获取所有BeanDefinition -> 过滤、赋值、遍历 -> 解析 -&…

CCleaner系统优化与隐私保护工具,中文绿色便携版 v6.23.11010

01 软件介绍 CCleaner 是一款高级的系统优化工具&#xff0c;其设计宗旨在于彻底清理 Windows 操作系统中积累的无用文件和冗余的注册表项。此举旨在显著提升计算机的运行效率并回收磁盘空间。该软件拥有高效的能力&#xff0c;可以清除包括临时文件、浏览器缓存及其历史记录在…

windows系统安装Ubuntu子系统

安装前先在 控制面板 中打开 程序与功能选项 &#xff0c;点击 启用或关闭Windows功能&#xff1a; 勾选 适用于 Linux的Windows子系统 和 虚拟机平台 、 Hyper-v 。 重启电脑后再 Microsoft Store Windows应用商店 中下载合适的Ubuntu版本。 运行Ubuntu程序&#xff0c;如出现…

如何在huggingface上申请下载使用llama2/3模型

1. 在对应模型的huggingface页面上提交申请 搜索对应的模型型号 登录huggingface&#xff0c;在模型详情页面上&#xff0c;找到这个表单&#xff0c;填写内容&#xff0c;提交申请。需要使用梯子&#xff0c;country填写梯子的位置吧(比如美国&#xff09; 等待一小时左右…

四川景源畅信:小白做抖音电商怎么样?

在数字时代&#xff0c;抖音已成为一个不可忽视的电商平台。对于初入行的小白来说&#xff0c;涉足抖音电商似乎既充满机遇又伴随着挑战。要判断小白做抖音电商的可行性&#xff0c;我们不妨从几个关键方面进行深入探讨。 一、市场趋势与流量获取 抖音作为新媒体的代表之一&…

web移动端调试——vconsole

因为项目是嵌套app内的H5界面&#xff0c;没办法直接查看控制台&#xff0c;所以使用了这个插件vconsole 一、使用 cdn 方式引入 <script src"https://cdn.bootcss.com/vConsole/3.3.4/vconsole.min.js"></script> <script> // 初始化 var vConso…

PyTorch的卷积和池化

卷积计算 input 表示输入的图像filter 表示卷积核, 也叫做滤波器input 经过 filter 的得到输出为最右侧的图像&#xff0c;该图叫做特征图 卷积的计算是将卷积核放入左上角&#xff0c;在局部区域间做点积&#xff0c;然后将卷积核在Input上面依次从左向右&#xff0c;从上到下…

高校课程评价|基于SSM+vue的高校课程评价系统的设计与实现(源码+数据库+文档)

高校课程评价系统 目录 基于SSM&#xff0b;vue的高校课程评价系统的设计与实现 一、前言 二、系统设计 三、系统功能设计 1管理员功能模块 2学生功能 3教师功能 4专家功能 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&…

Linux FT260驱动内核学习笔记

目录 1. 安装ft260驱动 2. 编译ft260源码 3. 通过sysfs配置ft260设备 3.1 多功能GPIO配置 3.2 控制GPIO 3.3 配置i2c总线频率 4. UART 5. 使用i2c-tools交互I2C设备 5.1 安装i2c-tools 5.2 探测I2C设备 5.3 读取所有寄存器数据 5.4 读取和写入 5.5 16位地址的读写…

web前端之纯CSS实现简单酷炫的照片墙效果、排除元素的伪类、scale

MENU 效果htmlstylescale:not() 效果 html <div class"container"><div class"box"><img src"../../image/1_.jpg"></div><div class"box"><img src"../../image/2_.jpg"></div>…