算法通关村第5关【青铜】| Hash和队列的特征
1.Hash基础
(1)基础
哈希也称为散列,通过算法变成固定长度的输出值,存入对应的位置
例如这个算法为取模算法,index=number 模 7
存入1到15
(2)碰撞处理
当多个元素映射到同一位置上时就产生了碰撞
哈希碰撞处理是在使用哈希函数时,不同的键可能映射到相同的哈希值(哈希冲突)时的解决方法。哈希碰撞处理是为了确保不同的键可以在哈希表中正确存储和检索,从而维护哈希表的性能和正确性。
以下是几种常见的哈希碰撞处理方法:
链地址法(Chaining): 这是一种常见的方法,通过在哈希桶位置上维护一个链表(或其他数据结构),将发生冲突的键值对添加到链表中。在查找或删除操作时,遍历链表来找到对应的键值对。
开放定址法(Open Addressing): 在这种方法中,当发生冲突时,会顺序地在哈希表中的其他位置寻找空闲的位置来存储键值对。这包括线性探测、二次探测、双重哈希等策略。
再哈希法(Rehashing): 当发生冲突时,计算另一个哈希函数,然后将键值对存储在新的哈希桶位置上。这可以有效地减少冲突。
建立一个“桶”的链表: 这是一种类似于链地址法的方法,但不是在每个哈希桶位置上维护一个链表,而是在发生冲突的哈希桶位置上维护一个链表。
完全二叉树: 将键值对按照哈希值顺序存储在完全二叉树的节点上。这种方法在特定情况下可以提供较好的性能。
开放定址法
开放定址法的主要思想是,当发生哈希冲突时,不仅仅将数据存储在哈希桶中,而是根据某种算法找到一个不冲突的位置,将数据存储在那里。这就需要一个探测序列(probing sequence),它是一系列指示位置的步骤,用于寻找下一个可用的位置。
常见的开放定址法包括:
-
线性探测(Linear Probing): 在发生冲突时,按顺序检查下一个位置,直到找到一个空闲位置为止。
-
二次探测(Quadratic Probing): 在发生冲突时,按照某个步长的平方逐渐增加位置,直到找到一个空闲位置为止。
-
双重散列(Double Hashing): 在发生冲突时,使用第二个哈希函数计算一个步长,然后在哈希表中逐渐增加位置,直到找到一个空闲位置为止。
开放定址法的优点是它对于内存的利用更有效,因为数据存储在数组中,没有额外的指针。然而,它在负载因子高时可能会导致聚集现象(clustering),即一些位置上会有很多连续的元素,而其他位置则很少使用。这可能会降低性能。
链地址法
"链地址法"(Chaining)是一种哈希表解决哈希冲突的方法之一。在哈希表中,不同的键可能会映射到相同的哈希桶位置,这就产生了哈希冲突。链地址法通过在每个哈希桶位置上维护一个链表(或其他数据结构)来处理这种冲突。
具体来说,当发生哈希冲突时,链地址法将冲突的键值对添加到哈希桶位置对应的链表中。每个链表节点包含一个键值对。当需要插入、查找或删除一个键值对时,先计算哈希值找到对应的哈希桶位置,然后在该位置的链表中进行操作。
以下是链地址法的基本步骤:
-
插入: 计算键的哈希值,找到对应的哈希桶位置。如果该位置为空,则在该位置插入键值对。如果该位置已经有其他键值对存在(即发生冲突),则在链表中继续插入新的键值对。
-
查找: 计算键的哈希值,找到对应的哈希桶位置。然后遍历链表,查找包含该键的节点。
-
删除: 计算键的哈希值,找到对应的哈希桶位置。然后遍历链表,找到包含该键的节点,并进行删除操作。
链地址法的优点是它相对简单,可以有效地解决哈希冲突。然而,当哈希冲突较多时,链表可能会变得较长,导致操作的时间复杂度增加。为了保持哈希表的高效性能,需要根据数据分布情况来选择合适的哈希函数,并根据情况动态调整哈希桶的数量。另外,当链表过长时,可以考虑使用更高效的数据结构,如红黑树,来替代链表,以提高查找效率。
2.队列基础
FIFO先进先出的线性表
基于链表实现
尾插+头删
public class MyLinkQueue {static class Node {public int data;public Node next;public Node(int data) {this.data = data;}}private Node front;private Node rear;private int size;//无参构造初始化public MyLinkQueue() {this.front = null;this.rear = null;}public boolean isEmpty() {return front == null;}//尾插public void push(int data){Node node = new Node(data);if (isEmpty()){front = node;rear = node;}else{rear.next = node;rear = node;}size++;}//头删public int pop(){if (isEmpty()){throw new EmptyStackException();}int res = front.data;front = front.next;size--;return res;}public int size(){return size;}public void traverse(){Node t = front;while(t!=null){System.out.println(t.data);t = t.next;}}public static void main(String[] args) {MyLinkQueue queue = new MyLinkQueue();queue.push(10);queue.push(20);queue.push(30);System.out.println("Queue elements:");queue.traverse(); // Output: 10 20 30System.out.println("Dequeued element: " + queue.pop()); // Output: 10System.out.println("Queue size: " + queue.size()); // Output: 2queue.push(40);queue.push(50);System.out.println("Queue elements:");queue.traverse(); // Output: 20 30 40 50System.out.println("Queue size: " + queue.size()); // Output: 4}}
相关文章:
算法通关村第5关【青铜】| Hash和队列的特征
1.Hash基础 (1)基础 哈希也称为散列,通过算法变成固定长度的输出值,存入对应的位置 例如这个算法为取模算法,indexnumber 模 7 存入1到15 (2)碰撞处理 当多个元素映射到同一位置上时就产生…...
C++:函数
函数参数的传递机制 C的每个程序至少有一个函数,即主函数main(),函数也是类的方法的实现手段。C的函数包括两类:预定于函数和用户自定义函数。 函数的定义格式为: <返回值类型><函数名>(<参数列表>) <函…...
Linux网络编程:libevent事件通知库
文章目录: 一:libevent库 二:libevent框架 1.常规事件event 1.1 创建事件event(event_new) 1.2 添加事件到 event_base(event_add) 1.3 从event_base上摘下事件(event_del&a…...
java.lang.reflect.InvocationTargetException:null报未知异常
在项目上线过程中,突然出现大量异常信息,堆栈信息如下: java.lang.reflect.InvocationTargetException: null at jdk .internal.reflect.GeneratedMethodAccessor792 .invoke(Unknown Source) ~[?:?] at jdk.internal.reflect.DelegatingM…...
MySQL高级篇——MySQL架构篇1(Linux下MySQL8的安装与使用)
目录 0 安装前0.1 Linux系统及工具的准备0.2 查看是否安装过MySQL0.3 MySQL的卸载 1 MySQL8的Linux版安装1.1 MySQL的4大版本1.2 下载MySQL指定版本1.3 CentOS7下检查MySQL依赖1.4 CentOS7下MySQL安装过程 2 MySQL登录2.1 首次登录2.2 修改密码2.3 设置远程登录 3 MySQL 8 的密…...
解决 go mod tidy 加载模块超时
如果go mod tidy 加载模块超时 解决方法 修改GOPROXY: 查看go环境相关信息: go envgo env -w GOPROXYhttps://goproxy.cn...
金融市场中的机器学习;快手推出自研语言模型“快意”
🦉 AI新闻 🚀 OpenAI可能面临《纽约时报》的起诉,侵犯知识产权引发争议 摘要:OpenAI使用《纽约时报》的文章和图片来训练AI模型,违反了《纽约时报》的服务条款,可能面临巨大损失。此前,也有其…...
【面试刷题】——什么是深拷贝和浅拷贝?
深拷贝(Deep Copy)和浅拷贝(Shallow Copy)是在编程中用来描述对象拷贝的两个概念,特别是在涉及对象包含其他对象(如嵌套数据结构、指针等)的情况下。 浅拷贝(Shallow Copyÿ…...
物联网(IoT)安全挑战与解决方案: 分析物联网设备面临的安全威胁,以及如何设计和管理安全的IoT生态系统
第一章:引言 随着科技的飞速发展,物联网(IoT)作为连接世界的桥梁,已经成为现代社会不可或缺的一部分。然而,随着IoT设备数量的不断增加,其安全问题也日益显著。本文将深入探讨IoT领域面临的安全…...
Ubuntu 22.04.3 LTS 维护更新发布
近日消息,Canonical 今天发布了代号为 Jammy Jellyfish、长期支持的 Ubuntu 22.04 第 3 个维护版本更新,距离上个版本相隔 6 周时间。 Ubuntu 22.04.3 LTS 最大的亮点在于内核升级到 Linux Kernel 6.2,此外 Mesa 图形堆栈也升级到 23.0.4 版…...
平安健康,找到了医疗服务的价值密码
健康是人类的永恒需求,围绕医疗和健康服务衍生的产业,却苦于无法和用户建立足够紧密、长期的联系。由此,也不得不面临价值从何而来的问题。 作为医疗服务领域的代表性企业,平安健康医疗科技有限公司(股票简称“平安好…...
❤ vue 使用原生组件
❤ vue 使用原生组件 1、做一个input输入框验证开始 ① 想让我们的input输入框类型为时间,只需要为我们的输入框简单的加一个类型的type即可 <input type"date" id"birthday" name"birthday" placeholder"年/月/日"&…...
4.12 TCP 连接,一端断电和进程崩溃有什么区别?
目录 TCP keepalive TCP 的保活机制 主机崩溃 进程崩溃 有数据传输的场景 客户端主机宕机,又迅速重启 客户端主机宕机,一直没有重启 TCP连接服务器宕机和进程退出情况总结 TCP keepalive TCP 的保活机制 TCP 保活机制需要通过 socket 接口设置 S…...
十二、pikachu之URL重定向
文章目录 1、URL重定向概述2、实战3、URL跳转的几种方式:3.1 META标签内跳转3.2 javascript跳转3.3 header头跳转 1、URL重定向概述 不安全的url跳转问题可能发生在一切执行了url地址跳转的地方。如果后端采用了前端传进来的(可能是用户传参,或者之前预埋…...
贝叶斯公式中的动词 命名技巧
一项血液化验有95%的把我诊断某种疾病,但是,这项化验用于健康人也会有1%的“伪阳性”结果(即如果一个健康人接受这项化验,则化验结果乌镇此人患有该疾病的概率是0.01)。如果该疾病的患者事实上只占总人口的0.5%,若某人化验结果为阳…...
ctfshow-web13 文件上传
0x00 前言 CTF 加解密合集CTF Web合集 0x01 题目 0x02 Write Up 首先看到是一个上传页面,测试其他无果,遂进行目录遍历,发现upload.php.bak文件 可以看到这里的限制条件,大小,以及内容,这里可以使用.use…...
Python项目开发案例————学生信息管理系统(附源码)
一、学生信息管理系统 本文使用Python语言开发了一个学生信息管理系统,该系统可以帮助教师快速录入学生的信息,并且对学生的信息进行基本的增、删、改、查操作;还可以实时地将学生的信息保存到磁盘文件中。 1.1 需求分析 为了顺应互联网时代…...
2023-08-25力扣每日一题
链接: 1448. 统计二叉树中好节点的数目 题意: 判断根节点到每个节点X的过程中,如果没有值大于X,则该节点为好节点,求好节点数量 解: 由于求根节点到其他节点的路径,则使用dfs算法ÿ…...
Vue3中的计算属性和属性监听
compute计算属性 Vue3中可以通过 compute进行监听计算属性,他返回的是一个ref的对象,也就是说 通过compuye这种方式计算属性实际上是进行了ref的操作 import { computed } from vue const user reactive({firstName: A,lastName: B }) // 只有getter的…...
微信开发之一键修改群公告的技术实现
简要描述: 设置群公告 请求URL: http://域名地址/setChatRoomAnnouncement 请求方式: POST 请求头Headers: Content-Type:application/jsonAuthorization:login接口返回 参数: 参数名必…...
【git】工作场景中常用的git命令
工作场景中常用的git命令 1. 必备改名改邮箱拉代码下来并且创建新分支git commit回滚某个文件删除分支 工作场景中常用的git命令,记录下来方便调取 1. 必备 改名改邮箱 一般与他人合作,至少你提交的名字得被人熟知或者遵循规范,因此需要更改…...
Vue路由(详解)
目录 路由原理 路由到底有什么作用? 路由安装和使用(vue2) 路由跳转 跳转实例: 路由的传值和取值 传值实例: 查询参和路由参的区别: 嵌套路由 嵌套实例: 路由守卫 守卫实例࿱…...
打开软件提示msvcp140.dll丢失的解决方法,msvcp140主要丢失原因
今天,我将为大家介绍一种非常常见的问题——msvcp140.dll丢失。这个问题可能会导致许多应用程序无法正常运行,甚至崩溃。但是,请不要担心,我会为大家提供5种解决方法,帮助大家轻松解决问题。 首先,我们来看…...
关于路由器和DNS解析的一些新理解
其实我本人对于交换机和路由器这些网络硬件是比较感兴趣的,也在一点一点的学习相关知识,每次解决一个问题,就让我对一些事情有新的思考。。 今天前台同事,的机器突然上不了网,,和领导一起去看了一波&#…...
vscode 与 C++
序 具体流程的话,官方文档里都有的:C programming with Visual Studio Code 浏览器下载一个mingw64,解压,配置环境变量vscode里安装c相关的插件没了 第一步只看文字,可能有点抽象,相关视频: …...
水果flstudio好用吗?中文版FL21最新版本如何下载
FL Studio21版是一款功能强大的音乐制作软件,广泛应用于电子音乐、流行音乐、电影配乐等领域。它提供了丰富多样的音频合成和编辑工具,使音乐制作变得更加灵活多样。无论是初学者还是专业音乐制作人,都可以通过直观的界面和丰富的音频特效来实…...
PHP is_array()函数详解,PHP判断是否为数组
「作者主页」:士别三日wyx 「作者简介」:CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」:对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 is_array 一、基本使用二、空数组三、同时判断多个…...
面试题-React(三):什么是JSX?它与常规JavaScript有什么不同?
在React的世界中,JSX是一项引人注目的技术,它允许开发者在JavaScript中嵌套类似HTML的标签,用于描述UI组件的结构。本篇博客将通过丰富的代码示例,深入探索JSX语法,解析其在React中的用法和优势。 一、JSX基础语法 在…...
纯前端实现图片上传七牛云
首先安装下依赖: npm install qiniu-js crypto-js 然后封装一下 uploaderHelper.ts import * as qiniu from qiniu-js; // ts-ignore import CryptoJS from crypto-js// 请求接口上传图片 export function uploadFile(file: File) {const uptoken getToken(你的…...
win10+wsl2+Ubuntu20.2+Pycharm+WSL解释器
目的:创建一个ubuntu系统下的python解释器,作为win平台下的pycharm的解释器。 这样做的好处是可以直接在win系统里操作文件,相比于linux方便一点,而且也不用对wsl的子系统进行迁移。 一、安装前准备 1. 设置-Windows更新-window…...
EL与JSTL
目录 EL EL语法 EL运算符 JSTL JSTL标签分类 JSP脚本:代码结构混乱、脚本与HTML 混合易出错、代码不易维护。 EL表达式:优化程序代码,增加程序可读性。 EL EL语法 EL表达式 ${ EL 表达式 } EL操作符 操作符“ . ” 获取对象的属性&a…...
【Linux】动态库和静态库
动态库和静态库 软链接硬链接硬链接要注意 自定义实现一个静态库(.a)解决、使用方法静态库的内部加载过程 自定义实现一个动态库(.so)动态库加载过程 静态库和动态库的特点 软链接 命令:ln -s 源文件名 目标文件名 软链接是独立连接文件的,他…...
R语言:联合多指标的ROC曲线
# 加载数据和包rm(list=ls())library(pROC)library(ggplot2)setwd("C:/Users/syy/Desktop/MRI_lab/")data<- read.csv("test1.csv", header = T)data$Groups...
将一个树形结构的数据平铺成一个一维数组(vue3)
一、需求描述 由于自带组件库没有具体完善,无法实现像element-ui这种可以多选选择任意一级的选项,也就是说,选择父级的时候不会联动选择子级的全部 例如: 所以,才会出现【二、案例场景】类似的场景,可以用来多选 ,并可以实现单选父级而不关联子级,选择了将树状数据进…...
OSCS开源安全周报第 56 期:Apache Airflow Spark Provider 任意文件读取漏洞
本周安全态势综述 OSCS 社区共收录安全漏洞 3 个,公开漏洞值得关注的是 Apache NiFi 连接 URL 验证绕过漏洞(CVE-2023-40037)、PowerJob 未授权访问漏洞(CVE-2023-36106)、Apache Airflow Spark Provider 任意文件读取漏洞(CVE-2023-40272)。 针对 NPM 、PyPI 仓库…...
CleanMyMac2024永久版Mac清理工具
Mac电脑作为相对封闭的一个系统,它会中毒吗?如果有一天Mac电脑产生了疑似中毒或者遭到恶意不知名攻击的现象,那又应该如何从容应对呢?这些问题都是小编使用Mac系统一段时间后产生的疑惑,通过一番搜索研究,小…...
软考高级系统架构设计师(一)计算机硬件
【原文链接】软考高级系统架构设计师(一)计算机硬件 1.1 计算机硬件组成 1.1.1 计算机的基本硬件组成 运算器控制器存储器输入设备输出设备 1.1.2 中央处理单元(CPU) 中央处理单元(CPU)的组成 运算器…...
bat文件中自定义cmd命令;执行完退出命令提示符窗口
1. bat中启动cmd命令 start cmd /k " cmd中命令行里自定义的命令 " 2.编写规则 start cmd /k "命令1 & 命令2 & 命令3" (无论前面命令是否成功, 后面都会执行start cmd /k "命令1 && 命令2 && 命令3 " (仅…...
深度学习的经典算法的论文、解读和代码实现
文章目录 CNN网络的经典算法LeNet-5AlexNetVGGInceptionInception-v1(GoogLeNet)BN-Inception ResNetR-CNNR-CNNFast R-CNNFaster R-CNN YOLOYOLO v1YOLO v2YOLO v3YOLO v4 RNN的经典算法RNNGRULSTMEncoder-DecoderAttentionTransformer CNN网络的经典算法 LeNet-5 来源论文&…...
开源TTS+gtx1080+cuda11.7+conda+python3.9吊打百度TTS
一、简介 开源项目,文本提示的生成音频模型 https://github.com/suno-ai/bark Bark是由Suno创建的基于变换器的文本到音频模型。Bark可以生成极为逼真的多语种演讲以及其他音频 - 包括音乐、背景噪音和简单的声音效果。该模型还可以产生非言语沟通,如…...
【私有GPT】CHATGLM-6B部署教程
【私有GPT】CHATGLM-6B部署教程 CHATGLM-6B是什么? ChatGLM-6B是清华大学知识工程和数据挖掘小组(Knowledge Engineering Group (KEG) & Data Mining at Tsinghua University)发布的一个开源的对话机器人。根据官方介绍,这是…...
基于“R语言+遥感“水环境综合评价方法教程
详情点击链接:基于"R语言遥感"水环境综合评价方法教程 一:R语言 1.1 R语言特点(R语言) 1.2 安装R(R语言) 1.3 安装RStudio(R语言) (1)下载地址…...
To_Heart—题解——P6234 [eJOI2019] T形覆盖
link. 突然很想写这篇题解。虽然题目不算难。 考场只有30分是为什么呢?看来是我没有完全理解这道题目吧! 首先很明显的转换是,把 T 型覆盖看成十字形,再考虑最后减去某一块的贡献。 然后然后直接往原图上面放十字形!对于每一个…...
[软件工具]精灵标注助手目标检测数据集格式转VOC或者yolo
有时候我们拿到一个数据集发现是xml文件格式如下: <?xml version"1.0" ?> <doc><path>C:\Users\Administrator\Desktop\test\000000000074.jpg</path><outputs><object><item><name>dog</name>…...
Spring BeanName自动生成原理
先看代码演示 项目先定义一个User类 public class User {private String name;Overridepublic String toString() {return "User{" "name" name \ };}public String getName() {return name;}public void setName(String name) {this.name name;} }…...
论文阅读_图形图像_U-NET
name_en: U-Net: Convolutional Networks for Biomedical Image Segmentation name_ch: U-Net:用于生物医学图像分割的卷积网络 addr: http://link.springer.com/10.1007/978-3-319-24574-4_28 doi: 10.1007/978-3-319-24574-4_28 date_read: 2023-02-08 date_publi…...
基于热交换算法优化的BP神经网络(预测应用) - 附代码
基于热交换算法优化的BP神经网络(预测应用) - 附代码 文章目录 基于热交换算法优化的BP神经网络(预测应用) - 附代码1.数据介绍2.热交换优化BP神经网络2.1 BP神经网络参数设置2.2 热交换算法应用 4.测试结果:5.Matlab代…...
基于秃鹰算法优化的BP神经网络(预测应用) - 附代码
基于秃鹰算法优化的BP神经网络(预测应用) - 附代码 文章目录 基于秃鹰算法优化的BP神经网络(预测应用) - 附代码1.数据介绍2.秃鹰优化BP神经网络2.1 BP神经网络参数设置2.2 秃鹰算法应用 4.测试结果:5.Matlab代码 摘要…...
2.文章复现《热电联产系统在区域综合能源系统中的定容选址研究》(附matlab程序)
0.代码链接 1.简述 光热发电是大规模利用太阳能的新兴方式,其储热系 统能够调节光热电站的出力特性,进而缓解光热电站并网带来的火电机组调峰问题。合理配置光热电站储热容量,能够 有效降低火电机组调峰成本。该文提出一种光热电站储热容 量配…...
如何开启esxi主机的ssh远程连接
环境:esxi主机,说明:esxi主机默认ssh是不开启的,需要人工手动启动,也可以设置同esxi主机一起开机启动。 1、找到esxi主机,点击“配置”那里,再点击右边的属性,如图所示: …...