Hash表(四)——Hash冲突解决办法&HashMap分析

1 合理选择 Hash冲突解决办法

Hash表(二)——散列冲突中学到常用的解决 Hash冲突的方法有开放寻址法和链表法。在 JavaThreadLocalMap采用线性探测的开放寻址法来解决冲突, LinkedHashMap采用了链表法解决 Hash冲突,现将开放寻址法和链表法总结如下。

1.1 开放寻址法

  • 优点:将数据存储在数组中;利用CPU缓存加快查询速度;并且序列化简单。
  • 缺点:删除数据麻烦,需要特殊标记已删除的数据;需要将所有数据存储在一个连续的存储空间中,比起链表来说,冲突的代价更高。
  • 适用场景:当数据量较小、装载因子小的时候可以采用开放寻址法。

1.2 链表法

  • 优点:对内存利用率高;对装载因子的容忍度高(开放寻址法只适用在装载因子小于1的情况,接近1时,就可能会有大量散列冲突,导致大量的探测、再散列,性能下降很多。但对于链表法,只要散列函数的值随机均匀,当装载因子大于1时,只是对应的链表长度增加,这里也可以通过将链表改造为跳表或者红黑树的方式加快查找速度)
  • 缺点:由于链表需要存储指针,存储较小的对象时,指针占用的内容消耗比较大;链表不支持随机查找,查找效率较低。
  • 适用场景:适合于存储大对象、数据量大的散列表;比开放寻址法更加灵活,支持更多的优化策略,如使用红黑树替代链表。
  • 优化:我们可将链表法中的链表替换成更加高效的动态的数据结构,如跳表、红黑树等。 如下图所示,将链表优化为红黑树。

2 Java中的 HashMap分析

HashMap是一个成熟的散列表,在Java中得到了广泛应用,下面来具体分析。

2.1 初始大小

如下图所示, HashMap默认的初始大小为16。

如果事先知道数据量的大小,可以通过修改初始大小,减少动态扩容次数,来提升 HashMap性能。

2.2 装载因子和动态扩容

如下图所示, HashMap默认的装载因子为0.75。

HashMap中元素个数超过 0.75*capacitycapacity表示 HashMap实际的容量),就会启动动态扩容,每次扩容的大小为原来的两倍。

2.3 Hash冲突的解决办法

JDK1.8之前, HashMap底层采用的链表法来解决冲突。即使装载因子和 Hash函数设计的再合理,随着数据量的增加也会出现链表过长的情况,一旦链表过长,严重影响了 HashMap的性能。

JDK1.8中对 HashMap底层做了优化。当链表长度大于8时,链表就转化为红黑树,当链表小于8时,将红黑树转化为链表。因为当链表过长的时候,查找的效率将会变慢,利用红黑树快速增删改查的特性,可以提高 HashMap的性能,而链表不长时,红黑树的快速增删改查的特性就不太明显,并且红黑树的还有维护成本,因此当链表不长时,不需要将链表转化为红黑树。

2.4 Hash函数

HashMap中的 Hash函数如下图所示,追求简单高效且分布均匀。

本文分享自微信公众号 - 算法半岛(jacob2359)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java识堂

为你的IDE集成AI,解放双手,我推荐这款神器!

我们平时写代码的时候,多少都会依赖编辑器的代码补全功能,敲几个字母就能补全一个词。可是这么多年过去了,语言升级了很多次,而代码提示却没有升级,还是只能限定在一个...

14750
来自专栏happyJared

MySQL 字符集、校对规则及索引

字符集指的是一种从二进制编码到某类字符符号的映射。校对规则则是指某种字符集下的排序规则。

12330
来自专栏Java研发军团

SpringAop源码全方位剖析,gogogo!

Spring Aop 在 Spring框架中的地位举足轻重,主要用于实现事务、缓存、安全等功能。

10620
来自专栏迈向前端工程师

企业面试题: js中怎么把10进制数123转化为二进制数

若省略该参数,则使用基数 10。但是要注意,如果该参数是 10 以外的其他值,则 ECMAScript 标准允许实现返回任意值。

30430
来自专栏A周立SpringCloud

Spring Cloud Stream 错误处理详解

系统处理方式,因消息中间件不同而异。如果应用没有配置错误处理,那么error将会被传播给binder,binder将error回传给消息中间件。消息中间件可以丢...

19320
来自专栏宜信技术实践

微服务与网关技术(SIA-GateWay)

把时间退回到二十年之前,当时企业级领域研发主要推崇的还是C/S模式,PB、Delphi这样的开发软件是企业应用开发的主流。随着时间的推移,基于浏览器的B/S架构...

33140
来自专栏迈向前端工程师

企业面试题: 比较typeof,instanceof,toString 三种类型检测的区别

7种内置类型:Boolean、Null、Undefined、Number、String、Symbol

14740
来自专栏须臾之余

Java集合源码分析之ArrayList

分析一个类的时候,数据结构往往是它的灵魂所在,理解底层的数据结构其实就理解了该类的实现思路,具体的实现细节再具体分析。

8020
来自专栏MudOnTire

常见数据结构和Javascript实现总结

做前端的同学不少都是自学成才或者半路出家,计算机基础的知识比较薄弱,尤其是数据结构和算法这块,所以今天整理了一下常见的数据结构和对应的Javascript的实现...

9430
来自专栏泰斗贤若如

Could not find resource——mybatis 找不到映射器xml文件

今天用IDEA写Mybatis的时候,测试报了如图所示的错,恶心死我了,后来解决了,总结一下,防止下回跳坑,当然,也是做一个分享,如果有朋友遇到这个错,希望有所...

70620

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励