前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HashMap 在 JDK1.7 和 JDK1.8 的区别

HashMap 在 JDK1.7 和 JDK1.8 的区别

作者头像
Li_XiaoJin
发布2022-06-10 20:20:58
8500
发布2022-06-10 20:20:58
举报
文章被收录于专栏:Lixj's BlogLixj's Blog

遇到的一个问题,之前没有好好思考过这个问题,现在研究一下

区别

  1. 最重要的一点是底层结构不一样,1.7是数组+链表,1.8则是数组+链表+红黑树结构;
  2. jdk1.7中当哈希表为空时,会先调用inflateTable()初始化一个数组;而1.8则是直接调用resize()扩容;
  3. 插入键值对的put方法的区别,1.8中会将节点插入到链表尾部,而1.7中是采用头插; 1.7采用头插法,会引发环形链表死循环;1.8采用尾插法;
  4. jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值,而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果,避免了只靠低位数据来计算哈希时导致的冲突,计算结果由高低位结合决定,使元素分布更均匀;
  5. 扩容时1.8会保持原链表的顺序,而1.7会颠倒链表的顺序;而且1.8是在元素插入后检测是否需要扩容,1.7则是在元素插入前;
  6. jdk1.8是扩容时通过hash&cap==0将链表分散,无需改变hash值,而1.7是通过更新hashSeed来修改hash值达到分散的目的;
  7. 扩容策略:1.7中是只要不小于阈值就直接扩容2倍;而1.8的扩容策略会更优化,当数组容量未达到64时,以2倍进行扩容,超过64之后若桶中元素个数不小于7就将链表转换为红黑树,但如果红黑树中的元素个数小于6就会还原为链表,当红黑树中元素不小于32的时候才会再次扩容。

关于红黑树相关知识:https://www.jianshu.com/p/e136ec79235c

JDK8中HashMap链表转红黑树的阈值为什么选8?为什么用红黑树做优化?

为什么会引入红黑树做查询优化呢?

在平常我们用HashMap的时候,HashMap里面存储的key是具有良好的hash算法的key(比如String、Integer等包装类),冲突几率自然微乎其微,此时链表几乎不会转化为红黑树,但是当key为我们自定义的对象时,我们可能采用了不好的hash算法,使HashMap中key的冲突率极高,但是这时 HashMap为了保证高速的查找效率,就引入了红黑树来优化查询了。

为什么树化的临界值为8?

源码中的介绍如下:

通过源码我们得知 HashMap源码作者通过泊松分布算出,当桶中结点个数为8时,出现的几率是亿分之6的,因此常见的情况是桶中个数小于8的情况,此时链表的查询性能和红黑树相差不多,因为转化为树还需要时间和空间,所以此时没有转化成树的必要。

既然个数为8时发生的几率这么低,我们为什么还要当链表个数大于8时来树化来优化这几乎不会发生的场景呢?

首先我们要知道亿分之6这个几乎不可能的概率是建立在什么情况下的 答案是:建立在良好的hash算法情况下,例如String,Integer等包装类的hash算法、如果一旦发生桶中元素大于8,说明是不正常情况,可能采用了冲突较大的hash算法,此时桶中个数出现超过8的概率是非常大的,可能有n个key冲突在同一个桶中,此时再看链表的平均查询复杂度和红黑树的时间复杂度,就知道为什么要引入红黑树了,

举个例子,若hash算法写的不好,一个桶中冲突1024个key,使用链表平均需要查询512次,但是红黑树仅仅10次, 红黑树的引入保证了在大量hash冲突的情况下,HashMap还具有良好的查询性能

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可 Links: https://lixj.fun/archives/hashmap在jdk7和jdk8的区别

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-07-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 区别
  • JDK8中HashMap链表转红黑树的阈值为什么选8?为什么用红黑树做优化?
    • 为什么会引入红黑树做查询优化呢?
      • 为什么树化的临界值为8?
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档