JDK1.8以后的hashmap为什么在链表长度为8的时候变为红黑树

  • 作者： 凯哥Java(公众号：凯哥Java)
  • 工作小总结
  • 时间：2021-05-26 20:39
  • 3344人已阅读
工作小总结&小工具类 Redis LoRaWAN&ChirpStack AI编程 AI相关 MQTT Maven mybatis ChatGPT uniapp zookeeper Thymeleaf语法 POI-TL sa-token PowerDesigner16.5 taos数据库 frp echarts Actor模型及Akka thingsboard 大疆无人机对接 CI/CD 教师资格证 小任务 面试其他 职场 淘宝客 支付宝支付 HBuilder X Flink Java集合类 多线程 ES Ribbon eureka Docker java游戏 网络通信 Nacos 芋道管理系统 Solr 分布式相关 Dubbo 数据结构 EasyPOI Drools RocketMQ JS 七天深入MySQL实战营 书籍 kafka spring Java基础 java web 若依(ruoyi) 分布式事务 面试宝典 mysql java8新特性 spring cloud ElasticSearch学习系列 HM_leadnews 即时通讯 并发 思维&学习 VUE 宝塔面板 算法刷题 设计模式 RabbitMQ学习系列教程 P3C规范 JVM学习系列 反射 自定义注解 网络美文 PHP源码 经验分享 资源 git项目 websocket 网赚 数据库读写分离 测试相关 其他随笔 shiro学习系列 fremarker学习系列 学习笔录-spring boot 网络文章 工作小总结
简介 在JDK1.8以及以后的版本中，hashmap的底层结构，由原来单纯的的数组+链表，更改为链表长度为8时，开始由链表转换为红黑树，为何大刀阔斧的对hashmap采取这个改变呢，以及为何链表长度为8才转变为红黑树呢，下面结合源码一起来分析一下。我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的，既然这么棒，那为什么hashmap为什么不直接就

🔔🔔🔔好消息!好消息!🔔🔔🔔

有需要的朋友👉:联系凯哥 微信号 kaigejava2022

在JDK1.8以及以后的版本中，hashmap的底层结构，由原来单纯的的数组+链表，更改为链表长度为8时，开始由链表转换为红黑树，为何大刀阔斧的对hashmap采取这个改变呢，以及为何链表长度为8才转变为红黑树呢，下面结合源码一起来分析一下。

我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的，既然这么棒，那为什么hashmap为什么不直接就用红黑树呢，请看下图：

源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

  那为什么选择8才会选择使用红黑树呢？看下图：

源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。为什么这么说呢，再看下图

在链表转变为红黑树方法中，有这样一个判断，数组长度小于MIN_TREEIFY_CAPACITY，就会扩容，而不是直接转变为红黑树，可不是什么链表长度为8就变为红黑树，要仔细看代码，还有别的条件，

现在回头想想，为啥用8？因为通常情况下，链表长度很难达到8，但是特殊情况下链表长度为8，哈希表容量又很大，造成链表性能很差的时候，只能采用红黑树提高性能，这是一种应对策略。

工作小总结&小工具类 Redis LoRaWAN&ChirpStack AI编程 AI相关 MQTT Maven mybatis ChatGPT uniapp zookeeper Thymeleaf语法 POI-TL sa-token PowerDesigner16.5 taos数据库 frp echarts Actor模型及Akka thingsboard 大疆无人机对接 CI/CD 教师资格证 小任务 面试其他 职场 淘宝客 支付宝支付 HBuilder X Flink Java集合类 多线程 ES Ribbon eureka Docker java游戏 网络通信 Nacos 芋道管理系统 Solr 分布式相关 Dubbo 数据结构 EasyPOI Drools RocketMQ JS 七天深入MySQL实战营 书籍 kafka spring Java基础 java web 若依(ruoyi) 分布式事务 面试宝典 mysql java8新特性 spring cloud ElasticSearch学习系列 HM_leadnews 即时通讯 并发 思维&学习 VUE 宝塔面板 算法刷题 设计模式 RabbitMQ学习系列教程 P3C规范 JVM学习系列 反射 自定义注解 网络美文 PHP源码 经验分享 资源 git项目 websocket 网赚 数据库读写分离 测试相关 其他随笔 shiro学习系列 fremarker学习系列 学习笔录-spring boot 网络文章 工作小总结

上一篇： Java中HashMap底层实现原理(JDK1.8)源码分析

下一篇： 【腾讯云】腾讯云注册后新购或者续费都可以领取佣金了

TopTop