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

哈希表简单介绍

概念

顺序结构以及平衡树中,元素关键字与他们存储的位置并没有直接的映射关系,从而会影响查找关键字的效率,顺序结构中查找关键字的时间复杂度为O(N),平衡树查找关键字的时间复杂度为O(log2^N)。

最理想的搜索方法——只搜索一次就能找到关键字。

如果有一种数据结构,能够使得关键字根据某种映射规则,将关键字和它的存储位置一一映射起来,那么在查找时通过映射规则就能够很快将关键字查找出来。

在这个数据结构中

插入元素:

根据某种特定的映射规则,找到关键字在存储结构中的位置,然后插入。

搜索元素:

根据某种特定映射规则,将求得的函数值作为元素的存储位置,然后与结构中此位置的元素比较,若关键字相等,则搜索成功。

该方式就被称为哈希或者散列,使用的映射函数就为哈希函数或者散列函数,构造出来的存储结构就为哈希表或者散列表。

比如:数据集合{1,7,6,4,5,9}

如果哈希函数设置为hash(key)=key%10,则数据在存储结构内会呈现以下关系

该方法查找每一个数只需要进行一次比较,效率很高,但是这种存储方式在实际使用的时候会导致很多的空间浪费,有些空间为空,被没有被有效利用起来,所以实际使用时模数的取值一般为不超过存储结构容量的最大质数。

哈希冲突

哈希冲突的原因是由于,当有一组数据需要通过相同的映射规则存储到到一个存储结构时,此时就有可能两个数得到的hash(key)的值相同,但是又不可能将两个数字同时存储在一个空间里面,这时就造成了哈希冲突,或者叫哈希碰撞。

此时把具有相同哈希地址的不同关键字记为“同义词”。

发生哈希表该如何处理呢?

处理方法

拉链法

比如:数据集合{1,7,6,4,5,9,12,25,36}

加入存储结构容量为7,则哈希函数为hash(key)=key%7。

这种情况就将哈希地址相同的数据元素依次链接到之前元素的后面。

成功查找的平均查找长度 ASL成功=(6*1+2*2)/9=1.11

ASL失败=9/7=1.286。

装填因子=表中记录数/散列表长度。

装填因子越大表示表装得越满。

直接定址法

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B

由于这是一个一次函数,所以对于每一个不相同的元素对应的值就不相同,所以哈希地址不会存在冲突。

优点:简单、均匀

缺点:需要事先知道关键字的分布情况
使用场景:适合查找比较小且连续的情况

开放定址法

线性探测法

意思就是通过哈希函数处理后得到的关键字哈希地址如果存在冲突,那么就依次往后面去找空位将这个数放进去。

相关文章:

哈希表简单介绍

