当前位置: 首页 > news >正文

哈希表——C++

目录

一、首先使用拉链法:

 二、开放寻址法

三、字符串哈希

1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图

2.接下来说一说算某个中间的区间的字符串哈希值


哈希表是一种数组之间互相映射的数据结构,比如举个简单的例子一个十个的数组要用一个五个的数组表示,我们可以使用取模的方法将十个数组中的数组映射到五个数字的小数组中。

核心思想是将数据项的键值(Key)通过哈希函数转换成数组的索引,从而直接访问数组中的位置来存储或查找数据项。

但是一个大的数组映射到小的数组中是很难避免映射冲突的问题的,为了解决这类问题,我们常用两个方法来解决;

  • 拉链法
  • 开放寻址法

一、首先使用拉链法:

拉链法顾名思义就是一个数组,每个数组上链接一个单链表,形状类似拉链,故拉链。

 但是如何取模运算,是我们需要解决的问题。

听y总说寻找大于规定范围最小的质数是冲突最小(我不知道为撒,但是听说数学有证明)

#include<iostream>
#include<cstring>
using namespace std;int main()
{for(int i=1e5;;i++){bool flag=true;for(int j = 2 ; j * j <=i;j++){if(i % j == 0){flag=false;break;}}if(flag){cout<<i<<endl;break;}}return 0;
}

例题:https://www.acwing.com/activity/content/problem/content/890/

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+3;
int h[N],e[N],ne[N],idx;void insert(int x)
{int k=(x%N+N)%N;  //保证k的值不为负数e[idx]=x;ne[idx]=h[k];h[k]=idx;idx++;
}bool find(int x)
{int k=(x%N+N)%N;  //保证k的值不为负数for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==x)  return true;}return false;
}int main()
{int m;cin>>m;memset(h,-1,sizeof (h));while(m--){char op[2];int x;scanf("%s%d",op,&x);if(*op=='I'){insert(x);}else{if(find(x)) puts("Yes");elseputs("No");}}return 0;
}

 二、开放寻址法

开放寻址法可以叫它为蹲坑法,通常N要是数据范围的两倍,然后找最小的大于数据范围的质数

然后在相应的地方进行插入数据。

