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

07-7.5.3 处理冲突的方法

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com


喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏

1. 拉链法

1.1 插入

如何插入?

  1. 结合散列函数计算新元素的散列地址
  2. 将新元素插入散列地址对应的链表(头插法、尾插法)

1.2 查找

如何查找?

  1. 先计算地址
  2. 再对链表中的元素进行对比

1.3 删除

如何删除?

  1. 先查找元素
  2. 如果能找到,就可以删除

2. 开放定址法

2.1 基本原理

根据散列函数 H ( k e y ) H(key) H(key),求得初始散列地址。若发生冲突,如何找到“另一个空闲位置?
H i = ( H ( k e y ) + d i ) % m H_i=(H(key)+d_i)\%m Hi=(H(key)+di)%m
H i H_i Hi —— 发生第 i 次冲突时的散列地址
H ( k e y ) H(key) H(key) —— 初始散列地址
d i d_i di —— 偏移量
m m m —— 散列表表长

四种常用方法构造探测序列 d i 。注: 0 ≤ i ≤ m − 1 d_i。注:0 \leq i \leq m-1 di。注:0im1

  1. 线性探测法 —— d i = 0 , 1 , 2 , 3 , . . . , m − 1 d_i=0,1,2,3,...,m-1 di=0,1,2,3,...,m1
  2. 平方探测法 —— d i = 0 2 , 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , k 2 , − k 2 。其中 k ≤ m / 2 d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2。其中k\leq m/2 di=02,12,12,22,22,...,k2,k2。其中km/2
  3. 双散列法 —— d i = i ∗ h a s h 2 ( k e y ) 。其中 h a s h 2 ( k e y ) 是另一散列函数 d_i = i * hash_2{(key)}。其中hash_2(key)是另一散列函数 di=ihash2(key)。其中hash2(key)是另一散列函数
  4. 伪随机序列法 —— d i d_i di是一个伪随机序列,如 d i = 1 , 1 , 4 , 5 , 1 , 4 , . . . d_i=1,1,4,5,1,4,... di=1,1,4,5,1,4,...

特别注意:关于删除操作

采用开放定址法时,删除元素不能简单地将被删除元素的空间置为空,否则将阶段在它之后的探测路径,可以做一个“已删除”标记,进行逻辑删除

相关文章:

07-7.5.3 处理冲突的方法

👋 Hi, I’m Beast Cheng 👀 I’m interested in photography, hiking, landscape… 🌱 I’m currently learning python, javascript, kotlin… 📫 How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以…...

几何距离与函数距离:解锁数据空间中的奥秘

几何距离:直观的空间度量 几何距离,顾名思义,是我们在几何学中熟悉的距离概念,如欧几里得距离、曼哈顿距离和切比雪夫距离等。这些距离度量直接反映了数据点在多维空间中的位置关系。 欧几里得距离:最为人熟知的几何距…...

LabVIEW的Actor Framework (AF) 结构介绍

LabVIEW的Actor Framework (AF) 是一种高级架构,用于开发并发、可扩展和模块化的应用程序。通过面向对象编程(OOP)和消息传递机制,AF结构实现了高效的任务管理和数据处理。其主要特点包括并发执行、动态可扩展性和强大的错误处理能…...

gitlab 搭建使用

1. 硬件要求 ##CPU 4 核心500用户 8 核心1000用户 ##内存 4 G内存500用户 8 G内存1000用户 2. 下载 链接 3. 安装依赖 yum -y install curl openssh-server postfix wget 4. 安装gitlab组件 yum -y localinstall gitlab-ce-15.9.3-ce.0.el7.x86_64.rpm 5. 修改配置文…...

探索JT808协议在车辆远程视频监控系统中的应用

一、部标JT808协议概述 随着物联网技术的迅猛发展,智能交通系统(ITS)已成为现代交通领域的重要组成部分。其中,车辆远程监控与管理技术作为ITS的核心技术之一,对于提升交通管理效率、保障道路安全具有重要意义。 JT8…...

视频使用操作说明书-T80005系列视频编码器如何对接海康NVR硬盘录像机,包括T80005系列高清HDMI编码器、4K超高清HDMI编码器

视频使用操作说明书-T80005系列视频编码器如何对接海康NVR硬盘录像机,包括T80005系列高清HDMI编码器、4K超高清HDMI编码器。 视频使用操作说明书-T80005系列视频编码器如何对接海康NVR硬盘录像机,包括T80005系列高清HDMI编码器、4K超高清HDMI编码器 同三…...

keep-alive缓存组件

keep-alive缓存组件是Vue.js中的一个特殊组件&#xff0c;主要用于缓存内部组件的数据状态&#xff0c;以提高应用的性能和用户体验。以下是关于keep-alive缓存组件的详细解析&#xff1a; 一、作用 缓存组件状态&#xff1a;当组件在<keep-alive>内部切换时&#xff0…...

