当前位置：首页 > news >正文

深入剖析 HashMap：内部结构与性能优化

news 来源：原创 2025/8/10 3:20:33

深入剖析 HashMap：内部结构与性能优化

引言

HashMap 是 Java 集合框架中的核心类，广泛应用于数据存储和检索场景。本文将深入剖析其内部结构，包括数组、链表和红黑树的转换机制，帮助读者理解其工作原理和性能优化策略。

1. HashMap 的基本结构

1.1 数组（Array）

作用：存储桶（bucket），每个桶可存放一个或多个键值对
初始容量：默认 16，可通过构造函数自定义
扩容机制：当元素数量超过阈值（capacity * loadFactor）时，数组扩容至原大小的两倍

1.2 链表（Linked List）

触发条件：桶中元素数量超过阈值（默认 8）时使用链表存储
特点：
- 插入/删除时间复杂度：O(1)
- 查找时间复杂度：O(n)

1.3 红黑树（Red-Black Tree）

触发条件：
- 链表长度 > 8
- 数组容量 ≥ 64
特点：
- 插入/删除/查找时间复杂度：O(log n)

2. 核心数据结构的使用

2.1 数组的索引计算

index = (n - 1) & hash
n：数组长度（容量）
hash：键的哈希值（通过扰动函数优化分布）

2.2 链表的实现

节点结构：

static class Node<K,V> {final int hash;final K key;V value;Node<K,V> next;
}
/** 后续在 Node<K,V> 使用时被transient修饰， transient是 Java 中的一个关键字，用于修饰类的成员变量。被 transient 修饰的变量表示该变量不会被默认的序列化机制所保存。
作用：阻止某个变量在对象序列化时被写入文件或传输。
使用场景：当某些数据不需要被持久化（如敏感信息、临时数据等），可以使用 transient。*/

2.3 红黑树的实现

节点结构：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;TreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;boolean red;
}

3. 数据结构转换机制

3.1 链表 → 红黑树

条件：

链表长度 > 8

static final int TREEIFY_THRESHOLD = 8;

数组容量 ≥ 64

static final int MIN_TREEIFY_CAPACITY = 64;

转换过程：

// jdk1.8
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize(); // 优先扩容else if ((e = tab[index = (n - 1) & hash]) != null) {// 将链表节点转换为树节点TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null) hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);// 构建红黑树if ((tab[index] = hd) != null) hd.treeify(tab);}
}

3.2 红黑树 → 链表

条件：树节点数量 ≤ 6

static final int UNTREEIFY_THRESHOLD = 6;

转换过程：

// jdk1.8
final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;
}

4. 性能优化策略

4.1 哈希冲突优化

扰动函数：通过二次哈希分散键值对分布

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

4.2 容量设置策略

初始容量：预估存储量，避免频繁扩容
负载因子：默认 0.75，平衡时间与空间成本

4.3 扩容优化

增量迁移：扩容时逐步迁移节点，避免长时间阻塞

5. 总结

结构	触发条件	时间复杂度	适用场景
数组	基础存储结构	O(1) 索引访问	元素均匀分布
链表	桶中元素 ≤ 8	O(n) 查找	少量哈希冲突
红黑树	桶中元素 >8 且容量 ≥64	O(log n) 操作	严重哈希冲突

关键点：

链表转树需同时满足长度和容量条件
树转链表采用更保守的阈值（6）防止频繁转换
合理的初始容量和负载因子可显著提升性能

深入剖析 HashMap：内部结构与性能优化

深入剖析 HashMap：内部结构与性能优化引言 HashMap 是 Java 集合框架中的核心类，广泛应用于数据存储和检索场景。本文将深入剖析其内部结构，包括数组、链表和红黑树的转换机制，帮助读者理解其工作原理和性能优化策略。 1. Hash…...

编程日记 2025/8/10 3:20:33

数据从辅存调入主存，页表中一定存在

