散列函数的基本概念
散列函数
算法不能设计太过复杂
- 太复杂的散列函数,势必会消耗很多计算时间
散列函数生成的值要尽可能随机并且均匀分布
- 这样才能避免或者最小化散列冲突
- 而且即便出现来冲突,散列到每个槽里的数据也会比较平均,不会出现某个槽内数据特别多的情况
散列冲突
开放寻址法
概述
如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入
优点
- 开放寻址法不像链表法,需要拉很多链表
- 散列表中的数据都存储在数据中,可以有效利用CPU缓存加快查询速度而且这样实现的散列表,序列化起来比较简单,链表法包含指针,序列化起来就没那么容易
缺点
- 删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据
- 所有数据都存储在一个数组中,比起链表法来说,冲突的代价更高
- 所有,使用开放寻址解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间
方法
线性探测(Linear Probing)
当往散列表中插入数据时,如果某个数据经过散列函数之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止
二次探测(Quadratic probing)
线性探测每次探测的步长是1,那它探测的下标序列就是hash(key) + 0, hash(key) + 1, hash(key) + 2 …
而二次探测探测的步长就变成原来的“二次方”, 也就是说,它探测的下标序列就是 hash(key) + 0, hash(key) + (1 ^ 2), hash(key) + (2 ^ 2)
双重散列(Double hashing)
不仅要使用一个散列函数。我们使用一组散列函数 hash1(key), hash2(key), hash3(key)
我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列,依次类推找到空闲的存储位置
装载因子(load factor)
不管采用那种方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高
为了尽可能保证散列表的操作效率,一般情况下,我们会尽快保证散列表中有一定比例的空闲槽位
状态因子概述及公式
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
装载因子来表示空位多少,状态因子越大,说明空闲位置越少,冲突越多,散列表的性能就会下降
如何解决装载因子过大的问题?
动态扩容
- 重新申请一个更大的散列表,将数据搬移这个新的散列表中
- 假设每次扩容我们都申请一个原来散列表大小两倍的空间。如果原来散列表的装载因子是0.8,那经过扩容之后,新散列表的装载因子因子就下降为原来的一半,变成了0.4
装载因子阀值的设置要权衡时间,空间复杂度
- 如果内存空间不紧张,对执行效率要求很高,可以降低负载因子的阀值
- 相反,如果内存空间紧张,对执行效率要求又不高,可以增加负载因子的值,甚至可以大于1
如何避免低效地扩容?
为了解决一次性扩容耗时过多的情况,我们可以将扩容操作穿插在插入操作的过程中,分批完成
当装载因子触达阀值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中
当有新数据要插入时,我们将新数据插入新散列表中,并且从老的散列表中拿出一个数据放入新散列表中
每次插入一个数据到散列表,我们都重复上面的过程。经过多次插入操作之后,老的散列表中的数据就一点一点全部搬移到新散列表中
这时间的查询,为了兼容了新,老散列表中的数据,我们先从新散列表中查找,如果没有找到,再去老的散列表中查找
通过这样均摊的方法,将一次性扩容的代价,均摊到多次插入操作中,就避免一次性扩容耗时过多的情况。这种实现方式,任何情况下,插入一个数据的时间复杂度都是O(1)
链表法
概述
在散列表中,每个"桶(bucket)" 或者"槽(slot)" 会对应一条链条,所以散列值相同的元素我们都会放在相同槽位对应的链表中
当插入的时候,我们只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度O(1)
当查找删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或删除。那查找或删除操作的时间复杂度是多少呢?
- 实际上,这两个操作的时间复杂度跟链表的长度k成正比,也就是O(k)
- 对于散列比较均匀的散列函数来说,理论上讲, k = n / m,其中n表示散列中数据个数,m表示散列中“槽”的个数
优点
- 链表法对内存的利用率比开放寻址法要高
- 因为链表结点可以在需要的时候再创建,并不需要像开放寻址法那样事先申请好
- 链表法比起开放寻址法,对大装载因子的容忍度更高
- 开放寻址法只能适用装载因子小于1的情况
- 接近1时,就可能会又大量的散列冲突,导致大量的探测,再散列等,性能会下降很多
- 但是对于链表法,只要散列函数的只随机均匀,即便装载因子变成10,也就是链表的长度变长了而已,虽然查找效率有所下降,但是比起顺序查找还是快很多
缺点
- 链表因为要存储指针,所有对于比较小的对象的存储,是比较消耗内存,还有可能会让内存的消耗翻倍
- 而且,因为链表中的结点是零散分布在内存中,不是连续,所有对于CPU缓存是不友好的,这方面对于执行效率也有一定的影响
- 总结
- 基于链表的散列冲突处理方法比较合适存储大对象,大数据量的散列表
- 而且,比起开放寻址法,它更加灵活,支持更多优化策略,比如用红黑树代替链表
工业级的散列表应该具有哪些特征?
要求
支持快速的查询,插入,删除操作
内存占用合理,不能浪费过多的内存空间
性能稳定,极端情况下,散列表的性能也不会退化到无法接受的程度
设计
设计一个合适的散列函数
定义装载因子阀值,并且设计动态扩容策略
选择合适的散列冲突解决方法
散列表的缺点和改进
缺点
- 散列表这种数据结构虽然支持非常高效的数据插入,删除,查找操作,但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就是,它无法支持按照某种顺序快速地遍历数据
- 如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历
改进
- 因为散列表是动态数据结构,不停有数据的插入,删除,所以每当我们希望按顺序遍历散列表中的数据的时候,都需要先排序,那效率势必会很低
- 为了解决这个问题,我们将散列表和链表(或跳表)结合一起使用
资料参考
- [Data Structure & Algorithm] Hash那点事儿
相关文章:
散列函数的基本概念
散列函数 算法不能设计太过复杂 太复杂的散列函数,势必会消耗很多计算时间 散列函数生成的值要尽可能随机并且均匀分布 这样才能避免或者最小化散列冲突而且即便出现来冲突,散列到每个槽里的数据也会比较平均,不会出现某个槽内数据特别多…...
【C++拷贝构造函数深浅拷贝】
拷贝构造函数 注意:访问权限是public 拷贝构造函数:类名(const 类名& 对象名){} 可以有多个参数 。 没有常引用就是普通构造函数 如果不写,编译器自己会给一个(作用仅仅是赋值,默认拷…...
快速编译安装tensorrt_yolo
快速编译安装 安装 tensorrt_yolo 通过 PyPI 安装 tensorrt_yolo 模块,您只需执行以下命令即可: pip install -U tensorrt_yolo 如果您希望获取最新的开发版本或者为项目做出贡献,可以按照以下步骤从 GitHub 克隆代码库并安装: …...
外盘黄金期货需要注意什么?
为大家整理了关于黄金做单的五大原则,相信对于新手投资者来说肯定会产生一定的帮助。 1、看多空:主要有两种方法,基本面判断和技术面判断,基本面判断,主要是借助基本信息面,如政策。供需,产量…...
Allegro光绘Gerber文件、IPC网表、坐标文件、装配PDF文件导出打包
Allegro光绘Gerber文件、IPC网表、坐标文件、装配PDF文件导出打包 一、Gerber文件层叠与参数设置二、装配图文件设置导出三、光绘参数设置四、Gerber孔符图、钻孔表及钻孔文件输出五、输出Gerber文件六、输出IPC网表七、导出坐标文件八、文件打包 一、Gerber文件层叠与参数设置…...
mysql的索引可以分为哪些类型
MySQL的索引是用于提高查询性能的重要数据结构。不同类型的索引在不同的使用场景中具有不同的优势和适用性。 1. 主键索引(Primary Key Index) 特点:唯一且不允许 NULL 值。用途:唯一标识表中的每一行。自动创建:定义…...
Content type ‘application/x-www-form-urlencoded;charset=UTF-8‘ not supported
Content type application/x-www-form-urlencoded;charsetUTF-8 not supported 问题背景新增页面代码改造 问题背景 这里有一个需求,前端页面需要往后端传参,参数包括主表数据字段以及子表数据字段,由于主表与子表为一对多关系,在…...
【JavaEE进阶】——利用框架完成功能全面的图书管理系统
目录 🚩项目所需要的技术栈 🚩项目准备工作 🎈环境准备 🎈数据库准备 🚩前后端交互分析 🎈登录 📝前后端交互 📝实现服务器代码 📝测试前后端代码是否正确 &am…...
WDF驱动开发-内存缓冲区
驱动程序通常使用内存缓冲区向/从框架和其他驱动程序传递数据,或在本地存储信息。 WDF常见的内存缓冲区包括框架内存对象(WDFMEMORY)、 lookaside、 MDL 和 本地缓冲区。 使用框架内存对象 框架使用 内存对象 来描述驱动程序从中接收并传递给框架的内存缓冲区。 每…...
c语言连接两个字符串
在C语言中,连接两个字符串可以使用 strcat 函数。这个函数将一个字符串复制到另一个字符串的末尾。使用 strcat 函数之前,需要确保目标字符串有足够的空间来容纳源字符串,否则可能会导致缓冲区溢出。 下面是一个使用 strcat 函数连接两个字符…...
基于springboot的大学计算机基础网络教学系统
文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于springboot的大学计算机基础网络教学…...
UOS常用命令
shutdown 关机 reboot 重启 reboot -f 强制重启 history 查看使用的历史命令 history -c 清空命令行常见目录结构 /bin 存储常用用户指令 /boot 存放用于系统引导时使用的各种文件 /dev 存放设备文件 /etc 存放系统,服务的配置…...
vue3 如何给表单添加表单效验+正则表达式
校验要求 我们的表单中有密码、电话号码 ,两项。 我们设置用密码为3到20位的非空字符 电话号码就用目前用的电话号码正则表达式,要求手机号码以 1 开头,第二位为 3 到 9 之间的数字,后面跟着任意 9 个数字,总共是 11…...
JavaScript算法实现dfs查找省市区路径
需求 存在如下数组,实现一个算法通过输入区名,返回省->市->区格式的路径,例如输入西湖区,返回浙江省->杭州市->西湖区。 // 定义省市区的嵌套数组 const data [{name: "浙江省",children: [{name: "…...
map文件分析
以下是一个具体的map文件示例,并附上详细的描述,帮助你更好地理解如何读取和分析map文件: 示例map文件 Memory ConfigurationName Origin Length Attributes FLASH 0x08000000 0x0…...
MySQL-创建表~数据类型
070-创建表 create table t_user(no int,name varchar(20),gender char(1) default 男);071-插入数据 语法格式: insert into 表名(字段名1, 字段名2, 字段名3,......) values (值1,值2,值3,......);insert into t_user(no, name, gender) values(1, Cupid, 男);字…...
【鸿蒙 HarmonyOS】Swiper组件
一、背景 项目中通常会遇到图片轮播,内容轮播的场景;如:在一些应用首页显示推荐的内容时,需要用到轮播显示的能力。 二、源码地址 ✍Gitee开源项目地址👉:https://gitee.com/cheinlu/harmony-os-next-swi…...
玩具机器人脚本适合场景
玩具机器人脚本作为一个模拟的玩具机器人脚本,适合以下场合: 1.教育和学习:对于初学者和编程爱好者来说,这个脚本是一个很好的学习工具,可以帮助他们理解如何编写和执行简单的控制逻辑。 2.在计算机科学、机器人技术或…...
人工智能模型组合学习的理论和实验实践
组合学习,即掌握将基本概念结合起来构建更复杂概念的能力,对人类认知至关重要,特别是在人类语言理解和视觉感知方面。这一概念与在未观察到的情况下推广的能力紧密相关。尽管它在智能中扮演着核心角色,但缺乏系统化的理论及实验研…...
MySQL备份与恢复:确保数据的安全与可靠性
引言: 数据的安全性和可靠性的重要性 在现代企业和组织中,数据已经成为了最重要的资产之一。数据的安全性和可靠性对于企业的运营至关重要。首先,数据的安全性保证了敏感信息不会落入错误的手中,防止了潜在的经济损失和法律风险。其次,数据的可靠性则确保了企业能够准确…...
Noisee AI – AI音乐影片MV在线生成工具,专门为Suno的好搭子来了~
导读 现在很多各大平台,抖音、快手、微视,还不能直接发布音频文件,如果有一个好听的音乐想做成MV,怎么办呢? 这时候就是Noisee AI的主场,上传一段音乐加上简单的描述就可以在3-5分钟内生成一个可以发布到…...
实战计算机网络02——物理层
实战计算机网络02——物理层 1、物理层实现的功能2、数据与信号2.1 数据通信模型2.2 通信领域常用术语2.3 模拟信号和数字信号 3、信道和调制3.1 信道3.2 单工通信、半双工通信、全双工通信3.3 调制3.4 奈式准则3.5 香农定律 4、传输媒体4.1 导向传输媒体4.2 非导向传输媒体 5、…...
Doris:冷热分层
目录 一、冷热分层介绍 二、存储策略(Storage policy) 2.1 创建存储资源 2.2 创建存储策略 2.3 使用存储策略 三、使用限制 一、冷热分层介绍 冷热分层支持所有 Doris 功能,只是把部分数据放到对象存储上,以节省成本&am…...
28.启动与暂停程序
上一个内容:27.设计注入功能界面 以它 27.设计注入功能界面 的代码为基础进行修改 点击添加游戏按钮之后就把游戏启动了 CWndINJ.cpp文件中修改: void CWndINJ::OnBnClickedButton1() {// TODO: 在此添加控件通知处理程序代码/*ExeLst.InsertItem(0, L…...
404 页面代码
<template> <div class"container"><h1>404</h1> <div ><p class"text-center">当前页面无法访问,可能没有权限或已删除</p><p class"text-center"> 去别处看看吧</p> </div> <…...
java设计模式和面向对象编程思想
Java设计模式和面向对象编程思想是软件开发中的核心概念,对于构建可维护、可扩展的软件系统至关重要。下面是对这两个主题的知识点总结: 面向对象编程(OOP)思想 封装:将数据(属性)和操作这些数据…...
超万卡训练集群网络互联技术解读
超万卡训练集群互联关键技术 大模型迈向万亿参数的多模态升级,万卡集群计算能力亟需飞跃。关键在于增强单芯片性能、提升超节点算力、融合DPU多计算能力,并追求算力能效比极致。这一系列提升将强有力支撑更大规模模型训练和推理,快速响应业务…...
AtomicInteger类介绍
文章目录 一、AtomicInteger的定义二、AtomicInteger的使用场景和作用1.使用场景2.作用 三、AtomicInteger的常用方法四、AtomicInteger的底层原理五、AtomicInteger和Integer的区别1.数据类型与线程安全性2.默认值与初始化3.常用方法与操作:4.内存模型与可见性5.使…...
Es 索引查询排序分析
文章目录 概要一、Es数据存储1.1、_source1.2、stored fields 二、Doc values2.1、FieldCache2.2、DocValues 三、Fielddata四、Index sorting五、小结六、参考 概要 倒排索引 优势在于快速的查找到包含特定关键词的所有文档,但是排序,过滤、聚合等操作…...
【C语言】解决C语言报错:Format String Vulnerability
文章目录 简介什么是Format String VulnerabilityFormat String Vulnerability的常见原因如何检测和调试Format String Vulnerability解决Format String Vulnerability的最佳实践详细实例解析示例1:直接使用不受信任的输入作为格式化字符串示例2:未验证格…...
怎么做阿里国际网站的数据分析/最新全国疫情消息
1. springMVC中controller的几种返回类型 Controller方法的返回值可以有以下几种: 1、返回ModelAndView 返回ModelAndView时最常见的一种返回结果。需要在方法结束的时候定义一个ModelAndView对象,并对Model和View分别进行设置。 2、返回String 1&a…...
免费字体下载/百度seo自然优化
计算机网络,谢希仁主编《计算机网络(第5版)》电子工业出版社。复习习题集:《计算机网络知识要点与习题解析》哈尔滨工程大学出版社。考研就是打持久战,谁坚持到最后,谁就会取得胜利,考研又像挖井…...
做网站毕业设计/微信推广软件哪个好
1、下载android源码2、在linux下生成android.ipr等执行下面的命令即可生成android.ipr等文件:cd ~/aosp //具体的源码根目录source build/envsetup.sh //用于初始化环境变量mmm development/tools/idegen/ //生成文件out/host/linux-x86/framework/idege…...
北京网站制作公司都在哪里/商业推广软文范例
一.应用知识点1.2实验知识点div布局CSS相对定位CSS各种属性的应用1.3实验环境本实验环境采用带桌面的Ubuntu Linux环境,实验中可能会用到桌面上的程序:Firefox:浏览器,可以用在需要前端界面的课程里,只需要打开环境里写…...
南通网站设计/今日国内新闻大事20条
随着各地市的二级建造师报名工作的结束,二级建造师备考可以提上日程了,那么关于这些备考难点首先你会说是不是网络图,今天小编带你掌握这些网络图首先我们来看某个案例说明:某框架结构工程,第二层现浇钢筋混凝土柱有钢…...
广州做网站新锐/今天北京发生大事了
2016年11月8日,昱辉阳光向德国Saferay公司提供10.4MW多晶硅太阳能光伏组件,在日本建立地面光伏项目。 德国Saferay是一家独立的大型电厂开发商,全球光伏发电系统超过800兆瓦,将于10月完成组件交付。 2016年11月7日,还宣…...