HashMap 源码深度解析JDK 1.8 中数组 链表 红黑树的底层实现原理【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址: https://gitcode.com/doocs/source-code-hunter本文基于本仓库 HashMap 源码赏析 一文对 JDK 1.8 中 HashMap 的底层数据结构、核心字段、put/get/resize 三大主流程以及红黑树原理进行源码级剖析。HashMap 是 Java 开发中最常用、最重要的容器之一读懂它的设计不仅有助于写出更高效的代码也能为理解 LinkedHashMap、HashSet、ConcurrentHashMap 等兄弟集合打下坚实基础。读完本文你将掌握 HashMap 的哈希定位、尾插法、链表转红黑树阈值、两倍扩容与高低位拆分等关键机制并能据此对初始容量等参数做出合理配置。一、整体认知HashMap 的底层数据结构JDK 1.8 的 HashMap 底层使用的是动态数组数组中每个元素存放的是链表或红黑树即经典的「数组 链表 红黑树」结构核心源码位于 JDK 1.8 的java.util.HashMap。这种设计要解决的核心问题是哈希冲突多个不同 key 经过哈希计算后可能映射到数组的同一个下标位置此时便在该下标处以链表或红黑树的方式把冲突的键值对串起来。而当某个桶位上的链表过长时查询效率会退化为 O(N)因此 JDK 1.8 引入了红黑树作为链表的升级形态。public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable, Serializable { // ... transient NodeK,V[] table; // Node数组实际存放键值对的地方 }二、核心常量与字段一把钥匙打开 HashMapHashMap 的设计精髓首先体现在一组精心挑选的常量与字段上。理解它们的含义与取值依据是读懂后续所有流程的前提。常量 / 字段默认值作用说明DEFAULT_INITIAL_CAPACITY1 416初始化容量使用位运算定义1 4即 16MAXIMUM_CAPACITY1 30最大容量约 10.7 亿DEFAULT_LOAD_FACTOR0.75f扩容因子已使用容量达到当前容量的 75% 时触发扩容threshold随容量变化当前 HashMap 所能容纳键值对数量的最大值容量 × 负载因子超过则扩容size0已使用的容量实际键值对数量tablenullNode 数组真正存放键值对的地方TREEIFY_THRESHOLD8链表转红黑树的阈值链表长度达到此值时进化成红黑树为什么初始容量选 16、负载因子选 0.75容量必须是2 的幂这是为了能用(n - 1) hash位运算代替取模运算来计算下标下文会展开1 4 16是经验上兼顾空间与冲突概率的起始值负载因子0.75f是空间利用率与查询效率的折中过小会导致频繁扩容浪费空间过大会让哈希冲突概率上升、链表变长。tableSizeFor构造方法里隐藏的位运算在带参构造方法中传入的initialCapacity并不会直接作为数组容量而是经过tableSizeFor处理得到一个大于等于传入值的最小 2 的幂public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity 0) throw new IllegalArgumentException(Illegal initial capacity: initialCapacity); if (initialCapacity MAXIMUM_CAPACITY) initialCapacity MAXIMUM_CAPACITY; if (loadFactor 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Illegal load factor: loadFactor); this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity); }这里有一个细节值得注意初始化时threshold被临时用来保存tableSizeFor的计算结果。也就是说在真正创建桶数组之前threshold变量暂存的是规格化后的初始容量待到首次resize()时才正式转换为阈值容量 × 负载因子。HashMap 提供了四个构造方法覆盖了绝大多数使用场景public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map? extends K, ? extends V m) { this.loadFactor DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }实战建议推荐在初始化时根据实际情况设置好初始容量。比如你确定要存放 1000 个键值对负载因子按 0.75 计算直接new HashMap(1000 / 0.75f 1)或更大一些的 2 的幂可以显著减少 resize 次数、提升效率。仓库中 HashSet 的带集合构造方法 也采用了同样的思路new HashMap(Math.max((int) (c.size()/.75f) 1, 16))。三、put 流程从哈希定位到链表尾插与树化put方法本身只有一行真正的逻辑全部封装在putVal中public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }putVal的完整流程可以分为四个阶段源码与注释如下final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; // 初始化桶数组 tabletable 被延迟到插入新数据时再进行初始化 if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 如果桶中不包含键值对节点引用则将新键值对节点的引用存入桶中即可 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时则将 e 指向该键值对 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; // 如果桶中的引用类型为 TreeNode则调用红黑树的插入方法 else if (p instanceof TreeNode) e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 对链表进行遍历并统计链表长度 for (int binCount 0; ; binCount) { // 链表中不包含要插入的键值对节点时则将该节点接在链表的最后 // JDK1.7中新增的Node节点采用头插入而JDK1.8中改成了尾插入 if ((e p.next) null) { p.next newNode(hash, key, value, null); // 如果链表长度达到阈值则进化成红黑树 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 条件为 true表示当前链表包含要插入的键值对终止遍历 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } // 判断要插入的键值对是否存在 HashMap 中 if (e ! null) { // existing mapping for key V oldValue e.value; // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值 if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); return oldValue; } } modCount; // 键值对数量超过阈值时则进行扩容 if (size threshold) resize(); afterNodeInsertion(evict); return null; }3.1 延迟初始化table数组并非在构造方法中创建而是在首次 put 时通过resize()才初始化。这是一种典型的懒加载优化new HashMap()不立即分配 16 个桶的内存避免了空 Map 白白占用空间。3.2 哈希定位(n - 1) hash计算桶下标使用的是tab[i (n - 1) hash]。由于容量 n 恒为 2 的幂n - 1的二进制低位全为 1此时(n - 1) hash等价于hash % n但位运算比取模快得多——这正是 HashMap 强制容量为 2 的幂的根本原因。3.3 三种冲突处理分支当定位到的桶位已有元素时按优先级依次判断命中桶首节点p.hash hash ((k p.key) key || (key ! null key.equals(k)))说明 key 已存在记录到e中待后续覆盖桶位是红黑树p instanceof TreeNode调用putTreeVal走红黑树插入复杂度 O(logN)桶位是普通链表遍历链表若找到相同 key 则跳出若遍历到尾部p.next null则采用尾插法把新节点挂到链表末尾。3.4 头插改尾插JDK 1.7 到 JDK 1.8 的关键变化源码注释特别强调了这一点JDK 1.7 中新增节点采用头插入JDK 1.8 中改成了尾插入。头插法在并发扩容时可能形成环形链表导致死循环改为尾插法后结合 resize 时保持原顺序的分组策略有效规避了该问题也让链表元素顺序可预测。3.5 链表树化TREEIFY_THRESHOLD 8当链表长度达到TREEIFY_THRESHOLD - 1即binCount 7对应链表实际节点数为 8时调用treeifyBin(tab, hash)将链表转换为红黑树。8这个阈值取自二项分布在负载因子 0.75、哈希随机的情况下链表长度达到 8 的概率极低约千万分之六此时转换是划算的——既避免了普通情况下树化的开销又能在极端冲突下把最坏复杂度从 O(N) 拉回 O(logN)。3.6 覆盖旧值与其他细节若e ! null说明 key 已存在按onlyIfAbsent决定是否覆盖旧值并返回旧值put的返回值即由此而来新插入成功后modCount结构性修改计数供 fail-fast 迭代器使用size threshold时触发resize()扩容。四、resize 扩容两倍扩容与高低位拆分resize()是 HashMap 中最复杂的流程之一承担着首次初始化桶数组与后续扩容双重职责。其核心逻辑分为两大步计算新容量与新阈值、迁移旧数据。final NodeK,V[] resize() { NodeK,V[] oldTab table; int oldCap (oldTab null) ? 0 : oldTab.length; int oldThr threshold; int newCap, newThr 0; // 如果 table 不为空表明已经初始化过了 if (oldCap 0) { // 当 table 容量超过容量最大值则不再扩容 if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } // 按旧容量和阈值的2倍计算新容量和阈值的大小 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; // double threshold } else if (oldThr 0) // initial capacity was placed in threshold // 初始化时将 threshold 的值赋值给 newCap // HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值 newCap oldThr; else { // zero initial threshold signifies using defaults // 调用无参构造方法时桶数组容量为默认容量 // 阈值为默认容量与默认负载因子乘积 newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // newThr 为 0 时按阈值计算公式进行计算 if (newThr 0) { float ft (float)newCap * loadFactor; newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold newThr; // 创建新的桶数组桶数组的初始化也是在这里完成的 NodeK,V[] newTab (NodeK,V[])new Node[newCap]; table newTab; // ...数据迁移见下文 return newTab; }4.1 三种扩容入口的取值逻辑场景新容量 newCap新阈值 newThr已初始化oldCap 0且未达最大值oldCap 1两倍扩容oldThr 1阈值同步翻倍已初始化但已达MAXIMUM_CAPACITY不再扩容threshold Integer.MAX_VALUE直接返回旧表未初始化但oldThr 0带容量构造newCap oldThr取自构造时暂存的tableSizeFor结果按newCap × loadFactor重新计算未初始化且oldThr 0无参构造DEFAULT_INITIAL_CAPACITY 16(int)(0.75f × 16) 124.2 数据迁移(e.hash oldCap) 0判定高低位扩容为原容量的两倍后元素需要重新放置到新数组上。JDK 1.8 没有采用逐元素重新取模的低效做法而是利用容量翻倍后二进制多出一位的特性用e.hash oldCap一次位运算完成分组若(e.hash oldCap) 0说明该元素在新数组中下标不变归入lo低位链表仍放在newTab[j]否则说明下标会加上 oldCap归入hi高位链表放到newTab[j oldCap]。链表迁移的关键代码如下if (oldTab ! null) { // 如果旧的桶数组不为空则遍历桶数组并将键值对映射到新的桶数组中 for (int j 0; j oldCap; j) { NodeK,V e; if ((e oldTab[j]) ! null) { oldTab[j] null; if (e.next null) newTab[e.hash (newCap - 1)] e; else if (e instanceof TreeNode) // 重新映射时需要对红黑树进行拆分 ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else { // preserve order NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; // 遍历链表并将链表节点按原顺序进行分组 do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); // 将分组后的链表映射到新桶中 if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } } } } } return newTab;注意注释中的// preserve order高低位拆分时用loTail/hiTail尾指针维护了元素原有相对顺序这正是与 JDK 1.7 头插法顺序反转、并发下可能成环的关键区别之一。红黑树节点则走TreeNode.split按同样规则拆分成 lo/hi 两棵子树若拆分后某棵子树节点数过少untreeify_threshold 6还会退化为链表避免小树带来的额外开销。五、get 流程三分支快速定位get与getNode的实现是对称的读路径同样利用(n - 1) hash定位桶位然后按结构分三种情况查找public V get(Object key) { NodeK,V e; return (e getNode(hash(key), key)) null ? null : e.value; } final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; // 1. 定位键值对所在桶的位置如果该位置有元素则获取第一个元素 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 如果hash和key都与第一个元素相同则第一个元素就是我们要获取的直接返回 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; if ((e first.next) ! null) { // 2. 如果 first 是 TreeNode 类型则调用红黑树查找方法 if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); // 3. 对链表进行查找 do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }查找顺序清晰明了先比 hashO(1) 的快速筛选再比 key 的引用或 equals。这也解释了为什么自定义对象作为 key 时必须正确重写hashCode()与equals()——前者决定桶位分布后者决定命中与否二者共同决定 get 的准确性与效率。桶首元素直接命中、红黑树走getTreeNodeO(logN)、链表顺序遍历三种路径覆盖了所有可能。六、内部类Node 与 TreeNode6.1 Node单向链表节点对应底层动态数组的定义transient NodeK,V[] tableNode本身是一个标准的单向链表结构static class NodeK,V implements Map.EntryK,V { final int hash; // 存储 key 的哈希值冗余存储避免重复计算 final K key; V value; NodeK,V next; // 指向下一个节点构成单向链表 Node(int hash, K key, V value, NodeK,V next) { this.hash hash; this.key key; this.value value; this.next next; } // getKey / getValue / toString / hashCode / setValue / equals // hashCode: Objects.hashCode(key) ^ Objects.hashCode(value) // equals: 基于 Map.Entry 的 key、value 双相等判断 }hash被final修饰并冗余保存在节点中是为了在扩容迁移、链表遍历时免去重复计算用空间换时间。6.2 TreeNode红黑树节点JDK 1.8 新增的红黑树TreeNode内部类在LinkedHashMap.Entry即带before/after双向链表指针的 Node基础上扩展了树结构所需字段static final class TreeNodeK,V extends LinkedHashMap.EntryK,V { TreeNodeK,V parent; // red-black tree links TreeNodeK,V left; TreeNodeK,V right; TreeNodeK,V prev; // needed to unlink next upon deletion boolean red; // 颜色true 红false 黑 TreeNode(int hash, K key, V val, NodeK,V next) { super(hash, key, val, next); } }可以看到 TreeNode 同时保留了链表指针继承自 Node 的next与prev这使得树与链表之间的相互转换treeifyBin/untreeify、以及扩容拆分split都成为可能。红黑树的插入、删除、旋转、变色等算法实现较复杂仓库原文档明确表示将单独成文深入剖析 TreeNode本文下一节先对红黑树这一数据结构本身做系统回顾。七、红黑树HashMap 平衡性的保障红黑树是一种自平衡的二叉查找树比普通的二叉查找树效率更高它可在O(logN)时间内完成查找、增加、删除等操作。7.1 为什么需要红黑树普通的二叉查找树在极端情况下如按有序序列插入会退化成链表导致增、删、查效率低下到 O(N)。红黑树通过定义一组性质将任意节点的左右子树高度差控制在规定范围内以达到平衡状态从而保证最坏情况下的操作复杂度仍为 O(logN)。7.2 红黑树的五大性质节点是红色或黑色根是黑色所有叶子都是黑色叶子是 NIL 节点每个红色节点必须有两个黑色的子节点从每个叶子到根的所有路径上不能有两个连续的红色节点从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。性质 4 与性质 5 是红黑树平衡性的来源性质 5 保证了黑高一致性质 4 则限制了红色节点的连续出现两者共同约束使得最长路径不会超过最短路径的两倍从而保证树高维持在 O(logN) 量级。7.3 维持平衡的两种操作红黑树的操作和其他树一样包括查找、插入、删除等其查找过程与二叉查找树一样简单但插入和删除要复杂得多——这也是它保持平衡性、不会退化成链表所付出的代价。为维持平衡红黑树主要依赖两种操作旋转左旋与右旋用于在不破坏二叉查找树性质的前提下调整子树结构变色将节点的红黑颜色互换配合旋转在 O(1) 局部调整中恢复性质。八、站在源码猎人的视角HashMap 与 JDK 集合体系的联动理解了 HashMap 之后仓库中其他几个集合文档可以形成一条完整的知识链互相印证HashSet完全基于 HashMap 实现——用 key 存储元素保证不重复所有 value 统一填充同一个PRESENT对象以节省内存其无序、允许一个 null、非线程安全等特性全部继承自 HashMap。它的add就是map.put(e, PRESENT) null构造时同样按c.size() / 0.75f 1估算容量以减少 rehash。LinkedHashMap继承 HashMap底层数据结构与扩容机制完全一致额外用一条双向链表维护顺序并通过accessOrder参数支持按访问顺序排序这正是实现LRU Cache的基础。ConcurrentHashMap在 HashMap 的数据结构上解决并发安全问题。JDK 1.7 使用分段锁Segment 继承 ReentrantLockJDK 1.8 改为CAS 乐观锁 synchronized 局部锁锁粒度细化到单个桶位并发能力显著提升。九、总结与实战要点回顾全文JDK 1.8 HashMap 的设计亮点可归纳为五点数组 链表 红黑树的三层结构以 O(1) 平均复杂度换取读写性能最坏情况 O(logN)容量恒为 2 的幂用(n - 1) hash位运算替代取模定位高效懒加载 两倍扩容 高低位拆分扩容迁移只需一次e.hash oldCap位运算即可完成分组且保持元素原顺序尾插法替代头插法配合有序迁移规避了并发场景下的环形链表问题树化阈值 8、退化阈值 6的差异化设计兼顾常态性能与极端场景。实战上最值得记住的一点在能预估数据规模时务必通过构造方法指定合理的初始容量new HashMap(预估容量 / 0.75f 1)这能显著减少扩容次数是提升 HashMap 使用效率最直接的手段。对于并发场景请优先选择 ConcurrentHashMap对于需要保持插入或访问顺序的场景请使用 LinkedHashMap。【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址: https://gitcode.com/doocs/source-code-hunter创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
