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

数据结构——哈希

哈希表 是一种使用哈希函数组织数据的数据结构,它支持快速插入和搜索。

哈希表(又称散列表)的原理为:借助 哈希函数,将键映射到存储桶地址。更确切地说,
1.首先开辟一定长度的,具有连续物理地址的桶数组;
2.当我们插入一个新的键时,哈希函数将决定该键应该分配到哪个桶中,并将该键存储在相应的桶中;
3.当我们想要搜索一个键时,哈希表将使用哈希函数来找到对应的桶,并在该桶中进行搜索。

负载因子 又叫装填因子,是哈希表的一个重要参数,它反映了哈希表的装满程度。
实际利用桶的个数 与 桶的总数 的比值,称为负载因子。

哈希函数

哈希函数是哈希表中最重要的组件,用于将键映射到特定的桶。我们使用 y = x % 5 作为散列函数,其中 x 是键值,y 是映射之后对应的桶的索引。

冲突解决

一般情况下,哈希函数会起到压缩键的地址空间的作用,设键的地址空间为 S,桶的地址空间为 T,则有 S≫T。
因此,经过映射之后,不同的数据会不可避免地分配到同一个桶中,这时便产生了冲突。

线性试探法

线性试探法属于开放定址法的一种,所谓线性试探法,就是当插入键 key 时,如果发现桶单元 bucket[hash(key)] 已经被占用,则向下线性寻找,直到找到可以使用的空桶。具体说来,经过第 i 次试探之后,桶单元应为:bucket[(hash(key)+i) mod M], i=1,2,3…

链地址法

解决冲突的另一种办法是将桶内产生冲突的键串联成一个链表。

再哈希法

再哈希法比较典型的应用是双重哈希法,即发生冲突时,通过使用另一个哈希函数来避免冲突。
然而,双重哈希法同样存在一些问题:
1.与线性试探法相比,双重哈希法会消耗较多的时间。
2.在双重哈希法中,删除会使问题变复杂,如果逻辑删除数量太多,则应重新构造哈希表。

公共溢出区法

顾名思义,公共溢出区法就是建立另一个哈希表 dict_overflow 作为公共溢出区,当发成冲突时则将该键保存在该哈希表中。

简单哈希集合

#define MAX_LEN 100000          // 初始化桶的数量class MyHashSet {
private:vector<int> set[MAX_LEN];   // 使用数组实现哈希集合/** 返回对应的桶的索引 */int getIndex(int key) {return key % MAX_LEN;}/** 在特定的桶中搜索键,如果该键不存在则返回 -1 */int getPos(int key, int index) {// 每个桶中包含一个列表,遍历所有桶中的元素来寻找特定的键for (int i = 0; i < set[index].size(); ++i) {if (set[index][i] == key) {return i;}}return -1;}
public:MyHashSet() {}void add(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {// 如果键不存在,则添加set[index].push_back(key);}}void remove(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos >= 0) {// 如果键存在,则删除set[index].erase(set[index].begin() + pos);}}bool contains(int key) {int index = getIndex(key);int pos = getPos(key, index);return pos >= 0;}
};

简单哈希映射

#define MAX_LEN 100000            // 初始化桶的数量class MyHashMap {
private:vector<pair<int, int>> map[MAX_LEN];       // 使用数组实现哈希集合/** 返回指定桶的索引 */int getIndex(int key) {return key % MAX_LEN;}/** 在桶中搜索键,如果不存在则返回 -1 */int getPos(int key, int index) {// 每个桶包含一个数组,遍历桶中的所有元素来查找指定的 keyfor (int i = 0; i < map[index].size(); ++i) {if (map[index][i].first == key) {return i;}}return -1;}public:MyHashMap() {}/** value 始终为正 */void put(int key, int value) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {map[index].push_back(make_pair(key, value));} else {map[index][pos].second = value;}}/** 如果存在映射关系,则返回 value,否则返回 -1 */int get(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {return -1;} else {return map[index][pos].second;}}/** 如果存在 key 的映射,则删除该映射关系 */void remove(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos >= 0) {map[index].erase(map[index].begin() + pos);}}
};

相关文章:

数据结构——哈希

哈希表 是一种使用哈希函数组织数据的数据结构&#xff0c;它支持快速插入和搜索。 哈希表&#xff08;又称散列表&#xff09;的原理为&#xff1a;借助 哈希函数&#xff0c;将键映射到存储桶地址。更确切地说&#xff0c; 1.首先开辟一定长度的&#xff0c;具有连续物理地址…...

效果好的it监控系统特点

一个好的IT监控系统应该具备以下特点&#xff1a;  全面性&#xff1a;IT监控系统应该能够监视和管理IT系统的所有方面&#xff0c;包括网络、服务器、应用程序和数据库等。这样可以确保系统的各个方面都得到充分的监视和管理。  可靠性&#xff1a;IT监控系统需要保持高可…...

leetcode1288. 删除被覆盖区间(java)

删除被覆盖区间 题目描述贪心法代码演示 题目描述 难度 - 中等 leetcode1288. 删除被覆盖区间 给你一个区间列表&#xff0c;请你删除列表中被其他区间所覆盖的区间。 只有当 c < a 且 b < d 时&#xff0c;我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作…...

Python 虚拟环境相关命令

一 激活 在 cd venv/scripts 进入虚拟环境 执行命令 activate 1、创建虚拟环境 $ python -m venv 2、激活虚拟环境 $ source <venv>/bin/activate 3、关闭虚拟环境 $ deactivate...