Linux上如何安装ffmpeg视频处理软件

在Linux上安装ffmpeg需要以下步骤&#xff1a; 更新系统 在开始安装之前&#xff0c;首先需要更新系统以获取最新的软件包列表和版本。在终端中执行以下命令&#xff1a; sudo apt update sudo apt upgrade安装依赖库 ffmpeg依赖于一些库和工具&#xff0c;需要先安装它们。在…...

element如何实现自定义表头?

有时候我们需要实现自定义表头,例如表头里加按钮啥的,这时候就需要用到自定义表头,但是官方对自定义表头的使用写的还是比较简单,今天就来详细说说 在需要使用自定义表头的表头上使用:render-header来启用自定义表头: <el-table-column :render-header="button&…...

OTP防重放攻击

OTP本意是一次性口令&#xff0c;比如邮箱验证码&#xff0c;短信验证码&#xff0c;或者根据totp或者hotp生成的默认30秒一变的6位数字。 不过开发者要注意&#xff0c;必须要在验证成功后失效那个验证码&#xff0c;不然就会导致重放攻击。 对于邮箱验证码&#xff0c;服务器…...

Oracle数据库加密与安全

Wallet简介&#xff1a; Oracle Wallet(即内部加密技术TDE( Transparent DataEncryption&#xff09; TDE是 Oracle10gR2中推出的一个新功能,使用时要保证Oracle版本是在10gR2或者以上 Wallet配置&#xff1a; 1.创建一个新目录&#xff0c;并指定为Wallet目录 /home/oracle…...

【YOLO格式的数据标签,目标检测】

标签为 YOLO 格式&#xff0c;每幅图像一个 *.txt 文件&#xff08;如果图像中没有对象&#xff0c;则不需要 *.txt 文件&#xff09;。*.txt 文件规格如下: 每个对象一行 每一行都是 class x_center y_center width height 格式。 边框坐标必须是 归一化的 xywh 格式&#x…...

Memcached内存碎片清理术:优化缓存性能的策略

标题&#xff1a;Memcached内存碎片清理术&#xff1a;优化缓存性能的策略 内存碎片是Memcached在长期运行过程中常见的问题&#xff0c;它会降低缓存效率并影响性能。作为高效的分布式内存缓存系统&#xff0c;Memcached提供了多种内存碎片整理策略。本文将详细介绍这些策略&…...

禁止使用存储过程

优质博文&#xff1a;IT-BLOG-CN 灵感来源 什么是存储过程 存储过程Stored Procedure是指为了完成特定功能的SQL语句集&#xff0c;经编译后存储在数据库中&#xff0c;用户可通过指定存储过程的名字并给定参数&#xff08;如果该存储过程带有参数&#xff09;来调用执行。 …...

Flink异常:org/apache/hadoop/hive/ql/parse/SemanticException

在flink项目中跑 上面这段代码出现如下这个异常&#xff0c; java.lang.NoClassDefFoundError: org/apache/thrift/TException 加上下面这个依赖后不报错 <dependency> <groupId>org.apache.thrift</groupId> <artifactId>libthrift</artifactId…...

Java:构造函数与对象

第一章&#xff1a;构造函数揭秘 —— 创造者的第一次触碰 构造函数&#xff0c;顾名思义&#xff0c;是用于创建和初始化对象的特殊方法。它没有返回类型&#xff0c;名字与类名一致。构造函数是对象诞生的第一步&#xff0c;也是最至关重要的一步。让我们通过一个生动的例子…...

Leetcode(经典题)day1

删除有序数组中的重复项|| 80. 删除有序数组中的重复项 II - 力扣&#xff08;LeetCode&#xff09; 和之前的删除有序数组中的重复项|相似&#xff0c;这里是要求最多出现两次&#xff0c;所以多加一个变量来记录出现次数即可&#xff0c;整体上还是使用双指针&#xff0c;…...

k8s record 20240710 监控

不是adaptor 是opetator 案例 监控有了&#xff0c;日志搜集呢&#xff1f; 一、kubelet 的小弟 kubelet — 负责维护容器的生命周期&#xff0c;节点和集群其他部分通信 cAdvisor 集成在 Kubernetes 的 kubelet 中&#xff0c;能够自动发现和监控集群中所有的容器。dockers…...

pdf工具

iLovePDF | 为PDF爱好者提供的PDF文件在线处理工具 https://www.ilovepdf.com/zh-cn 图片 pdf 合并成一个pdf也可以拆分...

百度文心4.0 Turbo开放,领跑国内AI大模型赛道!

百度文心4.0 Turbo开放&#xff0c;领跑国内AI大模型赛道&#xff01; 前言 文心一言大模型 就在7月5日&#xff0c;在2024世界人工智能大会 (WAIC) 上&#xff0c;百度副总裁谢广军宣布文心大模型4.0 Turbo正式向企业客户全面开放&#xff01;这一举动直接引发了业界的关注。那…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...