HashMap 源码深度解析：JDK 1.8 中数组 + 链表 + 红黑树的底层实现原理

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 HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // ... transient Node<K,V>[] table; // Node数组，实际存放键值对的地方 }

二、核心常量与字段：一把钥匙打开 HashMap

HashMap 的设计精髓，首先体现在一组精心挑选的常量与字段上。理解它们的含义与取值依据，是读懂后续所有流程的前提。

为什么初始容量选 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) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化 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 { Node<K,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 = ((TreeNode<K,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 三种冲突处理分支

当定位到的桶位已有元素时，按优先级依次判断：

1. 命中桶首节点：p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))，说明 key 已存在，记录到e中待后续覆盖；
2. 桶位是红黑树：p instanceof TreeNode，调用putTreeVal走红黑树插入，复杂度 O(logN)；
3. 桶位是普通链表：遍历链表，若找到相同 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 Node<K,V>[] resize() { Node<K,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; // 创建新的桶数组，桶数组的初始化也是在这里完成的 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // ...（数据迁移，见下文） return newTab; }

4.1 三种扩容入口的取值逻辑

4.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) { Node<K,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) // 重新映射时，需要对红黑树进行拆分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,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) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,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 ((TreeNode<K,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; }

查找顺序清晰明了：先比 hash（O(1) 的快速筛选），再比 key 的引用或 equals。这也解释了为什么自定义对象作为 key 时必须正确重写hashCode()与equals()——前者决定桶位分布，后者决定命中与否，二者共同决定 get 的准确性与效率。桶首元素直接命中、红黑树走getTreeNode（O(logN)）、链表顺序遍历，三种路径覆盖了所有可能。

六、内部类：Node 与 TreeNode

6.1 Node：单向链表节点

对应底层动态数组的定义transient Node<K,V>[] table，Node本身是一个标准的单向链表结构：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 存储 key 的哈希值（冗余存储，避免重复计算） final K key; V value; Node<K,V> next; // 指向下一个节点，构成单向链表 Node(int hash, K key, V value, Node<K,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 TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; // 颜色，true 红，false 黑 TreeNode(int hash, K key, V val, Node<K,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 红黑树的五大性质

1. 节点是红色或黑色；
2. 根是黑色；
3. 所有叶子都是黑色（叶子是 NIL 节点）；
4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）；
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

性质 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 继承 ReentrantLock），JDK 1.8 改为CAS 乐观锁 + synchronized 局部锁，锁粒度细化到单个桶位，并发能力显著提升。

九、总结与实战要点

回顾全文，JDK 1.8 HashMap 的设计亮点可归纳为五点：

1. 数组 + 链表 + 红黑树的三层结构，以 O(1) 平均复杂度换取读写性能，最坏情况 O(logN)；
2. 容量恒为 2 的幂，用(n - 1) & hash位运算替代取模，定位高效；
3. 懒加载 + 两倍扩容 + 高低位拆分，扩容迁移只需一次e.hash & oldCap位运算即可完成分组，且保持元素原顺序；
4. 尾插法替代头插法，配合有序迁移规避了并发场景下的环形链表问题；
5. 树化阈值 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