哈希表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.mfbz.cn/a/619219.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

人脸消费给传统食堂带来的变化

消费的技术基础是脸部识别&#xff0c;脸部识别是基于人的容貌特征信息进行认证的生物特征识别技术&#xff0c;其突出的特征是以非接触方式进行识别&#xff0c;避免个人信息的泄露。 面部识别和指纹识别、掌纹识别、视网膜识别、骨骼识别、心率识别等都是人体生物特征识别技术…

STC8增强型单片机开发——串口调试UART

一、什么是串口 串口是一种在数据通讯中广泛使用的通讯接口&#xff0c;通常我们叫做UART (通用异步收发传输器Universal Asynchronous Receiver/Transmitter)&#xff0c;其具有数据传输速度稳定、可靠性高、适用范围广等优点。在嵌入式系统中&#xff0c;串口常用于与外部设备…

IDEA安装使用Git

IDEA安装使用Git 1 Git下载与安装 2 在IDEA中使用Git 2.1 IDEA中配置Git 在IDEA中使用Git&#xff0c;本质上还是使用本地安装的Git软件&#xff0c;所以需要在IDEA中配置Git。 2.2 在IDEA中使用Git 2.2.1 获取Git仓库 在IDEA中使用Git获取仓库有两种方式: 本地初始化仓库从…

Java | Leetcode Java题解之第85题最大矩形

题目&#xff1a; 题解&#xff1a; class Solution {public int maximalRectangle(char[][] matrix) {int m matrix.length;if (m 0) {return 0;}int n matrix[0].length;int[][] left new int[m][n];for (int i 0; i < m; i) {for (int j 0; j < n; j) {if (mat…

Unity Material(材质)、Texture(纹理)、Shader(着色器)简介

文章目录 一、概念二、Rendering Mode三、Main Maps三、参考文章 一、概念 Material(材质)&#xff1a;物体的“色彩”、“纹理”、“光滑度”、“透明度”、“反射率”、“折射率”、“发光度”等&#xff0c;材质的本质是shader的实例(载体)Texture(贴图)&#xff1a;附件到…

【kali工具使用】Tcpdump 抓包查看三次握手过程

Tcpdump 抓包查看三次握手过程 tcpdump 常用参数&#xff1a; -c 指定要抓取的数据包数量 -n 对 IP 地址以数字方式显式&#xff0c;否则显式为主机名 port 指定端口 -I 指定 tcpdump 需要监听的接口。默认会抓取第一个网络接口 tcp 1ClientSYN1seqx 2Server SYN1 seq…

从 Oracle 到 TiDB,国有大行打造本地生活 APP 新体验

导读 本文介绍了某国有大行推出的本地生活服务类 APP 在数字时代的创新应用实践。该 APP 利用金融科技和互联网平台模式&#xff0c;打造“金融非金融”的线上生态服务平台&#xff0c;满足了用户多样化的生活需求。为应对用户增长和数据量增加带来的挑战&#xff0c;该 APP 决…

地表净辐射通量数据、太阳辐射量数据、降雨量数据、气温数据、日照时长、水汽压分布、风速风向数据、地表温度

引言 地表净辐射作为驱动大气运动的主要能量&#xff0c;它是气候变化乃至全球变化的重要驱动力。由地表净辐射可反演比辐射率、地表温度、地表反照率等地表特征参数&#xff0c;是提高天气预报质量和大气环流模式研究的一个重要参数。多种卫星遥感数据反演地表净辐射通量信息产…

发表在期刊PRB和JAP上文章的说明及引用

文章目录 前言一、磁畴壁波导的能带调控研究&#xff08;in PRB&#xff09;文章简介&#xff1a;关键词&#xff1a;文章引用&#xff1a; 二、具有固定旋转轨道的自旋转矩纳米振荡器&#xff08;in JAP&#xff09;文章简介&#xff1a;关键词&#xff1a;文章引用&#xff1…

LeetCode-460. LFU 缓存【设计 哈希表 链表 双向链表】

LeetCode-460. LFU 缓存【设计 哈希表 链表 双向链表】 题目描述&#xff1a;解题思路一&#xff1a;一张图秒懂 LFU&#xff01;解题思路二&#xff1a;精简版&#xff01;两个哈希表&#xff0c;一个记录所有节点&#xff0c;一个记录次数链表【defaultdict(new_list)&#x…