在虚拟内存系统中，数据从辅存调入主存时，页表中一定存在对应的页表项，但页表项的「存在状态」会发生变化。以下是详细分析： 关键逻辑页表的作用页表是虚拟内存的核心数据结构，记录了虚拟地址到物理地址的映射关系…...

编程日记 2025/8/10 3:18:37

藏品馆管理系统

藏品馆管理系统项目简介这是一个基于 PHP 开发的藏品馆管理系统，实现了藏品管理、用户管理等功能。藏品馆管理系统系统架构开发语言：PHP数据库：MySQL前端框架：BootstrapJavaScript 库：jQuery 目录结构 book/…...

编程日记 2025/8/10 3:17:41

力扣算法ing(60 / 100)

4.19 回溯合集—93复原ip地址有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 . 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址&…...

编程日记 2025/8/6 18:44:21

时态--06--现在完成時

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录现在完成時1.语法1.肯定句2.否定句3.疑问句4.have been/gone to5.现在分词 practice 现在完成時 1.语法 1.肯定句 2.否定句 3.疑问句 4.have been/gone to 5.现在分…...

编程日记 2025/8/10 3:20:22

Java中常见的锁synchronized、ReentrantLock、ReentrantReadWriteLock、StampedLock

在Java中，锁是实现多线程同步的核心机制。不同的锁适用于不同的场景，理解其实现原理和使用方法对优化性能和避免并发问题至关重要。一、隐式锁：synchronized 关键字实现原理基于对象监视器（Monitor）：每…...

编程日记 2025/8/8 7:05:19

【教程】DVWA靶场渗透

【教程】DVWA靶场渗透备注一、环境搭建二、弱口令（Brute Force）三、命令注入（Command Injection）四、CSRF（Cross Site Request Forgery）五、文件包含（File Inclusion）六、文件上传&…...

编程日记 2025/8/10 3:20:20

23种设计模式-创建型模式之原型模式（Java版本）

Java 原型模式（Prototype Pattern）详解 🧬 什么是原型模式？ 原型模式用于通过复制已有对象的方式创建新对象，而不是通过 new 关键字重新创建。核心是：通过克隆（clone）已有对象&a…...

编程日记 2025/8/6 0:00:36

【深度学习】【目标检测】【Ultralytics-YOLO系列】YOLOV3核心文件common.py解读

【深度学习】【目标检测】【Ultralytics-YOLO系列】YOLOV3核心文件common.py解读文章目录【深度学习】【目标检测】【Ultralytics-YOLO系列】YOLOV3核心文件common.py解读前言autopad函数Conv类__init__成员函数forward成员函数forward_fuse成员函数 Bottleneck类__init__成员…...

编程日记 2025/8/4 22:27:55

PDF转excel+json ，vue3+SpringBoot在线演示+附带源码

在线演示地址：Vite Vuehttp://www.xpclm.online/pdf-h5 源码gitee前后端地址： javapdfexcel: javaPDF转excelhttps://gitee.com/gaiya001/javapdfexcel.git 盖亚/vuepdfhttps://gitee.com/gaiya001/vuepdf.git 后续会推出前端版本跟nestjs版本识别复…...

编程日记 2025/8/10 3:18:40

LeetCode 热题 100_乘积最大子数组（88_152_中等_C++）(动态规划)

LeetCode 热题 100_乘积最大子数组（88_152） 题目描述：输入输出样例：题解：解题思路：思路一（暴力破解法(双重循环)）：思路二（动态规划）： …...

编程日记 2025/8/1 20:40:04

Nvidia显卡架构演进

1 简介显示卡（英语：Display Card）简称显卡，也称图形卡（Graphics Card），是个人电脑上以图形处理器（GPU）为核心的扩展卡，用途是提供中央处理器以外的微处理器帮…...

编程日记 2025/8/4 17:10:41

TCP/IP、UDP、HTTP、HTTPS、WebSocket 一文讲解

在当今互联网世界中，数据通信是所有应用运行的基础。无论是打开网页、发送消息还是视频通话，背后都依赖于各种网络协议的协同工作。其中，TCP/IP、UDP、HTTP、HTTPS 和 WebSocket 是最为核心的几种协议。本文将围绕它们的概念、特性和适用场景…...