使用U盘同步WSL2中的git项目

1、将U盘挂载到WSL2中 假设U盘在windows资源管理器中被识别为F盘&#xff0c;需要在WSL2中创建一个目录挂载U盘 sudo mkdir /mnt/f sudo mount -t drvfs F: /mnt/f后续所有的操作都完成后&#xff0c;拔掉U盘前&#xff0c;可以使用下面的命令从WSL2中安全的移除U盘 umount …...

Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装

Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装 目录 Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装 一、简单介绍 二、ControlNet 插件下载安装 三、ControlNet 插件模型下载安装 四、ControlNet 插件其他的下载安装方式 五、Co…...

CMAK学习

VS中的cmake_cmake vs_今天也要debug的博客-CSDN博客 利用vs2017 CMake开发跨平台C项目实战_cmake vs2017_神气爱哥的博客-CSDN博客 【【入门】在VS中使用CMake管理若干程序】https://www.bilibili.com/video/BV1iz4y117rZ?vd_source0aeb782d0b9c2e6b0e0cdea3e2121eba...

Python 推导式

Python 推导式 Python 推导式是一种独特的数据处理方式&#xff0c;可以从一个数据序列构建另一个新的数据序列的结构体。 Python 支持各种数据结构的推导式&#xff1a; 列表(list)推导式字典(dict)推导式集合(set)推导式元组(tuple)推导式 列表推导式 列表推导式格式为&…...

es6的新特性有哪些

ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript的一个重要版本&#xff0c;引入了许多新的语法和功能。以下是ES6的一些主要特性&#xff1a; 块级作用域&#xff08;Block Scope&#xff09;&#xff1a;引入了let和const关键字&#xff0c;可以在块级作用域中声明变…...

logstash 消费kafka数据,转发到tcp端口

1&#xff0c; logstash 配置文件 [roothost1: ] cat /opt/logstash/kafka-to-tcp.yml input { kafka {bootstrap_servers > "192.168.0.11:9092" #这里可以是kafka集群&#xff0c;如"192.168.149.101:9092,192.168.149.102:9092"consumer_threads &…...

航天智信:严控航天系统研发安全,助力建设“航天强国”

航天智信作为中国航天科工三院在信息装备领域“做大做强”的重要布局&#xff0c;主要从事系统运用与联合体系研究&#xff0c;复杂信息系统的顶层设计、总体论证及研制生产&#xff0c;提供体系级、系统级信息系统整体解决方案&#xff0c;以及信息安全系统的设计研发与集成验…...

阿里云2核4G服务器5M带宽五年租用价格表

阿里云2核4G服务器5M带宽可以选择轻量应用服务器或云服务器ECS&#xff0c;轻量2核4G4M带宽服务器297元一年&#xff0c;2核4G云服务器ECS可以选择计算型c7、c6或通用算力型u1实例等&#xff0c;买5年可以享受3折优惠&#xff0c;阿腾云分享阿里云服务器2核4G5M带宽五年费用表&…...

基于Laravel通用型内容建站企业官网系统源码 可免费商用

是一个基于 Laravel 企业内容建站系统。模块市场拥有丰富的功能应用&#xff0c;支持后台一键快速安装&#xff0c;让开发者能快的实现业务功能开发。 系统完全开源&#xff0c;免费且不限制商业使用 2023年08月23日增加了以下12个特性&#xff1a; [新功能] 手机端Banner支持…...

风力发电常见问题

目录 叶片失速 风力发电机失速状态是指风力发电机的叶片在高风速下无法继续提供升力&#xff0c;导致叶片停止旋转或减速旋转&#xff0c;从而降低了风力发电机的效率和发电能力。判断风力发电机是否处于失速状态通常可以通过以下方法&#xff1a; 监测风速&#xff1a;最简单…...

uniapp 解决跨域的问题

uniapp 解决跨域的问题 我真的是个 沙雕 找对了解决办法 写错了地方 "h5" : {"devServer" : {"disableHostCheck" : true,"https": false,"proxy" : {"/app" : {"target" : "https://192.16…...

Springboot GET和POST请求的常用参数获取方式

GET 使用RequestParam注解 可以在控制器方法的参数上使用RequestParam注解来获取请求中的参数值。例如&#xff1a; GetMapping("/example") public String example(RequestParam String param) {// 使用param参数的值return "Value of param: " param…...

项目(智慧教室)第四部分,页面交互功能

一。页面构思 1.标题栏 大标题&#xff1a;智慧教室管理系统 小标题&#xff1a;灯光&#xff0c;报警&#xff0c;风扇&#xff0c;温度&#xff0c;湿度&#xff0c;光照 2.样式设计 背景设置。字体设置&#xff08;字体大小&#xff0c;格式&#xff0c;颜色&#xff09; 3.…...

基于Matlab分析的电力系统可视化研究

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

MySQL为什么不推荐使用in

有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top 首发博客地址 系列文章地址 当使用IN语句时&#xff0c;MySQL可能会遇到以下问题&#xff1a; 索引问题&#xff1a;MySQL使用索引来加速查询&#x…...

python中的复数

在Python中&#xff0c;复数&#xff08;Complex Numbers&#xff09;是一种数值类型&#xff0c;用于表示具有实部和虚部的数值。复数由一个实部和一个虚部组成&#xff0c;形式为 a bj&#xff0c;其中 a 表示实部&#xff0c;b 表示虚部&#xff0c;而 j 表示虚数单位&…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...