精选文章 hash冲突解决

hash冲突解决

作者:csdn_9527666 时间: 2020-07-26 11:29:42
csdn_9527666 2020-07-26 11:29:42

1 开放寻址法

如冲突则根据指定步长向后寻找直到找到空位或没有位置

步长算法:

1.1 线性探查 步长为1 如threadlocal

key1:hash(key)+0

key2:hash(key)+1

key3:hash(key)+2

1.2 平方探测法  计算下一次的步长

key1:hash(key)+0

key2:hash(key)+1^2

key3:hash(key)+2^2

1.3  随机探测法 步长为随机生成的数  疑问:查询时如何查?如遍历查询有何意义?

缺点:

  • 查找性能不好:这种方法建立起来的哈希表,当冲突多的时候数据容易堆集在一起,这时候对查找不友好;
  • 删除节点不能真实删除浪费内存:删除结点的时候不能简单将结点的空间置空,否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点,只能在被删结点上添加删除标记,而不能真正删除结点;
  • 如果哈希表的空间已经满了,还需要建立一个溢出表,来存入多出来的元素。
  • 为了减少冲突,负载因子要小些,导致内存浪费

 

2 再哈希

有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数  直到不再冲突

也存在不能删除的问题? 如删除某元素后,查询另一个key调用第二个哈希函数后查询为null 无法确定继续处理还是key不存在?

缺点: 增加了计算时间

 

3 建立公共溢出区

将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

缺点:  如未能命中哈希表 需要遍历查找溢出表 查询效率低

 

4 拉链法(或成树法, 树是一种特殊的链表。树形转化后 插入更慢(相比于头插法) 查询更快(冲突节点数目较多时))

如出现冲突,将其作为链表一个节点加入头或者尾巴处(分为头插法和尾插法)

拉链法的优点:

  • 处理冲突的方式简单,且无堆集现象,一般不会发生冲突,因此平均查找长度较短;
  • 由于拉链法中各链表上的结点空间是动态申请的,所以它更适合造表前无法确定表长的情况;
  • 删除结点操作易于实现,只要简单地删除链表上的相应的结点即可。

拉链法的缺点:需要额外的存储空间。

从HashMap的底层结构中我们可以看到,HashMap采用是数组+链表/红黑树的组合来作为底层结构,也就是开放地址法+链地址法的方式来实现HashMap。

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:matplotlib绘制常见统计图形(一)

下一篇:[kuangbin带你飞]专题1-23 专题一 简单搜索 POJ 1426 Find The Multiple 用深搜dfs枚举结果+习得llu

您可能感兴趣

  • 提升办公室沟通技能,推荐你看这本书

    无论是对谁做了什么的误解,观念的冲突或人际关系的纠结,在任何工作场所都会不可避免地发生冲突。 但是,冲突的根源通常是沟通不畅。沟通不力,效率低下,会导致错过最后期限、错过机会和产生误解。 笔者建议职场人能多读一些类似《沟通与说服必读12篇》一类的经典沟通类书籍来提升办公室沟通技能。以下是通过更好的沟通来解决冲突和改善同事关系的四种方法。 1.立即公开解决问题。 当你的团队成员之间发生冲突时,...

  • 打家劫舍系列: 198.打家劫舍 213.打家劫舍2 337.打家劫舍3

    198.打家劫舍1 线性的dp,终于可以用到我自己的思路了,f[i]表示偷第i家所能得到的最大金币,那么它必然不能偷第i-1家,即从f[i-2]转移过来,但是我也可以不偷i-2,所以可以从f[i-3]转移过来,但是我不能不偷i-3了,因为中间隔了3个的话,必然能在中间再偷一个,(假设数据都是正数),所以自然而然想到转移方程 f[i]=max(f[i-2],f[i-3])+nums[i-3];...

  • Linux系统内存

    Linux 内存是后台开发人员,需要深入了解的计算机资源。合理的使用内存,有助于提升机器的性能和稳定性。本文主要介绍Linux 内存组织结构和页面布局,内存碎片产生原因和优化算法,Linux 内核几种内存管理的方法,内存使用场景以及内存使用的那些坑。 从内存的原理和结构,到内存的算法优化,再到使用场景,去探寻内存管理的机制和奥秘。 一、走进Linux 内存 1、内存是什么? 1)内存又称主存...

  • CAS存在的三大问题以及解决方案

    CAS的由来 在JDK 5之前Java语言是靠synchronized关键字保证同步的,这会导致有锁 锁机制存在以下问题: 在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。 一个线程持有锁会导致其它所有需要此锁的线程挂起。 如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。 volatile是不错的机制,但是volatile不能保...

  • js,javascript作用域, 全局局部作用域, 全局变量和局部变量, 块级作用域, 作用域链

    1.javaScript作用域 2.全局作用域(函数作用域) 局部作用域(函数作用域) 3.全局变量和局部变量 4.块级作用域 5.作用域链 1.预解析 2.变量预解析和函预解析 Document

  • 论文|从DSSM语义匹配到Google的双塔深度模型召回和广告场景中的双塔模型思考...

    点击标题下「搜索与推荐Wiki」可快速关注 ▼ 相关推荐 ▼ 1、基于DNN的推荐算法介绍 2、传统机器学习和前沿深度学习推荐模型演化关系 3、论文|AGREE-基于注意力机制的群组推荐(附代码) 4、论文|被“玩烂”了的协同过滤加上神经网络怎么搞? 本文包含(文章较长,建议先收藏再阅读,点击文末的阅读原文,查看更多推荐相关文章): DSSM DSSM的变种 MV-DNN Google Tw...

  • Synchronized和Lock的区别

    Synchronized和Lock的区别 并发编程中,锁是经常需要使用的。在开发中我们常用的锁有两种Synchronized和Lock。 线程安全问题 线程安全是在多线程编程中,有可能会出现同时访问同一个 共享、可变资源 的情况,始终都不会导致数据破坏以及其他不该出现的结果。这种资源可以是一个变量、一个对象、一个文件等。 共享:多个线程可以同时访问该共享变量。 可变:数据在生命周期中可以被改...

  • 芯片破壁者(十.上):风起樱花之地

    在不断升级的中美科技战中,每个人都很容易发现,在芯片上受制于人似乎是一个最难解的谜题。面对这种情况,很多国人可能都在思考:我们到底有没有可能打破“芯片枷锁”? 而从历史里寻找答案是文明的天性,在审视国家间的半导体博弈时,有一个无法绕开的话题,就是上世纪60年到到90年代,横跨数十年、关系错综复杂的美日半导体纠葛。这段历史中最为人津津乐道的有两点。一是日本在80年代一跃超过美国成为全球半导体产...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。