编程日记 2025/8/9 22:19:39

[密码学基础]密码学发展简史：从古典艺术到量子安全的演进

密码学发展简史：从古典艺术到量子安全的演进密码学作为信息安全的基石，其发展贯穿人类文明史，从最初的文字游戏到量子时代的数学博弈，每一次变革都深刻影响着政治、军事、科技乃至日常生活。本文将以技术演进为主线，…...

编程日记 2025/7/30 7:33:34

包含物体obj与相机camera的代数几何代码解释

反余弦函数的值域在 [0, pi] 斜体样式 cam_pose self._cameras[hand_realsense].camera.get_model_matrix() # cam2world# 物体到相机的向量 obj_tcp_vec cam_pose[:3, 3] - self.obj_pose.p dist np.linalg.norm(obj_tcp_vec) # 物体位姿的旋转矩阵 obj_rot_mat self.ob…...

编程日记 2025/8/3 13:02:25

【C++算法】65.栈_删除字符中的所有相邻重复项

文章目录题目链接：题目描述：解法C 算法代码： 题目链接： 1047. 删除字符串中的所有相邻重复项题目描述： 解法利用string模拟栈元素依次进栈，当进栈元素和栈顶元素一样的时候，就弹出栈顶字符…...

编程日记 2025/8/4 1:55:58

【java实现+4种变体完整例子】排序算法中【插入排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