#include<iostream>
#include<cstring>
using namespace std;const int N=200003,null=0x3f3f3f3f;
int h[N];int find(int x)
{int k=(x % N + N) % N;while(h[k]!=null && h[k]!=x){k++;//到头就从头再来if(k==N) k=0;}return k;//保证k要么是空位置的地址,要么是这个数已经被存放过了
}int main()
{int n;scanf("%d",&n);memset(h,0x3f,sizeof h);while(n--){char op[2];int x;scanf("%s%d",op,&x);if(*op == 'I'){h[find(x)] = x;}else{if(h[find(x)] == null) puts("No");else puts("Yes");}}return 0;
}

三、字符串哈希

一般常使用哈希来解决字符串的问题,常用的方法就是将一个字符串差分成字符前缀,然后存储每个字符前缀的哈希值,然后这个哈希值常使用一种进制的表示方式来确定,然后在进行取余。(要点:一般使用131进制,取余的除数是2^{^{^{64}}},而且使用unsigned long long 来存储也就可以通过溢出直接进行自动取余)。

1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图

需要注意的是这里的哈希值的处理方式我们需要认为是不存在冲突的,这一点和之前的数值哈希有所不同,而且还要注意的是在映射的时候是不可以映射成为0的。

举个例子解释一下

如何某个字符前缀会映射成为0,那比如说A是0,那AB也就是0了,这样是不符合要求的。

2.接下来说一说算某个中间的区间的字符串哈希值

如图所示,最重要的公式就是h[R]-h[l-1]*p^{r-l+1}

举个例子方便理解

我们在预处理h[i] 数组的时候,是把左边看成高位,右边看成低位(这与我们的习惯是相同的)
下面给出例子,计算[4,5]之间"de" 的哈希值   高位   a       b   c   d    e  低位  
                                                                               a        b      c  
                                             这是数组的下标        1      2   3    L    R   
                                       这里是P进制下位权    (p^4)  p^3  p^2   p^1   1

   我们在前缀和那节课已经学过了,怎么计算区间的部分和.  h[R] - h[L - 1].
   仔细一看,不对劲,位置对不上. 因此我们将字符串 "左移",为他们补上位权,这样子就能做到一一对应
                                    高位    a       b   c   d    e  低位  
                                                 a      b   c   '\0' '\0'
                 这是数组的下标        1      2   3    L    R   
         这里是P进制下位权    (p^4)  p^3  p^2   p^1   1

    为了方便理解,我用"\0"表示无意义字符. 这个时候就能计算了对吧?
    那位移是多少呢?
    就是 R - L + 1,在本例中, 5 - 3 + 1 = 2,左移两位. 补齐低位.

例题:https://www.acwing.com/activity/content/problem/content/891/

#include<iostream>
using namespace std;const int N=1e5+10,jinzhi=131;unsigned long long h[N],p[N];//h是存放每个字符子串的哈希值,p是存放字符串的权重的
char str[N];int get(int l,int r)
{return h[r]-h[l-1]*p[r-l+1];
}int main()
{int n,m;scanf("%d%d",&n,&m);scanf("%s",str+1);//初始化p[0]=1;for(int i=1;i<=n;i++){h[i]=h[i-1]*jinzhi+str[i];p[i]=p[i-1]*jinzhi;}while(m--){int l1,l2,r1,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);if(get(l1,r1)==get(l2,r2)){puts("Yes");}else puts("No");}return 0;
}

相关文章:

哈希表——C++

目录 一、首先使用拉链法&#xff1a; 二、开放寻址法 三、字符串哈希 1.具体如何使用进制的方式来存储字符前缀的可以看这个y总的这个图 2.接下来说一说算某个中间的区间的字符串哈希值 哈希表是一种数组之间互相映射的数据结构&#xff0c;比如举个简单的例子一个十个的数…...

LabVIEW叶片厚度远程监控

LabVIEW叶片厚度远程监控 随着网络技术的高速发展&#xff0c;远程监控广泛应用在各个领域。本文介绍了一种基于LabVIEW的植物叶片厚度远程监控系统&#xff0c;旨在实现对植物生长状况的精准监测和分析。 该系统利用LabVIEW软件开发工具&#xff0c;通过TCP网络协议实现数据…...

el-table动态合并

废话就不多说了&#xff0c;直接上代码&#xff01;&#xff01;&#xff01; 合并行 // 方法一 <template><div class"container"><el-table :data"dataSource" :border"true":header-cell-style"{ font-weight: normal,…...

【DevOps】产品需求文档(PRD)与常见原型软件

文章目录 1、PRD介绍1.1、概述1.2、前提条件1.3、主要目的1.4、关键内容1.5、表述方式1.6、需求评审人员1.7、一般内容结构 2、需求流程3、常见原型软件3.1、Word3.2、Axure3.2.1、详细介绍3.2.2、应用分类3.2.3、优缺点 3.3、摹客RP3.4、蓝湖3.5、GUI Design Studio 1、PRD介绍…...

【QT+QGIS跨平台编译】之十八:【Expat+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、Expat介绍二、文件下载三、文件分析四、pro文件五、编译实践一、Expat介绍 Expat库最初由James Clark创建,已经成为许多编程语言中常用的XML解析工具。它以其简单、快速和可靠的特点而受到广泛的认可和使用。 Expat库的优点包括: 快速:Expat的解析速度非常快…...

20240203

1.项目经理正在为新项目制订进度计划&#xff0c;项目的成功取决于使用需要政府颁发特殊环境许可证的设备&#xff0c;在网络图的设计过程中&#xff0c;项目经理应该做什么以确保正确的活动排序&#xff1f; A.使用滚动式规划考虑项目不确定性 B.分析外部依赖关系&#xff0c;…...

【Spark实践6】特征转换FeatureTransformers实践Scala版--补充算子

本节介绍了用于处理特征的算法&#xff0c;大致可以分为以下几组&#xff1a; 提取&#xff08;Extraction&#xff09;&#xff1a;从“原始”数据中提取特征。转换&#xff08;Transformation&#xff09;&#xff1a;缩放、转换或修改特征。选择&#xff08;Selection&…...

【知识点】设计模式

创建型 单例模式 Singleton&#xff1a;确保一个类只有一个实例&#xff0c;并提供该实例的全局访问点 使用一个私有构造方法、一个私有静态变量以及一个公有静态方法来实现。私有构造方法确保了不能通过构造方法来创建对象实例&#xff0c;只能通过公有静态方法返回唯一的私…...

WPS WORD 宏导出高亮文本

WPS手机版可以直接导出高亮文本&#xff0c;但只能导出手机编辑的部分&#xff0c;如果同时在电脑上编辑过&#xff0c;电脑上高亮的无法导出&#xff0c;因为作者不一样。 但WPS电脑版没有这个功能&#xff0c;只能通过宏编程实现。 这里利用了审阅模式&#xff0c;在文字高亮…...

python 基础知识点(蓝桥杯python科目个人复习计划32)

今日复习内容&#xff1a;基础算法中的位运算 1.简介 位运算就是对二进制进行操作的运算方式&#xff0c;分为与运算&#xff0c;或运算&#xff0c;异或运算&#xff0c;取反&#xff0c;左移和右移。 &#xff08;1&#xff09;与运算 xyx&y000010100111 (2)或运算 …...

(算法二)滑动窗口

滑动窗口&#xff1a;既一块区域进行滑动&#xff0c;且不回退 往往解决的是一段连续空间中满足条件的最长或者最短子数组&#xff08;串&#xff09; 是由暴力解法&#xff08;优化&#xff09;——>不回退的滑动窗口解法 长度最小的子数组 无重复字符的最长子数组 此类题…...

【Go语言成长之路】Hello Go

文章目录 Hello Go一、建立工程目录二、开启代码追踪三、编写代码四、测试代码 Hello Go 一、建立工程目录 pzspzs-ubuntu22:~$ mkdir go_study/hello -p pzspzs-ubuntu22:~$ cd go_study/hello​ 在hello目录下&#xff0c;我们会编写属于自己的第一个Go demo例子&#xff0…...

大数据应用开发3-Scala笔记1

一、编程框架 Scala语言是在JVM上运行的&#xff0c;兼容Java语法 区分大小写 - Scala是大小写敏感的&#xff0c;这意味着标识Hello 和 hello在Scala中会有不同的含义。 类名 - 对于所有的类名的第一个字母要大写。 如果需要使用几个单词来构成一个类的名称&#xff0c;每个…...

android 网络拦截器统一处理请求参数和返回值加解密实现

前言 项目中遇到参数加密和返回结果加密的业务 这里写一下实现 一来加深记忆 二来为以后参考铺垫 需求 项目在开发中涉及到 登陆 发验证码 认证 等前期准备接口 这些接口需要单独处理 比如不加密 或者有其他的业务需求 剩下的是登陆成功以后的业务需求接口 针对入参和返回值…...

Jmeter直连mysql数据库教程

mysql数据库能够通过Navicat等远程连接工具连接 下载驱动并加入jmeter 1.mysql驱动下载地址&#xff1a;MySQL :: Download MySQL Connector/J (Archived Versions) 找到对应的驱动下载&#xff1a;如下图&#xff1a; 把驱动jar包加入jmeter 配置jmeter连接mysql数据库…...

2024美赛数学建模B题思路分析 - 搜索潜水器

1 赛题 问题B&#xff1a;搜索潜水器 总部位于希腊的小型海上巡航潜艇&#xff08;MCMS&#xff09;公司&#xff0c;制造能够将人类运送到海洋最深处的潜水器。潜水器被移动到该位置&#xff0c;并不受主船的束缚。MCMS现在希望用他们的潜水器带游客在爱奥尼亚海底探险&…...

Tomcat在Java web的应用

Tomcat在Java web的应用 本来这篇博客顺应之前的内容&#xff0c;应该是需要写Tomcat的简介、基本使用、配置和部署项目、Web的项目结构、创建MavenWeb、idea本地集成以及Tomcat的Maven插件的笔记内容&#xff0c;但是总觉得没必要&#xff0c;因为这些内容网上肯定很多了&…...

Python爬虫某云免费音乐——多线程批量下载

重点一&#xff1a;每首音乐的下载地址 重点二&#xff1a;如何判断是免费音乐 重点三&#xff1a;如何用线程下载并保存 重点四&#xff1a;如何规避运行错误导致子线程死掉 重点五&#xff1a;如何管理子线程合理运行 需要全部代码的私信或者VX:Kmwcx1109 运行效果&…...

Python实现TCP和UDP通信

目录 一&#xff1a;TCP 二&#xff1a;UDP 一&#xff1a;TCP 在Python中实现TCP通信可以通过使用内置的socket模块来完成。以下是一个简单的示例&#xff0c;展示了如何使用Python的socket模块创建一个TCP客户端和服务器。 TCP服务器 import socket def start_server(): s…...

用HTML5 + JavaScript实现下雪效果

用HTML5 JavaScript实现下雪效果 下面是用HTML5 JavaScript实现下雪效果示例&#xff0c;展示了如何使用 HTML5 的 <canvas> 元素以及 JavaScript 来创建下雪效果。效果如下&#xff1a; 源码如下&#xff1a; <!DOCTYPE html> <html lang"en">…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...