JAVA:HashMap在1.8做了哪些优化的详细解析
1、简述
HashMap 是 Java 中最常用的数据结构之一,它以键值对的形式存储数据,允许快速的插入、删除和查找操作。在 JDK 1.8 之前,HashMap 主要是基于数组加链表的结构实现的。然而,在面对大量哈希冲突时(即多个键的哈希值相同时),链表可能会变得非常长,导致查询效率从 O(1) 退化为 O(n)。为了优化这种情况,JDK 1.8 对 HashMap 进行了几个重要的改进,主要包括引入红黑树(Red-Black Tree)和哈希算法的改进。本文将详细讲解这些优化及其背后的设计思路。

2、JDK 1.8 之前的 HashMap 实现
在 JDK 1.8 之前,HashMap 使用数组和链表的组合结构。当我们插入一个元素时,它首先通过键的哈希值确定数组中的位置(称为桶),如果该位置存在其他元素,新的键值对将被追加到该位置的链表上。
这种结构的优点是简单易实现,且在键分布均匀的情况下性能很好。但在极端情况下,如果大量的键映射到了同一个位置(哈希冲突),链表的长度会增长,查询时间复杂度会从 O(1) 退化到 O(n),这对性能影响较大。

3、JDK 1.8 对 HashMap 的优化
3.1 引入红黑树(Red-Black Tree)
为了优化链表查询的效率,JDK 1.8 引入了红黑树。当链表的长度超过一定阈值(默认是 8)时,链表会自动转换为红黑树。红黑树是一种自平衡二叉搜索树,查找、插入、删除操作的时间复杂度为 O(log n),因此大幅提升了查询性能。
当链表中的元素少于一定数量(默认是 6)时,红黑树会被转换回链表。这种转换机制在哈希冲突较严重时显著提升了 HashMap 的性能,同时也保证了在数据量较少时的内存开销不会过高。
// HashMap 中的链表转红黑树逻辑示例
if (binCount >= TREEIFY_THRESHOLD) {treeifyBin(tab, hash);
}
- TREEIFY_THRESHOLD:定义了链表转化为红黑树的阈值,默认值为 8。
- treeifyBin:负责将链表转化为红黑树。
3.2 动态扩容优化
HashMap 的容量是动态扩展的,当哈希表中的元素数量超过当前容量的 75% 时,会触发扩容操作。在 JDK 1.8 之前,扩容需要重新计算每个键的哈希值并分配到新的位置。JDK 1.8 优化了扩容逻辑,通过更高效的方式重新分配元素。
扩容时,原数组长度翻倍,每个元素要么保持在原位置,要么移动到新的索引位置。通过与新的容量进行简单的按位与运算,JDK 1.8 能快速确定元素在新数组中的位置,从而避免重新计算哈希值,提升了扩容的效率。
// HashMap 扩容时的元素迁移逻辑
int idx = e.hash & (newCapacity - 1);
3.3 改进的哈希算法
在 JDK 1.8 中,HashMap 采用了更好的哈希扰动函数(hash function),目的是减少哈希冲突的发生。通过对哈希值进行一系列位运算,使得高位和低位都能影响最终的数组索引,减少了低质量哈希函数带来的冲突问题。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这一优化主要是通过异或操作,将高位和低位的信息混合在一起,以提高哈希值的随机性,进而降低哈希冲突的概率。
4、优化的性能影响
JDK 1.8 的这些改进显著提升了 HashMap 在大数据量、高冲突场景下的性能:
- 在链表转换为红黑树后,查找性能从 O(n) 提升为 O(log n),尤其在高冲突情况下,性能提升明显。
- 动态扩容时避免了重复计算哈希值,扩容效率得到了提升。
- 改进的哈希算法进一步减少了哈希冲突的概率,提高了哈希表的整体性能。
以下是一个简单的示例代码,展示了 HashMap 在 JDK 1.8 中的工作机制:
import java.util.HashMap;public class HashMapDemo {public static void main(String[] args) {HashMap<String, Integer> map = new HashMap<>();// 插入元素,触发红黑树转换for (int i = 0; i < 20; i++) {map.put("key" + i, i);}// 输出 HashMap 内容map.forEach((key, value) -> System.out.println(key + ": " + value));// 扩容前后检查性能System.out.println("Size before expansion: " + map.size());for (int i = 20; i < 50; i++) {map.put("key" + i, i);}System.out.println("Size after expansion: " + map.size());}
}
5、总结
JDK 1.8 对 HashMap 的优化主要集中在两个方面:提高哈希冲突情况下的查找效率和优化扩容过程。通过引入红黑树结构,HashMap 能够在面对大量哈希冲突时依然保持高效的查询性能;而动态扩容的优化则减少了不必要的哈希值重计算操作。这些优化使得 HashMap 在 JDK 1.8 中性能更加稳定和高效,特别是在大数据量的高并发环境中,表现尤为出色。
这也是为什么在性能敏感的系统中,升级到 JDK 1.8 后 HashMap 的表现更加优越的原因。希望这篇文章能帮助你更好地理解这些优化的实现原理,并在实际开发中加以应用。
相关文章:
JAVA:HashMap在1.8做了哪些优化的详细解析
1、简述 HashMap 是 Java 中最常用的数据结构之一,它以键值对的形式存储数据,允许快速的插入、删除和查找操作。在 JDK 1.8 之前,HashMap 主要是基于数组加链表的结构实现的。然而,在面对大量哈希冲突时(即多个键的哈…...
jest使用__mocks__设置模拟函数不生效 解决方案
模拟文件 // __mocks__/axios.js const axios jest.fn(); axios.get jest.fn(); axios.get.mockResolvedValue({data: {undoList: [get data],}, }); export default axios; 测试文件 jest.mock(axios); import Axios from axios;test(mytest, () > {console.log("…...
javaEE-网络原理-1初识
目录 一.网络发展史 1.独立模式 2.网络互联 二.局域网LAN 1.基于网线直连: 2.基于集线器组件: 3.基于交换机组件: 4.基于交换机和路由器组件 编辑 三、广域网WAN 四、网络通信基础 1.ip地址 2.端口号: 3.协议 4.五…...
笔上云世界微服务版
目录 一、项目背景 二、项目功能 一功能介绍 三、环境准备 • 需要开发的端口 • Mysql 导入数据库 编辑 • Redis 编辑 • RabbitMQ 编辑 在创建blog虚拟主机(方法如下) • Nacos • Nginx 四、前端部署 五、后端部署 六、测试计划操作 一功能测试 二…...
linux安装redis及Python操作redis
目录 一、Redis安装 1、下载安装包 2、解压文件 3、迁移文件夹 4、编译 5、管理redis文件 6、修改配置文件 7、启动Redis 8、将redis服务交给systemd管理 二、Redis介绍 1、数据结构 ①字符串String ②列表List ③哈希Hash ④集合Set ⑤有序集合Sorted Set 2、…...
node.js内置模块之---stream 模块
stream 模块的作用 在 Node.js 中,stream 模块是一个用于处理流(stream)的核心模块。流是一种处理数据的抽象方式,允许程序处理大量数据时不会一次性将所有数据加载到内存中,从而提高性能和内存效率。通过流࿰…...
《learn_the_architecture_-_aarch64_exception_model》学习笔记
1.当发生异常时,异常级别可以增加或保持不变,永远无法通过异常来转移到较低的权限级别。从异常返回时,异常级别可能会降低或保持不变,永远无法通过从异常返回来移动到更高的权限级别。EL0级不进行异常处理,异常必须在比…...
【C++项目实战】贪吃蛇小游戏
一、引言 贪吃蛇,这款经典的电子游戏,自1976年诞生以来,一直受到全球玩家的喜爱。它的规则简单,玩法直观,但同时也充满了挑战性。在这篇文章中,我们将一起探索如何开发一个贪吃蛇游戏,无论是作为…...
Python基于matplotlib实现树形图的绘制
在Python中,你可以使用matplotlib库来绘制树形图(Tree Diagram)。虽然matplotlib本身没有专门的树形图绘制函数,但你可以通过组合不同的图形元素(如线条和文本)来实现这一点。 以下是一个简单的示例&#…...
【UE5 C++课程系列笔记】21——弱指针的简单使用
目录 概念 声明和初始化 转换为共享指针 打破循环引用 弱指针使用警告 概念 在UE C 中,弱指针(TWeakPtr )也是一种智能指针类型,主要用于解决循环引用问题以及在不需要强引用保证对象始终有效的场景下,提供一种可…...
【游戏设计原理】46 - 魔杖
幻想,人们可以通过多种形式来引发,比如文字,图片,绘画,语言等,但游戏与以上这些形式的区别,正如游戏与其他艺术形式的区别一样,游戏作为一种艺术和娱乐形式,其独特之处在…...
【路径跟踪】PIDMPC
路径跟踪(Path Tracking)是指在实际行驶过程中,根据预先规划好的路径进行控制,能够沿着设定的路径行驶。常见的路径跟踪算法包括基于模型的控制方法(如PID控制器)、模型预测控制(Model Predicti…...
Spring源码分析之事件机制——观察者模式(二)
目录 获取监听器的入口方法 实际检索监听器的核心方法 监听器类型检查方法 监听器的注册过程 监听器的存储结构 过程总结 Spring源码分析之事件机制——观察者模式(一)-CSDN博客 Spring源码分析之事件机制——观察者模式(二ÿ…...
热备份路由HSRP及配置案例
✍作者:柒烨带你飞 💪格言:生活的情况越艰难,我越感到自己更坚强;我这个人走得很慢,但我从不后退。 📜系列专栏:网路安全入门系列 目录 一,HSRP的相关概念二,…...
仿生的群体智能算法总结之三(十种)
群体智能算法是一类通过模拟自然界中的群体行为来解决复杂优化问题的方法。以下是30种常见的群体智能算法,本文汇总第21-30种。接上文 : 编号 算法名称(英文) 算法名称(中文) 年份 作者 1 Ant Colony Optimization (ACO) 蚁群优化算法 1991 Marco Dorigo 2 Particle Swar…...
CentOS 7系统 OpenSSH和OpenSSL版本升级指南
文章目录 CentOS 7系统 OpenSSH和OpenSSL版本升级指南环境说明当前系统版本当前组件版本 现存安全漏洞升级目标版本升级准备工作OpenSSL升级步骤1. 下载和解压2. 编译安装3. 配置环境 OpenSSH升级步骤1. 下载和解压2. 编译安装3. 创建systemd服务配置4. 更新SSH配置文件5. 设置…...
【专题】2024年出口跨境电商促销趋势白皮书报告汇总PDF洞察(附原数据表)
原文链接:https://tecdat.cn/?p38722 在当今全球化加速演进、数字经济蓬勃发展的大背景下,跨境电商行业正以前所未有的态势重塑国际贸易格局,成为各方瞩目的焦点领域。 根据亚马逊发布的《2024年出口跨境电商促销趋势白皮书》,…...
【Ubuntu】不能连上网络
1. ping路由器的IP地址 ping 192.168.1.1 如果ping不通的话,可能是网络故障导致的。需要重启配置ip地址。配置文件 sudo vi /etc/network/interface 2. ping 8.8.8.8 如果ping不通的话,可能是路由器不能链接往外网; 或者路由器显示了当…...
CSS3 框大小
CSS3 框大小 CSS3 是网页设计和开发中不可或缺的一部分,它为开发者提供了更多样化、更灵活的样式和布局选择。在 CSS3 中,框大小(Box Sizing)是一个重要的概念,它决定了元素内容的宽度和高度以及元素整体的大小。本文将详细介绍 CSS3 框大小的概念、用法以及最佳实践。 …...
联发科MTK6771/MT6771安卓核心板规格参数介绍
MT6771,也被称为Helio P60,是联发科技(MediaTek)推出的一款中央处理器(CPU)芯片,可运行 android9.0 操作系统的 4G AI 安卓智能模块。MT6771芯片采用了12纳米工艺制造,拥有八个ARM Cortex-A73和Cortex-A53核心,主频分别…...
NelmioApiDocBundle集成指南:与JMS Serializer、FOSRestBundle完美协作
NelmioApiDocBundle集成指南:与JMS Serializer、FOSRestBundle完美协作 【免费下载链接】NelmioApiDocBundle Generates documentation for your REST API from attributes 项目地址: https://gitcode.com/gh_mirrors/ne/NelmioApiDocBundle NelmioApiDocBun…...
滴水逆向 Day05:函数嵌套调用的内存布局(图文版)
0基础小白学逆向记录贴,一起来学逆向。https://mp.weixin.qq.com/s/EPDY6i2-R-WQI101KTJvtg 一、核心目标:搞懂一个函数调用另一个函数时,栈空间是怎么变化的、参数怎么传递、返回值怎么回来、ebp/esp 到底在干什么。 二、示例代码࿰…...
【AGI环境监测革命】:3大颠覆性应用、7类实时预警场景与2025碳中和落地路径
第一章:AGI驱动的环境监测范式跃迁 2026奇点智能技术大会(https://ml-summit.org) 传统环境监测长期受限于传感器密度、数据孤岛与响应滞后性,而具备自主推理、多模态融合与跨域协同能力的通用人工智能(AGI)正从根本上重构这一技…...
告别龟速下载!Hugging Face预训练模型(BERT/RoBERTa)手动下载与本地加载保姆级教程
突破网络限制:Hugging Face模型高效下载与本地化实战指南 1. 为什么我们需要离线加载Hugging Face模型? 国内开发者在尝试使用Hugging Face的预训练模型时,经常会遇到下载速度极慢甚至完全无法连接的问题。这种情况在高校网络环境或某些特定…...
云端全自动AI漫剧生成工作流:从模型选型到完整实现
云端全自动AI漫剧生成工作流:从模型选型到完整实现 一、绪论 1.1 漫剧产业的AI化浪潮 漫剧作为“文字故事+静态漫画+动态效果”的新型内容形态,凭借低制作成本、高传播效率的优势,正迅速成为短视频平台的流量新风口。然而,传统漫剧生产流程高度依赖人工协作——从剧本改…...
鲜枣去核机(论文 CAD图纸)
鲜枣去核作业长期依赖人工操作,不仅效率低下,还易因操作疲劳导致果肉损伤,影响产品品质。鲜枣去核机的出现,为这一环节提供了高效解决方案。其核心作用在于通过机械结构精准定位枣核位置,利用特定刀具快速分离果核与果…...
Wan2.2-I2V-A14B与Dify集成:打造无需编码的AI视频工作流
Wan2.2-I2V-A14B与Dify集成:打造无需编码的AI视频工作流 1. 引言:让业务人员也能玩转AI视频生成 想象一下这样的场景:电商运营团队需要为上千款商品制作短视频,传统方式需要设计师逐一手动制作,耗时耗力。而现在&…...
Sunshine游戏串流终极指南:从零开始搭建自托管游戏主机
Sunshine游戏串流终极指南:从零开始搭建自托管游戏主机 【免费下载链接】Sunshine Self-hosted game stream host for Moonlight. 项目地址: https://gitcode.com/GitHub_Trending/su/Sunshine 想要在任何设备上流畅玩PC游戏,但厌倦了云游戏服务的…...
Orwell Dev-C++和Embarcadero Dev-C++哪个更轻量
在选择轻量级的开发环境时,Orwell Dev-C和Embarcadero Dev-C都是基于经典Dev-C的衍生版本,但二者的轻量化程度存在差异:1. 安装包体积Orwell Dev-C:安装包约50MB,保留了核心编译和基础调试功能。Embarcadero Dev-C&…...
从‘有状态’到实战:用iptables为你的Ubuntu服务器打造企业级安全策略
从‘有状态’到实战:用iptables为你的Ubuntu服务器打造企业级安全策略 在当今数字化时代,服务器安全已成为企业IT基础设施的重中之重。想象一下,你的Ubuntu服务器上运行着关键的Web应用和数据库服务,每天处理着成千上万的请求——…...
