一文理解哈希冲突四种解决方法

简介: 一文理解哈希冲突四种解决方法

哈希冲突的产生原因
哈希是通过对数据进行再压缩,提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的,而数据可能比较多,导致经过哈希函数处理后仍然有不同的数据对应相同的索引值。这时候就产生了哈希冲突(两个值都需要同一个地址索引位置)。

产生哈希冲突的影响因素
装填因子(装填因子=数据总数 / 哈希表长)、哈希函数、处理冲突的方法

解决哈希冲突的四种方法
其实也就是哈希表的实现。

1.开放地址方法(再散列法)

可以通俗理解为所有的地址都对所有的数值开放,而不是链式地址法的封闭方式,一个数值固定在一个索引地址位置。

p1=hash(key)如果冲突就在p1地址的基础上+1或者散列处理,p2=hash(p1)....

  (1)线性探测

   按顺序决定值时,如果某数据的值已经存在,则在原来值的基础上往后加一个单位,直至不发生哈希冲突。

image.png

  (2)再平方探测

   按顺序决定值时,如果某数据的值已经存在,则在原来值的基础上先加1的平方个单位,若仍然存在则减1的平方个单位。随之是2的平方,3的平方等等。直至不发生哈希冲突。

和线性探测相比就是改变探测了步长。因为如果都是+1来探测在数据量比较大的情况下,效率会很差。
image.png

  (3)伪随机探测

   按顺序决定值时,如果某数据已经存在,通过随机函数随机生成一个数,在原来值的基础上加上随机数,直至不发生哈希冲突。

2.链式地址法(HashMap的哈希冲突解决方法)
image.png

  对于相同的值,使用链表进行连接。使用数组存储每一个链表。

  优点:

  (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

  (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

  (3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

   (4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

    缺点:

  指针占用较大空间时,会造成空间浪费,若空间用于增大散列表规模进而提高开放地址法的效率。

3.建立公共溢出区

  建立公共溢出区存储所有哈希冲突的数据。

4.再哈希法

  对于冲突的哈希值再次进行哈希处理,直至没有哈希冲突。

可以理解为p=hash(key)如果冲突就p=hash2(key)....

image.png

image.png

相关文章
|
存储 算法 Serverless
解决哈希冲突的方式
解决哈希冲突的方式
726 0
|
存储 关系型数据库 数据库
聊多版本并发控制(MVCC)
MVCC是数据库并发控制技术,用于减少读写冲突。它维护数据的多个版本,使事务能读旧数据而写新数据,无需锁定记录。当前读获取最新版本,加锁防止修改;快照读不加锁,根据读取时的读视图(readview)决定读哪个版本。InnoDB通过隐藏字段(DB_TRX_ID, DB_ROLL_PTR)和undo log存储版本,readview记录活跃事务ID。读已提交每次读取都创建新视图,可重复读则在整个事务中复用一个视图,确保一致性。MVCC通过undo log版本链和readview规则决定事务可见性,实现了非阻塞并发读。
2142 5
聊多版本并发控制(MVCC)
|
存储 算法 NoSQL
还分不清 Cookie、Session、Token、JWT?看这一篇就够了
Cookie、Session、Token 和 JWT(JSON Web Token)都是用于在网络应用中进行身份验证和状态管理的机制。虽然它们有一些相似之处,但在实际应用中有着不同的作用和特点,接下来就让我们一起看看吧,本文转载至http://juejin.im/post/5e055d9ef265da33997a42cc
52607 16
|
设计模式 监控 安全
JUC第一讲:Java并发知识体系详解 + 面试题汇总(P6熟练 P7精通)
JUC第一讲:Java并发知识体系详解 + 面试题汇总(P6熟练 P7精通)
5000 0
|
11月前
|
存储 Serverless
哈希冲突
哈希冲突可通过优化哈希函数或采用冲突解决策略应对。开放寻址法通过线性、二次探查或双散列寻找空位,但易导致聚集,影响效率;链表法则在冲突位置构建链表,避免抢占,更适应动态数据,是常用方案之一。
|
关系型数据库 MySQL 数据库
mysql 里创建表并插入数据
【10月更文挑战第5天】
1183 1
|
存储 数据采集 人工智能
切块、清洗、烹饪:RAG知识库构建的三步曲
大语言模型明明已经喂了大量文档,为什么还是答非所问?就像米其林厨师需要精心处理食材,RAG系统也需要巧妙处理文档。从文本分块、清洗到结构化索引,这些不起眼的处理步骤决定了AI回答质量的上限。掌握这些技巧,让你的RAG系统从「路边摊」蜕变为「米其林餐厅」。
2138 3
|
存储 安全 Java
ThreadLocal - 原理与应用场景详解
ThreadLocal是Java中用于实现线程隔离的重要工具,为每个线程提供独立的变量副本,避免多线程数据共享带来的安全问题。其核心原理是通过 ThreadLocalMap 实现键值对存储,每个线程维护自己的存储空间。ThreadLocal 广泛应用于线程隔离、跨层数据传递、复杂调用链路的全局参数传递及数据库连接管理等场景。此外,InheritableThreadLocal 支持子线程继承父线程的变量值,而 TransmittableThreadLocal 则解决了线程池中变量传递的问题,提升了多线程上下文管理的可靠性。深入理解这些机制,有助于开发者更好地解决多线程环境下的数据隔离与共享挑战。
2436 44
|
人工智能 PHP 开发工具
Cursor 完全使用教程
Cursor 是由 Anysphere 实验室开发的一款 AI 驱动代码编辑器,基于 VSCode 深度定制,支持导入 VSCode 配置。相比 GitHub Copilot 插件,Cursor 在代码补全、对话生成、多文件修改等方面体验更优,支持快捷键快速调用 AI 功能,提供丰富上下文注记,提升开发效率。需订阅使用,适合追求高效编程体验的开发者。
|
算法 Java Sentinel
限流算法(计数器、滑动时间窗口、漏斗、令牌)原理以及代码实现
> 本文会对这4个限流算法进行详细说明,并输出实现限流算法的代码示例。 > 代码是按照自己的理解写的,很简单的实现了功能,还请大佬们多多交流找bug。
3394 0