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

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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类:一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛,需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如,如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项,那么就查看 drivers/scsi/aha1542.c 文件,一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

用命令行的方式启动.netcore webapi

用命令行的方式启动.netcore web项目 进入指定的项目文件夹,比如我发布后的代码放在下面文件夹中 在此地址栏中输入“cmd”,打开命令提示符,进入到发布代码目录 命令行启动.netcore项目的命令为:  dotnet 项目启动文件.dll --urls="http://*:对外端口" --ip="本机ip" --port=项目内部端口 例: dotnet Imagine.M

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

深入理解RxJava:响应式编程的现代方式

在当今的软件开发世界中,异步编程和事件驱动的架构变得越来越重要。RxJava,作为响应式编程(Reactive Programming)的一个流行库,为Java和Android开发者提供了一种强大的方式来处理异步任务和事件流。本文将深入探讨RxJava的核心概念、优势以及如何在实际项目中应用它。 文章目录 💯 什么是RxJava?💯 响应式编程的优势💯 RxJava的核心概念

【即时通讯】轮询方式实现

技术栈 LayUI、jQuery实现前端效果。django4.2、django-ninja实现后端接口。 代码仓 - 后端 代码仓 - 前端 实现功能 首次访问页面并发送消息时需要设置昵称发送内容为空时要提示用户不能发送空消息前端定时获取消息,然后展示在页面上。 效果展示 首次发送需要设置昵称 发送消息与消息展示 提示用户不能发送空消息 后端接口 发送消息 DB = []@ro

Thymeleaf:生成静态文件及异常处理java.lang.NoClassDefFoundError: ognl/PropertyAccessor

我们需要引入包: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-thymeleaf</artifactId></dependency><dependency><groupId>org.springframework</groupId><artifactId>sp