哈希表(c++)
1、介绍
哈希表,也称为散列表,是一种非常高效的数据结构。它通过将键(Key)映射到数组的特定位置来快速查找、插入和删除数据。这个映射过程由哈希函数(Hash Function)完成,该函数将键转化为一个整数,该整数用作数组的下标。
2、实现

哈希表将一个很大的集合映射成0~N
例如: 将x属于(-10^9 ~ 10^9)映射到0~10^5里
两部操作首先: x mod 10^5;其次 : 解决冲突{两种办法:{拉链发 和 开放寻址法}}
上述需要注意在做模运算的时候,最好取比10^5第一个大的质数模,这样会减少冲突,冲突指的是会映射到一个地方去
2.1、拉链法
图解:

注意:算法题里,一般只会考添加和查找,几乎很少考删除操作,就算考删除,也不会真的删除,只是跳过这个点
添加操作和查找操作类似于单链表
如图:

2.2、开放寻址法
此方法只需要一个一维数组就可以实现
规则:
空间开到2~3倍的N:目的是可以减少冲突
这里同样要找到开的N的第一个质数

3、例题:840. 模拟散列表 - AcWing题库

拉链法:
#include<iostream>
#include<cstring>using namespace std;
//找到100000的第一个质数去mod会减少冲突
const int N = 100003;
//h[]表示映射数组,e[],ne[]是单链表e存数,ne指向下一个节点,idx分配空间
int h[N],e[N],ne[N],idx;
//拉链法的存入操作
void insert(int x)
{//先让x%N是为了避免负数很大的情况,不能先加N再mod。int k = (x % N + N) % N; e[idx] = x;//存入xne[idx] = h[k];//指针连到哈希表中h[k] = idx++;//让当前映射的值,去记录开辟了多少空间,存一下,方便后面查找
}bool find(int x)
{int k = (x % N + N) % N;for(int i=h[k];i!=-1;i=ne[i]){if(e[i] == x){return true;}}return false;
}int main()
{int n;scanf("%d", &n);memset(h, -1, sizeof h);//方便单链表查找操作while (n -- ){char op[2];int x;scanf("%s%d", op,&x);if(op[0] == 'I'){insert(x);}else{if(find(x)) printf("Yes\n");else printf("No\n");}}return 0;
}
开放寻址法:
#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;//寻找映射值//去寻找k的位置,如果k下有这个数返回的就是这个数的位置//如果k下没这个数,返回的是这个数应该存的位置while(h[k] != null && h[k] != x){k++;if(k==N) k = 0;}return k;
}int main()
{int n;scanf("%d", &n);//解释一下这里为啥是0x3f是因为memset是按字节去存储的,一个int是4个字节//每个字节是0x3f所以4个字节就是3f3f3f3fmemset(h,0x3f,sizeof h);while (n -- ){char op[2];int x;scanf("%s %d", op, &x);int k = find(x);//与拉链法区别是,寻址法都需要寻找k,直接合并成一个就可以if(op[0] == 'I'){h[k] = x;}else{if(h[k] == x) printf("Yes\n");else printf("No\n");}}return 0;
}
相关文章:
哈希表(c++)
1、介绍 哈希表,也称为散列表,是一种非常高效的数据结构。它通过将键(Key)映射到数组的特定位置来快速查找、插入和删除数据。这个映射过程由哈希函数(Hash Function)完成,该函数将键转化为一个…...
C#基础-标识符命名规则
目录 1、标识符定义 2、遵循规则 3、标识符的例子 4、MSDN中英文解释 英文...
Zabbix Web界面中文汉化
要想达到上图的效果,第一步先查看 /usr/share/zabbix/assets/fonts/ [rootservice yum.repos.d]# ll /usr/share/zabbix/assets/fonts/ 总用量 0 lrwxrwxrwx. 1 root root 33 3月 23 16:58 graphfont.ttf -> /etc/alternatives/zabbix-web-font 继续查看graph…...
esp32CAM环境搭建(arduino+MicroPython+thonny+固件)
arduino ide 开发工具 arduino版本:1.8.19 arduino ide 中文设置: file >> preferences >> arduino IDE 获取 ESP32 开发环境:打开 Arduino IDE ,找到 文件>首选项 ,将 ESP32 的配置链接填入附加开发板管理网…...
Spring Boot从入门到实战
课程介绍 本课程从SpringBoot的最基础的安装、配置开始到SpringBoot的日志管理、Web业务开发、数据存储、数据缓存,安全控制及相关企业级应用,全程案例贯穿,案例每一步的都会讲解实现思路,全程手敲代码实现。让你不仅能够掌Sprin…...
Spring Boot(七十一):整合RateLimiter实现接口限流
1 简介 RateLimiter 从概念上来讲,速率限制器会在可配置的速率下分配许可证。如果必要的话,每个acquire() 会阻塞当前线程直到许可证可用后获取该许可证。一旦获取到许可证,不需要再释放许可证。 RateLimiter使用的是一种叫令牌桶的流控算法,RateLimiter会按照一定的频率…...
通过jsDelivr实现Github的图床CDN加速
最近小伙伴们是否发现访问我的个人博客http://xiejava.ishareread.com/图片显示特别快了? 我的博客的图片是放在github上的,众所周知的原因,github访问不是很快,尤其是hexo博客用github做图床经常图片刷不出来。一直想换图床&…...
Kafka系列之:Connect 中的错误报告
Kafka系列之:Connect 中的错误报告 Kafka Connect 提供错误报告来处理各个处理阶段遇到的错误。默认情况下,转换期间或转换中遇到的任何错误都会导致连接器失败。每个连接器配置还可以通过跳过此类错误、选择性地将每个错误以及失败操作的详细信息和有问题的记录(具有各种详…...
MySQL面试题--开发(最全,涵盖SQL基础、架构、事务)
MySQL面试题--事务https://mp.csdn.net/mp_blog/creation/editor/136947072 MySQL面试题--MySQL内部技术架构https://blog.csdn.net/Timebro/article/details/136946046?spm1001.2014.3001.5501 MySQL面试题--最全面-索引https://blog.csdn.net/Timebro/article/details/136…...
【移动端】Flutter 获取Android AMap实例
背景 本文的背景,是因为我在开发高德地图时,需要自定义高德比例尺位置和样式;但结果查看了AMap Flutter插件和AMap SDK源码后,发现AMap无法添加自定义MyMethodCallHandler的实现类! why? 源码 在Flutte…...
什么是PLC物联网关?PLC物联网关有哪些功能?
在数字化浪潮的推动下,工业物联网(IIoT)正逐步成为推动制造业智能化转型的关键力量。而在这一变革中,PLC物联网关扮演着至关重要的角色。今天,就让我们一起走进PLC物联网关的世界,了解它的定义、功能&#…...
R-CNN笔记
目标检测之R-CNN论文精讲,RCNN_哔哩哔哩_bilibili 论文背景 在该论文提出之前,主流的目标检测思路是: 将一幅图片划分成很多个区域,单独提取出来 对于每个区域使用传统的特征提取方法提取 提取结束后可以使用以为特征向量表示 可以…...
uni-app从零开始快速入门
教程介绍 跨端框架uni-app作为新起之秀,在不到两年的时间内,迅速被广大开发者青睐和推崇,得益于它颠覆性的优势“快”,快到可以节省7套代码。本课程由uni-app开发者团队成员亲授,带领大家无障碍快速掌握完整的uni-app…...
Springboot集成jersey打包jar找不到class处理
环境 java17 springboot 3.x 如题,简单来说,jersey官方希望用户通过 register 的方式,将所有的资源类注册到jersey中,但是,一般开发中,可能定义了N个Resource类,一个一个的加入,太…...
基于springboot和vue的旅游资源网站的设计与实现
环境以及简介 基于vue, springboot旅游资源网站的设计与实现,Java项目,SpringBoot项目,含开发文档,源码,数据库以及ppt 环境配置: 框架:springboot JDK版本:JDK1.8 服务器…...
Python编程异步爬虫——协程的基本原理
Python编程之异步爬虫 协程的基本原理 要实现异步机制的爬虫,自然和协程脱不了关系。 案例引入 先看一个案例网站,地址为https://www.httpbin.org/delay/5,访问这个链接需要先等5秒钟才能得到结果,这是因为服务器强制等待5秒时…...
基于springboot+vue的旅游推荐系统
博主主页:猫头鹰源码 博主简介:Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战,欢迎高校老师\讲师\同行交流合作 主要内容:毕业设计(Javaweb项目|小程序|Pyt…...
Debezium日常分享系列之:Debezium2.5稳定版本之Monitoring
Debezium日常分享系列之:Debezium2.5稳定版本之Monitoring 一、Snapshot metrics二、Streaming metrics三、Schema history metrics Debezium系列之:安装jmx导出器监控debezium指标 除了 Zookeeper、Kafka 和 Kafka Connect 提供的对 JMX 指标的内置支持…...
GuLi商城-商品服务-API-三级分类-网关统一配置跨域
参考文档: https://tangzhi.blog.csdn.net/article/details/126754515 https://github.com/OYCodeSite/gulimall-learning/blob/master/docs/%E8%B0%B7%E7%B2%92%E5%95%86%E5%9F%8E%E2%80%94%E5%88%86%E5%B8%83%E5%BC%8F%E5%9F%BA%E7%A1%80.md 谷粒商城-day04-完…...
【ai技术】(4):在树莓派上,使用qwen0.5b大模型+chatgptweb,搭建本地大模型聊天环境,速度飞快,非常不错!
1,视频地址 https://www.bilibili.com/video/BV1VK421i7CZ/ 【ai技术】(4):在树莓派4上,使用ollama部署qwen0.5b大模型chatgptweb前端界面,搭建本地大模型聊天工具,速度飞快 2,下载…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
