异常教程

Java 8 中的 Hashmap 性能改进

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2800+ 小伙伴加入学习 ，欢迎点击围观

问题：

在 Java 7 之前， java.util.Hashmap 实现总是遇到哈希冲突问题，即当多个 hashCode() 值最终出现在同一个桶中时，这些值将放在链表实现中，这会降低 Hashmap 的性能 O(1 ) 到 O(n)。

解决方案：

通过使用平衡树而不是链表来存储映射条目，提高 java.util.HashMap 在高散列冲突条件下的性能。这将提高实现 Comparable 任何键类型的冲突性能。

此 JDK 8 更改仅适用于 HashMap 、 LinkedHashMap 和 ConcurrentHashMap 。
主要思想是，一旦哈希桶中的项目数量增长超过某个阈值 ( TREEIFY_THRESHOLD )，该桶将从使用条目链表切换到平衡树。在高散列冲突的情况下，这会将最坏情况下的性能从 O(n) 提高到 O(log n)，并且当它们变得太小时（由于删除或调整大小）它们将转换回链表。 


 static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

另请注意，在极少数情况下，此更改可能会导致 HashMap 和 HashSet 的迭代顺序发生变化。没有为 HashMap 对象指定特定的迭代顺序——任何依赖于迭代顺序的代码都应该是固定的。