kafka安装配置及集成springboot

1. 安装 单机安装kafka Kafka对于zookeeper是强依赖&#xff0c;保存kafka相关的节点数据&#xff0c;所以安装Kafka之前必须先安装zookeeper dockerhub网址: https://hub.docker.com Docker安装zookeeper 下载镜像&#xff1a; docker pull zookeeper:3.4.14创建容器 doc…

SeetaFace6人脸活体检测C++代码实现Demo

SeetaFace6包含人脸识别的基本能力&#xff1a;人脸检测、关键点定位、人脸识别&#xff0c;同时增加了活体检测、质量评估、年龄性别估计&#xff0c;并且顺应实际应用需求&#xff0c;开放口罩检测以及口罩佩戴场景下的人脸识别模型。 官网地址&#xff1a;https://github.co…

【CSP CCF记录】数组推导

题目 过程 思路 每次输入一个Bi即可确定一个Ai值&#xff0c;用temp记录1~B[i-1]&#xff0c;的最大值分为两种情况&#xff1a; 当temp不等于Bi时&#xff0c;则说明Bi值之前未出现过&#xff0c;Ai必须等于Bi才能满足Bi是Ai前缀最大的定义。当temp等于Bi时&#xff0c;则说…

后端开发之用Mybatis简化JDBC的开发快速入门2024及数据库连接池技术和lombok工具详解

JDBC 简化JDBC的开发 JDBC仅仅是一套接口 是一套规范 Mybatis是持久层框架 用于简化JDBC的开发 使用Java语言操作关系型数据库的一套API 原始的JDBC程序 package com.bigdate.mybatis;import com.bigdate.mybatis.mapper.UserMapper; import com.bigdate.mybatis.pojo.Use…

(二)Jetpack Compose 布局模型

前文回顾 &#xff08;一&#xff09;Jetpack Compose 从入门到会写-CSDN博客 首先让我们回顾一下上一篇文章中里提到过几个问题&#xff1a; ComposeView的层级关系&#xff0c;互相嵌套存在的问题&#xff1f; 为什么Compose可以实现只测量一次&#xff1f; ComposeView和…

【JVM】感觉弗如...类加载机制

【JVM】感觉弗如…类加载机制 在Java开发过程中&#xff0c;从源代码&#xff08;.java文件&#xff09;到字节码&#xff08;.class文件&#xff09;再到运行时的类加载&#xff0c;会经历几个关键步骤&#xff0c;我们先简单过一遍大体的过程。再介绍今天这篇博客的重点内容—…

几个字符串函数的使用和模拟实现(2)

strcop的使用和模拟实现 strcpy函数的使用事项&#xff1a; 源字符串时不需要修改的&#xff0c;在定义前加上const 源字符串被拷贝到目标字符串上时终止字符\0也被拷贝进去 目标数组的大小要相对于源数组的大小足够大&#xff0c;并且不应该在内存中重叠 函数的返回值是一个字…

【Unity】Unity项目转抖音小游戏(二)云数据库和云函数

业务需求&#xff0c;开始接触一下抖音小游戏相关的内容&#xff0c;开发过程中记录一下流程。 抖音云官方文档&#xff1a;https://developer.open-douyin.com/docs/resource/zh-CN/developer/tools/cloud/develop-guide/cloud-function-debug 1.开通抖音云环境 抖音云地址&a…

软件体系结构风格

目录 一、定义 二、.经典软件体系结构风格&#xff1a; 1.管道和过滤器 2.数据抽象和面向对象系统 3.基于事件系统&#xff08;隐式调用&#xff09; 4.分层系统 5.仓库 6.C2风格 7.C/S 8.三层C/S 9.B/S 题&#xff1a; 一、定义 软件体系机构风格是描述某一特定应用…

C#泛型委托

在C#中&#xff0c;delegate 关键字用于声明委托&#xff08;delegates&#xff09;&#xff0c;委托是一种类型安全的函数指针&#xff0c;允许你传递方法作为参数或从方法返回方法。有时我们需要将一个函数作为另一个函数的参数&#xff0c;这时就要用到委托&#xff08;Dele…