以下是插入排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格： 一、插入排序基础实现原理将元素逐个插入到已排序序列的合适位置，逐步构建有序序列。代码示例 public class InsertionSort {void…...

编程日记 2025/8/10 3:20:21

神经网络的数学之旅：从输入到反向传播

目录神经网络简介神经元激活函数神经网络神经网络的工作过程前向传播（forward）反向传播（backward）训练神经网络神经网络简介神经元在深度学习中，必须要说的就是神经⽹络，或者说是⼈⼯神经⽹络&#…...

编程日记 2025/8/10 3:20:32

软件测试的页面交互标准：怎样有效提高易用性

当用户遇到"反人类"设计时 "这个按钮怎么点不了？"、"错误提示完全看不懂"、"我输入的内容去哪了？"——这些用户抱怨背后，都指向同一个问题：页面交互的易用性缺陷。作为软件测试工程师&a…...

编程日记 2025/8/4 8:46:12

Linux419 三次握手四次挥手抓包 wireshark

还是Notfound 没连接可能我在/home 准备配置静态IP vim ctrlr 撤销 u撤销配置成功准备关闭防火墙准备配置 YUM源 df -h 未看到sr0文件准备排查准备挂载还是没连接计划重启有了不重启了挂载准备修改配置文件准备准备清理缓存 ok 重新修改配…...

编程日记 2025/8/9 6:32:20

玩转Docker | 使用Docker部署tududi任务管理工具

玩转Docker | 使用Docker部署tududi任务管理工具前言一、tududi介绍Tududi简介核心功能特点二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署tududi服务下载镜像创建容器创建容器检查容器状态检查服务端口安全设置四、访问tududi服务访问tududi首页登录tu…...

编程日记 2025/8/5 4:43:29

ueditorplus编辑器已增加AI智能

之前功能请参考：https://www.geh3408.top/blog/76 下载：https://gitee.com/mo3408/ueditorplus 注意：key值需要单独获取，默认为DeepSeek，默认key有限制，请更换为自己的。演示地址：https://www.geh3408.top/ueditorplus/dist 更多体验：ueditorplus编辑器已增加AI智…...

编程日记 2025/8/6 1:34:27

深度学习数据预处理：Dataset类的全面解析与实战指南

前言在深度学习项目中，数据预处理是模型训练前至关重要的一环。一个高效、灵活的数据预处理流程不仅能提升模型性能，还能大大加快开发效率。本文将深入探讨PyTorch中的Dataset类，介绍数据预处理的常见技巧，并通过实战示例展示如何…...

编程日记 2025/8/6 9:15:38

【机器学习-周总结】-第4周

以下是本周学习内容的整理总结，从技术学习、实战应用到科研辅助技能三个方面归纳： 文章目录 📘 一、技术学习模块：TCN 基础知识与结构理解🔹 博客1：【时序预测05】– TCN（Temporal Convolutiona…...

编程日记 2025/8/8 16:51:12

高可靠 ZIP 压缩方案兼容 Office、PDF、TXT 和图片的二阶段回退机制

一、引言在企业级应用中，经常需要将多种类型的文件（如 Office 文档、PDF、纯文本、图片等）打包成 ZIP 并提供给用户下载。但由于文件路径过长、特殊字符或权限等问题，Go 标准库的 archive/zip 有时会出现“压缩成功却实际未写入…...

编程日记 2025/8/7 3:47:13

【HDFS入门】HDFS数据冗余与容错机制解析：如何保障大数据高可靠存储？

目录 1 HDFS冗余机制设计哲学 1.1 多副本存储策略的工程权衡 1.2 机架感知的智能拓扑算法 2 容错机制实现原理 2.1 故障检测的三重保障 2.2 数据恢复的智能调度 3 关键场景容错分析 3.1 数据中心级故障应对 3.2 数据损坏的校验机制 4 进阶优化方案 4.1 纠删码技术实…...

编程日记 2025/8/8 6:24:21

06-libVLC的视频播放器：推流RTMP

创建媒体对象 libvlc_media_t* m = libvlc_media_new_path(m_pInstance, inputPath.toStdString().c_str()); if (!m) return -1; // 创建失败返回错误 libvlc_media_new_path：根据文件路径创建媒体对象。注意：toStdString().c_str() 在Qt中可能存在临时字符串析构问题，建议…...

编程日记 2025/8/7 12:45:58

【DT】USB通讯失败记录

项目场景： DT小板 USB通讯失败问题描述 V1.1 板子含有降压电路、电容充电电路、姿态传感电路，语音电路、电弧电路、TF卡电路焊接完成：功能正常 V1.2 为方便数传模块拔插，把座子缩小并做在了背面，下载口反向方便狭…...

编程日记 2025/8/8 1:42:58

【笔记】网路安全管理-实操

一、系统安全防护-Windows 开始-》管理工具-》本地安全策略-》账户策略-》密码策略-》 1.密码必须符合复杂性要求。双击打开-》勾选已启用-》单击：应用-》单击：确定 2.密码长度最小值。双击打开-》设置密码长度最小值为：？个字符 3.密码最短使用期限。双击打开-》设置密码…...

编程日记 2025/7/30 14:03:03

FFMPEG-视频解码-支持rtsp|rtmp|音视频文件（低延迟）

本人亲测解码显示对比延迟达到7到20毫秒之间浮动兼容播放音视频文件、拉流RTSP、RTMP等网络流基于 Qt 和 FFmpeg 的视频解码播放器类，继承自 QThread，实现了视频流的解码、播放控制、帧同步和错误恢复等功能工作流程初始化阶段: 用户设置URL和显示尺寸调用play()启动线程解…...

编程日记 2025/8/9 8:09:48

LDR、MOV和STR指令详解

文章目录前言一、LDR指令详解 1.基本语法 2.寻址方式 3.伪指令形式二、MOV指令详解 1.基本语法 2.常见用法 3.特殊变体三、STR指令详解 1.基本语法 2.寻址方式四、三者区别与联系 1.基本语法 2.操作效率 3.大数值处理总结前言 ARM汇编中的LDR、MOV和STR是三个最基础也最…...

编程日记 2025/8/8 4:40:43

MATLAB 控制系统设计与仿真 - 41

鲁棒控制的其他函数 - 回路成型函数 loopsyn 灵敏度问题由鲁棒控制工具箱中的loopsyn就可以直接求解，该函数采用H无穷回路成型算法设计控制器，函数的调用格式为： [K,CL,gamma,info] loopsyn(G,Gd) % G为受控对象模型% Gd为期望的回路传递函…...

编程日记 2025/8/6 13:24:41

Scade 语言词法介绍

Scade 6 是一种具备形式化语法与形式化语义的领域特定语言（注1）。自2008年发布（注5）起，在 Scade Suite 产品系列中语言定义方面到目前未产生重要的改变(注2)。在下面的内容中将介绍Scade 语言的词法(注3)。注1&#x…...

编程日记 2025/7/30 15:25:17

Replicate Python client

本文翻译整理自：https://github.com/replicate/replicate-python 文章目录一、关于 Replicate Python 客户端相关链接资源关键功能特性二、1.0.0 版本的重大变更三、安装与配置1、系统要求2、安装3、认证配置四、核心功能1、运行模型2、异步IO支持3、流式输出模型…...

编程日记 2025/8/9 20:35:46

LLM做逻辑推理题 - 如何找出不标准的球？

题目: 有80个外观一致的小球，其中一个和其它的重量不同，（不知道更轻还是更重）。现在给你一个天平，允许你称四次，把重量不同的球找出来，怎么称？ 1. 答案第1次称量：天平…...

编程日记 2025/8/3 1:55:11

[密码学基础]国密算法深度解析：中国密码标准的自主化之路

国密算法深度解析：中国密码标准的自主化之路国密算法（SM系列算法）是中国自主研发的密码技术标准体系，旨在打破国际密码技术垄断，保障国家信息安全。本文将从技术原理、应用场景和生态发展三个维度，全面解…...

编程日记 2025/8/6 9:34:34

【计算机视觉】三维视觉项目 - Colmap二维图像重建三维场景

COLMAP 3D重建项目概述项目功能项目运行方式1. 环境准备2. 编译 COLMAP3. 数据准备4. 运行 COLMAP 常见问题及解决方法1. **编译问题**2. **运行问题**3. **数据问题** 项目实战建议项目参考文献项目概述 COLMAP 是一个开源的三维重建软件，专注于 Structure-from…...

编程日记 2025/8/7 23:26:28

基于Fabric.js的选座布局系统开发笔记

项目概述最近开发了一个简单的选座布局系统，主要用于会议、活动或餐厅等场景的座位和桌子布局设计。系统基于HTML5 Canvas和Fabric.js库实现，支持添加座位、桌子，并能保存布局数据。技术栈 • HTML5 Canvas：作为绘图的基础 •…...

编程日记 2025/8/8 1:21:16

PHP怎样连接MySQL数据库？

方法一：使用 mysqli 扩展 mysqli 是 MySQL 的改进版扩展，提供了面向对象和过程化的接口。面向对象风格 <?php$servername "localhost"; $username "your_username"; $password "your_password"; $dbname &quo…...

编程日记 2025/8/5 1:33:53

将飞帆制作的网页作为 Vue 2 组件引入到自己网页中使用

飞帆平台有一个功能：不仅所有的网页都是通过控件搭建而成，而且生成的网页又是一个大控件，可以导入到你自己的网页使用。这篇文章，我们要讲的就是如何将飞帆生成的网页作为控件（组件）导入到自己的网页中。…...

编程日记 2025/7/30 15:25:03

Python制作简易PDF查看工具PDFViewerV1.0显示优化

原文说明为不破坏原文结构，因此功能优化不在原文中维护了。关于这款工具原文请通过下面链接访问。Python制作简易PDF查看工具PDFViewerV1.0 这款小工具基本功能已经可以作为一款文档浏览器使用，但还有一些美中不足的地方，本文将介绍对文本查找功能的优化调整。优化效果 …...

编程日记 2025/8/7 11:49:16

YOLOv11改进有效涨点专栏：从理论到实战的深度优化指南

## YOLOv11的进化之路在目标检测领域，YOLO系列算法始终保持着革命性的创新步伐。YOLOv11作为该系列的最新演进版本，在保持实时检测优势的同时，通过架构层面的深度优化实现了精度与速度的平衡。本文将从**七大核心模块**出发，系统性地解析针对YOLOv11的有效改进方案，涵盖从…...

编程日记 2025/8/5 8:37:21

【EDA软件】【设计约束和分析操作方法】

1. 设计约束设计约束主要分为物理约束和时序约束。物理约束主要包括I/O接口约束（如引脚分配、电平标准设定等物理属性的约束）、布局约束、布线约束以及配置约束。时序约束是FPGA内部的各种逻辑或走线的延时，反应系统的频率和速度的约束…...

编程日记 2025/8/4 10:38:28

JVM基础认知：JVM到底是什么？为什么它如此重要？

随着 Java 语言在企业级应用、互联网服务、嵌入式系统等领域的广泛采用，JVM（Java Virtual Machine，Java虚拟机）成为了支撑整个生态的核心基础。初学者往往会把注意力集中在 Java 代码本身，却忽视了背后那台“看不见的机…...

编程日记 2025/8/9 18:02:51

javassist

使用javassist获取参数名 1，添加依赖需要在pom.xml文件中添加下面的依赖： <dependency><groupId>org.javassist</groupId><artifactId>javassist</artifactId><version>3.28.0-GA</version> </depende…...

编程日记 2025/8/2 23:10:16

【C++算法】66.栈_比较含退格的字符串

文章目录题目链接：题目描述：解法C 算法代码： 题目链接： 844. 比较含退格的字符串题目描述： 解法用字符串来模拟栈。 C 算法代码： class Solution { public:bool backspaceCompare(string s, string t…...

编程日记 2025/8/10 1:41:13

游戏引擎学习第235天:在 Windows 上初始化 OpenGL

奇怪有问题之前没注意到这个问题是Count 0 GlobalConstants_Renderer_UsedDebugCamer 打开的话会有Bug Count是零的话就不让排序了 game.h: 查阅 TODO 列表大家好，欢迎来到 game Hero，这是一档我们在直播中一起编写完整游戏的节目。不幸的是&a…...

编程日记 2025/8/7 11:42:26

FPGA系列之DDS信号发生器设计（DE2-115开发板）

一、IP核 IP(Intellectual Property)原指知识产权、著作权等，在IC设计领域通常被理解为实现某种功能的设计。IP模块则是完成某种比较复杂算法或功能（如FIR滤波器、FFT、SDRAM控制器、PCIe接口、CPU核等）并且参数可修改的电路模块&#xff0c…...

编程日记 2025/8/4 1:42:16

修改Theme SHELL美化panel

安装使用使用Tweaks进行设置需要创建.themes文件夹，在当前目录下 mkdir ~/.themes从官网下载文件 https://www.gnome-look.org/p/1013030 将打包压缩文件移动到~/themes，并解压 tar -xvf 01-Flat-Remix-Light-20250413.tar.xz然后使用按 Alt F2…...

编程日记 2025/8/8 4:23:58

Sentinel源码—5.FlowSlot借鉴Guava的限流算法二

大纲 1.Guava提供的RateLimiter限流使用示例 2.Guava提供的RateLimiter简介与设计 3.继承RateLimiter的SmoothBursty源码 4.继承RateLimiter的SmoothWarmingUp源码 3.继承RateLimiter的SmoothBursty源码 (1)SmoothBursty的初始化流程 (2)SmoothBursty的初始化完成后的变量…...

编程日记 2025/7/30 15:24:40

深入剖析 HashMap：内部结构与性能优化

引言

1. HashMap 的基本结构

1.1 数组（Array）

1.2 链表（Linked List）

1.3 红黑树（Red-Black Tree）

2. 核心数据结构的使用

2.1 数组的索引计算

2.2 链表的实现

2.3 红黑树的实现

3. 数据结构转换机制

3.1 链表 → 红黑树

3.2 红黑树 → 链表

4. 性能优化策略

4.1 哈希冲突优化

4.2 容量设置策略

4.3 扩容优化

5. 总结

相关文章：