概念 在顺序结构以及平衡树中,元素关键字与他们存储的位置并没有直接的映射关系,从而会影响查找关键字的效率,顺序结构中查找关键字的时间复杂度为O(N),平衡树查找关键字的时间复杂度为O(log2^…...

kafka 之 本地部署单机版

安装JDK 查看你选择的版本需要安装哪一个版本的jdk 网址 下载 JDK下载 注:如果网页不允许下载,使用wget命令下载即可,下载之后安装。 建议使用rpm安装,之后使用 update-alternatives --config java 控制当前环境使用Java的版…...

开发一款通过蓝牙连接控制水电表的微信小程序

增强软硬件交互 为了更好的解决师生生活中的实际问题,开发蓝牙小程序加强了和校区硬件的交互。 比如通过蓝牙连接控制水电表,减少实体卡片的使用。添加人脸活体检测功能,提高本人认证效率,减少师生等待时间。 蓝牙水电控展示 蓝…...

力扣14.最长公共前缀

思路:将字符串数组中第一个字符串用作参考; 8.将他的长度作为范围,因为超范围了之后就不会再有公共前缀了 9.将字符串数组的长度也作为范围,意思是便利字符串数组中的字符串 11.开始第一层循环,依次遍历第一个字符串的…...

你也喜欢“钓鱼“吗?

免责声明:本文仅做分享! 目录 什么是网络钓鱼 流程 攻击手法 0-隐藏自己 1-office宏 创建xxx.dotm 创建xxx.docx 2-RLO 自解压 3-快捷方式lnk 4-邮件伪造 Swaks Gophish 5-网站克隆 setoolkit nginx反向代理 前端页面克隆 6-wifi钓鱼 7-其他 防御 溯源 反…...

druid jdbc 执行 sql 输出 开销耗时

druid 执行sql输出 参考链接配置_LogFilter alibaba/druid Wiki GitHub 看不太懂的往这里瞅瞅。 1. 别名映射 这个地方 给我们提供了 5 种 logfilter : log4j、log4j2、slf4j、commonlogging和commonLogging 每一种实际上都代表一个日志框架 或 日志门面。 -Ddruid.fil…...

C++如何处理内存碎片问题

目录 一.前言二.什么是内存碎片三.如何处理内存碎片 一.前言 这篇文章简单讨论一下C如何处理内存碎片问题。 二.什么是内存碎片 所谓内存碎片就是系统中存在的不能供进程使用的小块内存,主要包括外部碎片以及内部碎片。 外部碎片:内存分配和回收的过…...

FreeRTOS常用API接口函数

提示:FreeRTOS常用API接口函数:并对部分参数附上自己的解释,后面继续补充 FreeRTOS常用API接口函数 1.任务相关的API1.1 创建任务:xTaskCreate1.2 开启任务调度器函数:vTaskStartScheduler1.3 任务的删除:vTaskDelete1…...

DesignPattern设计模式

1 前言 1.1 内容概要 理解使用设计模式的目的掌握软件设计的SOLID原则理解单例的思想,并且能够设计一个单例理解工厂设计模式的思想,能够设计简单工厂,理解工厂方法了解建造者模式的思想,掌握其代码风格理解代理设计模式的思想&a…...

3.ChatGPT在教育领域的应用:教学辅助与案例分享(3/10)

ChatGPT在教育领域的应用:教学辅助与案例分享 引言 在21世纪的教育领域,技术革新正以前所未有的速度改变着传统的教学和学习方式。随着人工智能(AI)的快速发展,教育技术(EdTech)领域迎来了新的…...

Kafka+PostgreSql,构建一个总线服务

之前开发的系统,用到了RabbitMQ和SQL Server作为总线服务的传输层和存储层,最近一直在看Kafka和PostgreSql相关的知识,想着是不是可以把服务总线的技术栈切换到这个上面。今天花了点时间试了试,过程还是比较顺利的,后续…...

电脑怎么录屏?四款录屏工具分享

作为一个刚刚踏入视频创作领域的新手,我一直在寻找一款适合自己的录屏软件。最近,我尝试了四款市面上比较热门的录屏工具。今天,就让我来分享一下我的使用体验,希望能给同样在寻找录屏软件的朋友们一些参考。 一、福昕录屏大师 …...

Java代码审计篇 | ofcms系统审计思路讲解 - 篇4 | XXE漏洞审计

文章目录 Java代码审计篇 | ofcms系统审计思路讲解 - 篇4 | XXE漏洞审计0. 前言1. XXE代码审计【有1处】1.1. 搜索JRXmlLoader1.1.1. JRAntApiWriteTask1.1.2. JRAntUpdateTask1.1.3. TableReportContextXmlRule1.1.4. JasperCompileManager【存在漏洞】 1.2. 搜索XMLReader1.2…...

Leetcode 每日一题:Word Ladder

写在前面: 今天我们来看一道图论的题,这道题目是我做过目前最难与图论联想到的一道题目之一。如果没有提示的话,我们很容易往 dp 等解决 array 问题的方向去解决它,经过我超过 2个小时的思考我觉得这种方向是没前途的&#xff5e…...

c++ 编辑器 和 编译器 的详细解释

在 C 开发中,编辑器 和 编译器 是两个不同的工具,分别在编写代码和生成可执行文件的过程中起着不同的作用。下面是它们的详细介绍: 1. 编辑器(Editor) 编辑器 是用来编写和编辑代码的工具。C 代码就是通过编辑器编写…...

计算机视觉(二)—— MDPI特刊推荐

特刊征稿 01 期刊名称: Applied Computer Vision and Pattern Recognition: 2nd Volume 截止时间: 摘要提交截止日期:2024年10月30日 投稿截止日期:2024年12月30日 目标及范围: 包括但不限于以下领域&#xff1a…...

交叉编译工具链的安装及带wiringPi库的交叉编译实现

交叉编译工具链的安装及带wiringPi库的交叉编译实现 交叉编译的概念交叉编译工具链的安装下载交叉编译工具链配置环境遍变量编译程序到ARM平台 带wiringPi库的交叉编译下载编译wiringPi库调用树莓派的wringPi库 交叉编译的概念 交叉编译是在一个平台上生成另一个平台上的可执行…...

java: 程序包org.junit.jupiter.api不存在

明明idea没有报错,引用包也没问题,为啥提示java: 程序包org.junit.jupiter.api不存在? 配置!还TMD是配置! 如果是引用包的版本不对或者其他,直接就是引用报错或者pom里面飘红了。 这个应该是把generat…...

代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯

代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯 1.动态规划理论基础 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题…...

为什么矩阵特征值之和等于主对角线元素之和,特征值乘积等于行列式值

首先给出特征值和特征向量的定义。 设A是n阶矩阵,如果数λ和n维非零向量x使关系式 Axλx (1) 成…...

ssm+java2026年毕设司库管理系统【源码+论文】

本系统(程序源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、选题背景关于企业理财与融资管理问题的研究,现有研究主要以大型企业ERP系统或通用财务管理软件为主,专门针对中…...

做了5年GEO优化,我敢说90%的企业都没看懂GEO的真实成本

很多人来问我 GEO 是什么意思,大多是听别人说这是 AI 时代的获客新路子,能比传统推广省好几倍的钱,还能让 AI 优先推荐自己家。但我每次都先不说那些好听的好处,先给大家算清楚,做 GEO 这件事里,那些 90% 的…...

保姆级避坑指南:Ubuntu系统下Hadoop HA集群搭建,我踩过的那些SSH和配置文件的“坑”

Ubuntu下Hadoop HA集群搭建:那些教科书不会告诉你的实战陷阱 第一次在Ubuntu上搭建Hadoop HA集群时,我天真地以为照着官方文档就能顺利跑起来。直到SSH连接莫名其妙失败、JournalNode权限报错刷屏、ZKFC死活不启动时,才明白为什么有人说大数据…...

5分钟搞懂3GPP NTN标准:从Release16到19的关键技术演进与实战应用

5分钟搞懂3GPP NTN标准:从Release16到19的关键技术演进与实战应用 当全球通信行业将目光投向低轨卫星星座与高空平台时,3GPP的NTN(非地面网络)标准正在重塑连接边界。本文将以工程师视角,带您穿透技术文档迷雾&#xf…...

别再死记硬背了!用HuggingFace Diffusers库5分钟搞懂Stable Diffusion的VAE、U-Net和CLIP怎么协同工作

5分钟透视Stable Diffusion核心组件:用HuggingFace Diffusers实战VAE/U-Net/CLIP协同机制 当你在HuggingFace Diffusers库中第一次调用StableDiffusionPipeline时,是否好奇过那段简短的文本提示如何变成精美图像?这背后是VAE、U-Net和CLIP三…...

手把手教你用丹青识画:智能影像雅鉴系统保姆级入门教程

手把手教你用丹青识画:智能影像雅鉴系统保姆级入门教程 1. 认识丹青识画系统 "以科技之眼,点画意之睛。"这句话完美诠释了丹青识画系统的核心理念。这是一款将人工智能技术与东方美学相结合的创新工具,能够自动分析图像内容并生成…...

python基于微信小程序的智慧社区娱乐服务管理平台

目录需求分析与规划技术架构设计功能模块开发实时交互实现数据可视化测试与部署安全与优化迭代计划项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作需求分析与规划 明确平台核心功能:居民活动报名、场地预约、社区公…...

KMS_VL_ALL_AIO激活工具完全指南:从问题诊断到长效管理

KMS_VL_ALL_AIO激活工具完全指南:从问题诊断到长效管理 【免费下载链接】KMS_VL_ALL_AIO Smart Activation Script 项目地址: https://gitcode.com/gh_mirrors/km/KMS_VL_ALL_AIO 如何诊断Windows/Office激活失败的核心原因? 1.1 激活失败的三大…...

DOL-CHS-MODS实战指南:从入门到精通的5个关键步骤

DOL-CHS-MODS实战指南:从入门到精通的5个关键步骤 【免费下载链接】DOL-CHS-MODS Degrees of Lewdity 整合 项目地址: https://gitcode.com/gh_mirrors/do/DOL-CHS-MODS 副标题:一站式解决Degrees of Lewdity汉化与Mod整合难题,让你轻…...

水下机器人导航的‘感官进化’:从纯视觉VIO到声光惯压融合的SVIn2系统拆解

水下机器人导航的‘感官进化’:从纯视觉VIO到声光惯压融合的SVIn2系统拆解 当一台水下机器人潜入浑浊的湖泊执行管道巡检任务时,它的视觉传感器突然失效——悬浮颗粒使画面变成乳白色噪点,而水流扰动让惯性测量单元(IMU)数据充满噪声。这正是…...