哈希表之处理哈希冲突的闭散列方式

2024-04-17 10:18

本文主要是介绍哈希表之处理哈希冲突的闭散列方式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一. 哈希的概念

       首先,在顺序搜索以及二叉树搜索树中,元素存储的位置与元素的关键码之间没有对应的关系,因此查找一个元素时,必须要经过关键码的多次比较,搜索效率取决于搜索过程中元素的比较次数。

       那么,我们理想的搜索方法是:可以不经过任何的比较,一次直接从中找到要搜索的元素。如果构造一种存储结构,通过某种函数使得元素的存储位置与元素的关键码之间有一一映射的关系,那么在查找过程中通过该哈希函数可以直接找到该元素。当向该存储结构中:

(1)插入元素时:根据某种函数利用待插元素的关键码计算出该元素的存储位置并按照此位置进行存放。

(2)搜索元素时:根据某种函数利用待搜索元素的关键码计算出该元素应该存储的位置,在该位置取出元素与搜索元素比较,若相等时则表示搜索成功,否则搜索失败。

该方式即为哈希(散列)方法,哈希方法中使用的某种函数称为哈希(散列)函数,构造出来的存储结构称为哈希(散列)表。

举例:数据集合={1,3,5,6,8}    哈希函数:Hash(key)=key%10

此时,将数据集合中的元素存储在哈希表中如下:


将key值代入到哈希函数中,从而取出该key值的存储位置,此时,搜索指定元素如8时,直接利用哈希函数计算出存储位置下标,将其对应的值与要搜索的值8比较,相等时,表示找到了,否则没找到。通过上述操作可以看出,搜索的速度非常快。

但存在这样一个问题:当向数据集合中插入元素11时,将元素11存储在哪儿?依旧利用key=11计算出Hash(11)=11%10=1,那么原本应该存储在下标为1的位置,但是此时下标为1的位置已经有存储的元素1,对于出现的这种现象我们称为哈希冲突!

哈希冲突:对于两个数据元素的关键码Ki和Kj(i!=j),即Ki!=Kj,有Hash(Ki)==Hash(Kj),即不同的关键码通过相同的哈希函数计算得到相同的哈希地址,这种现象称为哈希冲突或哈希碰撞。把具有不同关键码而计算出相同的哈希地址的数据元素称为同义词。那么发生这种哈希冲突应该如何处理呢?

处理哈希冲突常见有两种解决方式:闭散列和开散列。

二.闭散列处理哈希冲突

闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被装满,说明哈希表中必然还有空位置,那么就可以把key存放在表中的“下一个”空位中。那如何寻找下一个空位置呢?

我们介绍以线性探测的方式寻找下一个空位置。下面举例介绍如何线性探测寻找下一个空位置去处理哈希冲突:

这篇关于哈希表之处理哈希冲突的闭散列方式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/911519

相关文章

RabbitMQ消息总线方式刷新配置服务全过程

《RabbitMQ消息总线方式刷新配置服务全过程》SpringCloudBus通过消息总线与MQ实现微服务配置统一刷新,结合GitWebhooks自动触发更新,避免手动重启,提升效率与可靠性,适用于配... 目录前言介绍环境准备代码示例测试验证总结前言介绍在微服务架构中,为了更方便的向微服务实例广播消息,

Java堆转储文件之1.6G大文件处理完整指南

《Java堆转储文件之1.6G大文件处理完整指南》堆转储文件是优化、分析内存消耗的重要工具,:本文主要介绍Java堆转储文件之1.6G大文件处理的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言文件为什么这么大?如何处理这个文件?分析文件内容(推荐)删除文件(如果不需要)查看错误来源如何避

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案:复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2:删除后修改唯一字

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

Java docx4j高效处理Word文档的实战指南

《Javadocx4j高效处理Word文档的实战指南》对于需要在Java应用程序中生成、修改或处理Word文档的开发者来说,docx4j是一个强大而专业的选择,下面我们就来看看docx4j的具体使用... 目录引言一、环境准备与基础配置1.1 Maven依赖配置1.2 初始化测试类二、增强版文档操作示例2.

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

Linux线程之线程的创建、属性、回收、退出、取消方式

《Linux线程之线程的创建、属性、回收、退出、取消方式》文章总结了线程管理核心知识:线程号唯一、创建方式、属性设置(如分离状态与栈大小)、回收机制(join/detach)、退出方法(返回/pthr... 目录1. 线程号2. 线程的创建3. 线程属性4. 线程的回收5. 线程的退出6. 线程的取消7.

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

golang程序打包成脚本部署到Linux系统方式

《golang程序打包成脚本部署到Linux系统方式》Golang程序通过本地编译(设置GOOS为linux生成无后缀二进制文件),上传至Linux服务器后赋权执行,使用nohup命令实现后台运行,完... 目录本地编译golang程序上传Golang二进制文件到linux服务器总结本地编译Golang程序