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

哈希表(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、介绍 哈希表&#xff0c;也称为散列表&#xff0c;是一种非常高效的数据结构。它通过将键&#xff08;Key&#xff09;映射到数组的特定位置来快速查找、插入和删除数据。这个映射过程由哈希函数&#xff08;Hash Function&#xff09;完成&#xff0c;该函数将键转化为一个…...

C#基础-标识符命名规则

目录 1、标识符定义 2、遵循规则 3、标识符的例子 4、MSDN中英文解释 英文...

Zabbix Web界面中文汉化

要想达到上图的效果&#xff0c;第一步先查看 /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版本&#xff1a;1.8.19 arduino ide 中文设置&#xff1a;​ file >> preferences >> ​ arduino IDE 获取 ESP32 开发环境&#xff1a;打开 Arduino IDE &#xff0c;找到 文件>首选项 ,将 ESP32 的配置链接填入附加开发板管理网…...

Spring Boot从入门到实战

课程介绍 本课程从SpringBoot的最基础的安装、配置开始到SpringBoot的日志管理、Web业务开发、数据存储、数据缓存&#xff0c;安全控制及相关企业级应用&#xff0c;全程案例贯穿&#xff0c;案例每一步的都会讲解实现思路&#xff0c;全程手敲代码实现。让你不仅能够掌Sprin…...

Spring Boot(七十一):整合RateLimiter实现接口限流

1 简介 RateLimiter 从概念上来讲,速率限制器会在可配置的速率下分配许可证。如果必要的话,每个acquire() 会阻塞当前线程直到许可证可用后获取该许可证。一旦获取到许可证,不需要再释放许可证。 RateLimiter使用的是一种叫令牌桶的流控算法,RateLimiter会按照一定的频率…...

通过jsDelivr实现Github的图床CDN加速

最近小伙伴们是否发现访问我的个人博客http://xiejava.ishareread.com/图片显示特别快了&#xff1f; 我的博客的图片是放在github上的&#xff0c;众所周知的原因&#xff0c;github访问不是很快&#xff0c;尤其是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实例

背景 本文的背景&#xff0c;是因为我在开发高德地图时&#xff0c;需要自定义高德比例尺位置和样式&#xff1b;但结果查看了AMap Flutter插件和AMap SDK源码后&#xff0c;发现AMap无法添加自定义MyMethodCallHandler的实现类&#xff01; why&#xff1f; 源码 在Flutte…...

什么是PLC物联网关?PLC物联网关有哪些功能?

在数字化浪潮的推动下&#xff0c;工业物联网&#xff08;IIoT&#xff09;正逐步成为推动制造业智能化转型的关键力量。而在这一变革中&#xff0c;PLC物联网关扮演着至关重要的角色。今天&#xff0c;就让我们一起走进PLC物联网关的世界&#xff0c;了解它的定义、功能&#…...

R-CNN笔记

目标检测之R-CNN论文精讲&#xff0c;RCNN_哔哩哔哩_bilibili 论文背景 在该论文提出之前&#xff0c;主流的目标检测思路是&#xff1a; 将一幅图片划分成很多个区域&#xff0c;单独提取出来 对于每个区域使用传统的特征提取方法提取 提取结束后可以使用以为特征向量表示 可以…...

uni-app从零开始快速入门

教程介绍 跨端框架uni-app作为新起之秀&#xff0c;在不到两年的时间内&#xff0c;迅速被广大开发者青睐和推崇&#xff0c;得益于它颠覆性的优势“快”&#xff0c;快到可以节省7套代码。本课程由uni-app开发者团队成员亲授&#xff0c;带领大家无障碍快速掌握完整的uni-app…...

Springboot集成jersey打包jar找不到class处理

环境 java17 springboot 3.x 如题&#xff0c;简单来说&#xff0c;jersey官方希望用户通过 register 的方式&#xff0c;将所有的资源类注册到jersey中&#xff0c;但是&#xff0c;一般开发中&#xff0c;可能定义了N个Resource类&#xff0c;一个一个的加入&#xff0c;太…...

基于springboot和vue的旅游资源网站的设计与实现

环境以及简介 基于vue, springboot旅游资源网站的设计与实现&#xff0c;Java项目&#xff0c;SpringBoot项目&#xff0c;含开发文档&#xff0c;源码&#xff0c;数据库以及ppt 环境配置&#xff1a; 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xf…...

Python编程异步爬虫——协程的基本原理

Python编程之异步爬虫 协程的基本原理 要实现异步机制的爬虫&#xff0c;自然和协程脱不了关系。 案例引入 先看一个案例网站&#xff0c;地址为https://www.httpbin.org/delay/5&#xff0c;访问这个链接需要先等5秒钟才能得到结果&#xff0c;这是因为服务器强制等待5秒时…...

基于springboot+vue的旅游推荐系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…...

Debezium日常分享系列之:Debezium2.5稳定版本之Monitoring

Debezium日常分享系列之&#xff1a;Debezium2.5稳定版本之Monitoring 一、Snapshot metrics二、Streaming metrics三、Schema history metrics Debezium系列之&#xff1a;安装jmx导出器监控debezium指标 除了 Zookeeper、Kafka 和 Kafka Connect 提供的对 JMX 指标的内置支持…...

GuLi商城-商品服务-API-三级分类-网关统一配置跨域

参考文档&#xff1a; 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&#xff0c;视频地址 https://www.bilibili.com/video/BV1VK421i7CZ/ 【ai技术】&#xff08;4&#xff09;&#xff1a;在树莓派4上&#xff0c;使用ollama部署qwen0.5b大模型chatgptweb前端界面&#xff0c;搭建本地大模型聊天工具&#xff0c;速度飞快 2&#xff0c;下载…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...