HashMap 源码解析JDK1.8 数组 链表 红黑树的底层实现与扩容机制【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址: https://gitcode.com/GitHub_Trending/so/source-code-hunter本文是 source-code-hunter 项目 JDK 集合源码赏析系列的一部分基于 HashMap.md 一文展开。HashMap 是日常开发中最常用、也是面试最常考的容器之一读懂它的源码不仅有助于写出更高效的代码也能为理解 HashSet、LinkedHashMap、ConcurrentHashMap 等兄弟容器打下坚实基础。读完本文你将掌握 JDK1.8 HashMap 的数据结构、hash 定位、put/get 全流程、扩容机制、链表与红黑树的转换阈值以及红黑树保持平衡的核心性质。一、JDK1.8 HashMap 的整体设计JDK1.8 的 HashMap 底层使用的是动态数组数组中每个元素存放的是一棵链表或红黑树。也就是说它的底层结构是数组 链表 红黑树三者的组合数组table用于快速定位桶bucket位置是键值对实际存放的骨架链表Node解决哈希冲突多个 hash 相同的键值对以单向链表的形式串在同一个桶上红黑树TreeNode当链表长度过长时为避免极端情况下退化成线性查找会将链表转换为红黑树将最坏时间复杂度从 O(N) 降到 O(logN)。与 JDK1.7 相比1.8 最大的变化就是引入了红黑树并且把链表的新增节点从头插法改成了尾插法下文 put 源码中会再次强调。二、核心常量与字段逐个解析先看类声明与核心字段public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable, Serializable { /** * 初始化容量默认 16使用位运算 1 4 表示 */ static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16 /** * 最大容量 2^30 */ static final int MAXIMUM_CAPACITY 1 30; /** * 扩容因子负载因子使用的容量达到当前容量的 75% 就扩容 */ static final float DEFAULT_LOAD_FACTOR 0.75f; /** * 链表转红黑树的阈值链表长度达到此值8会进化成红黑树 */ static final int TREEIFY_THRESHOLD 8; /** * 当前 HashMap 所能容纳键值对数量的最大值超过这个值则需扩容 */ int threshold; /** * 已使用的容量键值对个数 */ transient int size; /** * Node 数组实际存放键值对的地方 */ transient NodeK,V[] table; ... }几个关键点DEFAULT_INITIAL_CAPACITY 1 4初始容量为 16源码用位运算而不是直接写 16是因为容量本身设计为 2 的幂次位运算既直观又高效。DEFAULT_LOAD_FACTOR 0.75f负载因子默认 0.75。它表示“使用容量 / 当前容量”的比值当size threshold即容量 × 负载因子时触发扩容。0.75 是空间与时间的一个折中过小浪费空间、频繁扩容过大则冲突加剧、查找变慢。TREEIFY_THRESHOLD 8链表树化阈值。当某个桶上的链表长度达到 8 时调用treeifyBin尝试把链表转成红黑树。注意treeifyBin内部还有一个前置条件只有当 table 容量 64 时才真正树化否则优先扩容resize 可以打散链表这是源码中容易忽略的细节。threshold与sizethreshold是扩容阈值size是已存储键值对的数量。两者结合判断是否需要resize()。三、构造方法与 tableSizeFor容量为什么总是 2 的幂HashMap 提供了四个构造方法源码如下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); } 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); }值得注意的两个细节校验规则initialCapacity 0抛IllegalArgumentException超过MAXIMUM_CAPACITY会被截断为1 30loadFactor 0或Float.isNaN(loadFactor)也会抛异常。这是源码级防御式编程的典型示例。threshold tableSizeFor(initialCapacity)此时 threshold 保存的并不是真正的扩容阈值而是被“借用”来暂时保存经过tableSizeFor处理后的初始容量真正的阈值计算发生在第一次resize()时。tableSizeFor的作用是把传入的容量向上取整到最近的2 的幂次比如传入 19 会得到 32。为什么要保证容量是 2 的幂因为定位桶下标用的是(n - 1) hash这种位与运算等价于hash % n但更快。当n是 2 的幂时n - 1的二进制全是 1位与运算可以均匀地散列到各个桶同时避免取模运算带来的性能损耗。推荐实践原文档原话在初始化时根据实际情况设置好初始容量用好了可以显著减少 resize扩容时所有元素要重新映射即 rehash提升效率。例如预估要存 1000 个元素可new HashMap(1024)一次到位避免频繁扩容。四、put 全流程putVal 逐行拆解put方法入口很简单核心逻辑都在putVal中public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 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; }4.1 putVal 的执行脉络懒初始化table为 null 或长度为 0 时先调用resize()完成数组的首次初始化数组创建动作其实发生在 resize 里也就是说无参构造的 HashMap 在第一次 put 时才真正分配数组内存。桶定位i (n - 1) hash计算桶下标。若该桶为空直接放入新节点时间复杂度 O(1)。冲突处理三分支桶中第一个节点与待插入的 key 相等先比较 hash再用或equals双重比较说明是更新操作e指向该节点桶首是TreeNode说明该桶已树化走红黑树插入putTreeVal否则遍历链表若找到相同 key 则终止遍历更新若遍历到链表尾部仍没有则尾插法追加新节点并检查binCount TREEIFY_THRESHOLD - 1即链表达 8 个节点时调用treeifyBin尝试树化。更新值e ! null表示 key 已存在根据onlyIfAbsent决定是否覆盖旧值并返回旧值这是put返回值语义的由来。扩容判定size threshold时触发resize()。4.2 两个容易被忽略的细节JDK1.7 头插 vs JDK1.8 尾插1.7 新节点插入链表头部在并发扩容时容易形成环形链表导致死循环1.8 改为尾插配合 resize 中的分组迁移规避了这一问题。注意HashMap 本身仍非线程安全并发场景请使用 ConcurrentHashMap其并发原理见该文档CAS 乐观锁 synchronized 局部锁锁粒度比 JDK7 分段锁更细。afterNodeAccess/afterNodeInsertion这两个方法在 HashMap 中是空实现属于为子类预留的 hook 方法。LinkedHashMap 正是重写了它们来维护双向链表顺序相关解析见 LinkedHashMap.md。五、hash 扰动函数hash(key) 与 (n-1) hashputVal收到的 hash 并不是key.hashCode()的原始值而是经过hash(key)处理后的值static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这段代码被称为扰动函数将 key 的 hashCode 高 16 位与低 16 位做异或让高位的特征也参与低位运算。因为定位桶只用到了(n - 1) hash的低位n 为 2 的幂时 n-1 的高位全是 0如果不做扰动仅依赖低位当 hashCode 分布不均时容易大量冲突。扰动后散列更均匀冲突概率更低。另一个细节key null时 hash 为 0所以HashMap 允许一个 null key它会被放到下标为 0 的桶里。六、扩容机制 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; 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; }6.1 新容量与新阈值怎么算已初始化oldCap 0若oldCap MAXIMUM_CAPACITY不再扩容threshold 直接设为Integer.MAX_VALUE否则newCap oldCap 1翻倍并且当旧容量不小于默认容量 16 时newThr oldThr 1阈值同步翻倍。未初始化但 threshold 0即使用了带初始容量的构造方法newCap oldThr此时才真正兑现构造时tableSizeFor计算出的容量。完全默认无参构造newCap 16newThr 0.75 * 16 12。兜底计算若newThr 0如旧容量小于 16 时阈值未翻倍统一用ft newCap * loadFactor重新计算并做最大值保护。6.2 链表迁移的高明之处lo / hi 双链表对普通链表resize 采用了一种无需重新计算下标、无需打乱顺序的精妙做法因为新容量是旧容量的 2 倍(e.hash newCap - 1)与(e.hash oldCap - 1)相比唯一的区别是**多出的那一位oldCap 对应的位**是 0 还是 1。因此只需判断(e.hash oldCap) 0为 0节点留在原下标j串成 lo 链表low为 1节点迁移到j oldCap串成 hi 链表high。迁移后保持了原链表节点的相对顺序配合 1.8 的尾插法进一步降低并发风险。对红黑树则调用TreeNode.split做类似的拆分拆完后若某半边节点数过少还会退化成链表。七、get 查询getNode 的三种命中路径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; }查找逻辑与 put 完全对称先算 hash、定位桶、比较首节点然后根据桶内结构是红黑树还是链表走对应查找。比较 key 时统一采用“先比 hash再用或equals”的双重判断hash 不等直接跳过hash 相等再用或equals精确认证这也是为什么key 的equals和hashCode必须一致重写——这一点在 String.md 中有专门强调equals相等的两个对象hashCode必须相等否则 HashMap 无法正确定位和取回元素。八、底层节点结构Node 与 TreeNode8.1 Node单向链表节点static class NodeK,V implements Map.EntryK,V { final int hash; 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; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue value; value newValue; return oldValue; } public final boolean equals(Object o) { if (o this) return true; if (o instanceof Map.Entry) { Map.Entry?,? e (Map.Entry?,?)o; if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue())) return true; } return false; } }Node 是对Map.Entry的实现结构非常清晰hash、key、value三个字段加上next指针很明显是一个单向链表结构正是它串起了transient NodeK,V[] table数组中的冲突元素。hashCode()由 key 和 value 的 hashCode 异或得到equals()则要求 key 和 value 同时相等。8.2 TreeNode红黑树节点/** * JDK8 加入的红黑树 TreeNode 内部类红黑树的方法比较复杂这里只展示一些重要的属性结构代码 */ 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 // 颜色true 红false 黑 boolean red; TreeNode(int hash, K key, V val, NodeK,V next) { super(hash, key, val, next); } }TreeNode 继承了LinkedHashMap.Entry即带 before/after 指针的双向链表节点并增加了parent、left、right、prev指针与red颜色标记兼具双向链表与红黑树两种结构的能力既服务于树的旋转、变色与查找又保留了链表的前后链接以便拆分、删除时快速断链。这也解释了为什么树化后仍然可以“还原”出有序链表。九、回顾数据结构红黑树红黑树是 HashMap 链表过长时的“进化形态”它是一种自平衡的二叉查找树比普通的二叉查找树效率更高可在O(logN) 时间内完成查找、增加、删除等操作。为什么需要它因为普通的二叉查找树在极端情况下如按有序序列插入会退化成链表导致增、删、查效率降至 O(N)。红黑树通过定义以下性质将任意节点的左右子树高度差控制在规定范围内以达到平衡状态节点是红色或黑色。根是黑色。所有叶子都是黑色叶子是 NIL 节点。每个红色节点必须有两个黑色的子节点从每个叶子到根的所有路径上不能有两个连续的红色节点。从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。红黑树的操作和其他树一样包括查找、插入、删除等。其查找过程和二叉查找树一样简单但插入和删除操作要复杂得多——这正是其为保持平衡性、不退化成长链表所付出的代价。红黑树为保持平衡性所进行的操作主要有旋转左旋、右旋和变色。红黑树的实现确实比较复杂光是理解其插入、删除的操作原理就颇为费劲。原文档作者在此处“挖了个坑”计划后续单独成文分析 HashMap 内部类 TreeNode 对红黑树数据结构的完整实现读者也可以带着上述五条性质结合putTreeVal、rotateLeft、rotateRight、balanceInsertion、balanceDeletion等方法自行研读。十、从 HashMap 看它的“家族成员”理解了 HashMap 之后会发现它是整个集合家族的“地基”仓库中的 HashSet.md 与 LinkedHashMap.md 都直接建立在其上HashSet 基于 HashMap 实现内部持有HashMapE, Object map所有元素作为 map 的key存储value 统一使用同一个静态PRESENT对象以节省内存从而天然获得“元素不重复”的特性。因为依赖 HashMap 的 key所以 HashSet 也是无序、非线程安全、允许一个 null 元素的。它的add就是map.put(e, PRESENT) nullcontains就是map.containsKey(o)几乎全部方法都是一行代理。LinkedHashMap 继承 HashMap底层数据结构与扩容机制与 HashMap 完全一致差异在于它额外用一条双向链表维护插入/访问顺序通过重写afterNodeInsertion、afterNodeRemoval、afterNodeAccess三个 hook 方法在增删查后维护链表当构造参数accessOrder true时每次get都会把节点移到链表尾部从而天然支持LRU 缓存的实现配合removeEldestEntry即可淘汰最久未使用的元素。ConcurrentHashMap 的并发升级同样是数组 链表 红黑树 TREEIFY_THRESHOLD 8但为线程安全做了改造空桶用CAS无锁写入冲突时用synchronized 局部锁锁住桶首节点扩容时其他线程可协助迁移helpTransfer相比 JDK7 的分段锁Segment 继承 ReentrantLock锁粒度更细、并发能力更强详见 ConcurrentHashMap.md。此外集合家族中 ArrayList.md 代表“动态数组”实现、LinkedList 代表“双向链表”实现配合本文的 HashMap可以横向对比“数组 vs 链表 vs 哈希表”三类容器在插入、查找、扩容上的不同取舍。十一、总结与面试要点数据结构JDK1.8 HashMap 动态数组 单向链表 红黑树table懒加载首次 put 才初始化。三个核心参数默认容量 16、负载因子 0.75、树化阈值 8容量始终是 2 的幂桶下标用(n - 1) hash定位hash 经高 16 位与低 16 位异或扰动且允许一个 null key。put 流程懒初始化 → 桶定位 → 空桶直接放入 / 首节点相同则更新 / TreeNode 走红黑树插入 / 链表尾插并计数链表达 8 时treeifyBin尝试树化最后size threshold触发扩容。get 流程hash 定位 → 比较首节点 → 按 TreeNode / 链表分别查找全程先比 hash 再比 key或equals。扩容容量与阈值双倍增长链表迁移利用(e.hash oldCap)拆分为 lo/hi 两条链表分别落在j与j oldCap保持原顺序树节点走TreeNode.split。与 JDK1.7 的差异1.8 引入红黑树、链表改尾插法、resize 保持节点相对顺序从设计层面缓解了 1.7 头插法在并发扩容时的环形链表问题但 HashMap 依旧非线程安全并发请用 ConcurrentHashMap。红黑树满足五条性质的二叉查找树增删查 O(logN)靠左旋、右旋、变色维持平衡。更完整的源码注解可回到 HashMap.md 原文对照阅读对集合家族感兴趣的同学建议按 HashSet → LinkedHashMap → ConcurrentHashMap 的顺序继续研读会发现处处都是 HashMap 的身影。【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址: https://gitcode.com/GitHub_Trending/so/source-code-hunter创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/12 7:56:53 · 阅读 1.2k HashMap 源码解析：JDK1.8 数组 + 链表 + 红黑树的底层实现与扩容机制
HashMap 源码解析JDK1.8 数组 链表 红黑树的底层实现与扩容机制【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址: https://gitcode.com/GitHub_Trending/so/source-code-hunter本文是 source-code-hunter 项目 JDK 集合源码赏析系列的一部分基于 HashMap.md 一文展开。HashMap 是日常开发中最常用、也是面试最常考的容器之一读懂它的源码不仅有助于写出更高效的代码也能为理解 HashSet、LinkedHashMap、ConcurrentHashMap 等兄弟容器打下坚实基础。读完本文你将掌握 JDK1.8 HashMap 的数据结构、hash 定位、put/get 全流程、扩容机制、链表与红黑树的转换阈值以及红黑树保持平衡的核心性质。一、JDK1.8 HashMap 的整体设计JDK1.8 的 HashMap 底层使用的是动态数组数组中每个元素存放的是一棵链表或红黑树。也就是说它的底层结构是数组 链表 红黑树三者的组合数组table用于快速定位桶bucket位置是键值对实际存放的骨架链表Node解决哈希冲突多个 hash 相同的键值对以单向链表的形式串在同一个桶上红黑树TreeNode当链表长度过长时为避免极端情况下退化成线性查找会将链表转换为红黑树将最坏时间复杂度从 O(N) 降到 O(logN)。与 JDK1.7 相比1.8 最大的变化就是引入了红黑树并且把链表的新增节点从头插法改成了尾插法下文 put 源码中会再次强调。二、核心常量与字段逐个解析先看类声明与核心字段public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable, Serializable { /** * 初始化容量默认 16使用位运算 1 4 表示 */ static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16 /** * 最大容量 2^30 */ static final int MAXIMUM_CAPACITY 1 30; /** * 扩容因子负载因子使用的容量达到当前容量的 75% 就扩容 */ static final float DEFAULT_LOAD_FACTOR 0.75f; /** * 链表转红黑树的阈值链表长度达到此值8会进化成红黑树 */ static final int TREEIFY_THRESHOLD 8; /** * 当前 HashMap 所能容纳键值对数量的最大值超过这个值则需扩容 */ int threshold; /** * 已使用的容量键值对个数 */ transient int size; /** * Node 数组实际存放键值对的地方 */ transient NodeK,V[] table; ... }几个关键点DEFAULT_INITIAL_CAPACITY 1 4初始容量为 16源码用位运算而不是直接写 16是因为容量本身设计为 2 的幂次位运算既直观又高效。DEFAULT_LOAD_FACTOR 0.75f负载因子默认 0.75。它表示“使用容量 / 当前容量”的比值当size threshold即容量 × 负载因子时触发扩容。0.75 是空间与时间的一个折中过小浪费空间、频繁扩容过大则冲突加剧、查找变慢。TREEIFY_THRESHOLD 8链表树化阈值。当某个桶上的链表长度达到 8 时调用treeifyBin尝试把链表转成红黑树。注意treeifyBin内部还有一个前置条件只有当 table 容量 64 时才真正树化否则优先扩容resize 可以打散链表这是源码中容易忽略的细节。threshold与sizethreshold是扩容阈值size是已存储键值对的数量。两者结合判断是否需要resize()。三、构造方法与 tableSizeFor容量为什么总是 2 的幂HashMap 提供了四个构造方法源码如下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); } 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); }值得注意的两个细节校验规则initialCapacity 0抛IllegalArgumentException超过MAXIMUM_CAPACITY会被截断为1 30loadFactor 0或Float.isNaN(loadFactor)也会抛异常。这是源码级防御式编程的典型示例。threshold tableSizeFor(initialCapacity)此时 threshold 保存的并不是真正的扩容阈值而是被“借用”来暂时保存经过tableSizeFor处理后的初始容量真正的阈值计算发生在第一次resize()时。tableSizeFor的作用是把传入的容量向上取整到最近的2 的幂次比如传入 19 会得到 32。为什么要保证容量是 2 的幂因为定位桶下标用的是(n - 1) hash这种位与运算等价于hash % n但更快。当n是 2 的幂时n - 1的二进制全是 1位与运算可以均匀地散列到各个桶同时避免取模运算带来的性能损耗。推荐实践原文档原话在初始化时根据实际情况设置好初始容量用好了可以显著减少 resize扩容时所有元素要重新映射即 rehash提升效率。例如预估要存 1000 个元素可new HashMap(1024)一次到位避免频繁扩容。四、put 全流程putVal 逐行拆解put方法入口很简单核心逻辑都在putVal中public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 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; }4.1 putVal 的执行脉络懒初始化table为 null 或长度为 0 时先调用resize()完成数组的首次初始化数组创建动作其实发生在 resize 里也就是说无参构造的 HashMap 在第一次 put 时才真正分配数组内存。桶定位i (n - 1) hash计算桶下标。若该桶为空直接放入新节点时间复杂度 O(1)。冲突处理三分支桶中第一个节点与待插入的 key 相等先比较 hash再用或equals双重比较说明是更新操作e指向该节点桶首是TreeNode说明该桶已树化走红黑树插入putTreeVal否则遍历链表若找到相同 key 则终止遍历更新若遍历到链表尾部仍没有则尾插法追加新节点并检查binCount TREEIFY_THRESHOLD - 1即链表达 8 个节点时调用treeifyBin尝试树化。更新值e ! null表示 key 已存在根据onlyIfAbsent决定是否覆盖旧值并返回旧值这是put返回值语义的由来。扩容判定size threshold时触发resize()。4.2 两个容易被忽略的细节JDK1.7 头插 vs JDK1.8 尾插1.7 新节点插入链表头部在并发扩容时容易形成环形链表导致死循环1.8 改为尾插配合 resize 中的分组迁移规避了这一问题。注意HashMap 本身仍非线程安全并发场景请使用 ConcurrentHashMap其并发原理见该文档CAS 乐观锁 synchronized 局部锁锁粒度比 JDK7 分段锁更细。afterNodeAccess/afterNodeInsertion这两个方法在 HashMap 中是空实现属于为子类预留的 hook 方法。LinkedHashMap 正是重写了它们来维护双向链表顺序相关解析见 LinkedHashMap.md。五、hash 扰动函数hash(key) 与 (n-1) hashputVal收到的 hash 并不是key.hashCode()的原始值而是经过hash(key)处理后的值static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这段代码被称为扰动函数将 key 的 hashCode 高 16 位与低 16 位做异或让高位的特征也参与低位运算。因为定位桶只用到了(n - 1) hash的低位n 为 2 的幂时 n-1 的高位全是 0如果不做扰动仅依赖低位当 hashCode 分布不均时容易大量冲突。扰动后散列更均匀冲突概率更低。另一个细节key null时 hash 为 0所以HashMap 允许一个 null key它会被放到下标为 0 的桶里。六、扩容机制 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; 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; }6.1 新容量与新阈值怎么算已初始化oldCap 0若oldCap MAXIMUM_CAPACITY不再扩容threshold 直接设为Integer.MAX_VALUE否则newCap oldCap 1翻倍并且当旧容量不小于默认容量 16 时newThr oldThr 1阈值同步翻倍。未初始化但 threshold 0即使用了带初始容量的构造方法newCap oldThr此时才真正兑现构造时tableSizeFor计算出的容量。完全默认无参构造newCap 16newThr 0.75 * 16 12。兜底计算若newThr 0如旧容量小于 16 时阈值未翻倍统一用ft newCap * loadFactor重新计算并做最大值保护。6.2 链表迁移的高明之处lo / hi 双链表对普通链表resize 采用了一种无需重新计算下标、无需打乱顺序的精妙做法因为新容量是旧容量的 2 倍(e.hash newCap - 1)与(e.hash oldCap - 1)相比唯一的区别是**多出的那一位oldCap 对应的位**是 0 还是 1。因此只需判断(e.hash oldCap) 0为 0节点留在原下标j串成 lo 链表low为 1节点迁移到j oldCap串成 hi 链表high。迁移后保持了原链表节点的相对顺序配合 1.8 的尾插法进一步降低并发风险。对红黑树则调用TreeNode.split做类似的拆分拆完后若某半边节点数过少还会退化成链表。七、get 查询getNode 的三种命中路径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; }查找逻辑与 put 完全对称先算 hash、定位桶、比较首节点然后根据桶内结构是红黑树还是链表走对应查找。比较 key 时统一采用“先比 hash再用或equals”的双重判断hash 不等直接跳过hash 相等再用或equals精确认证这也是为什么key 的equals和hashCode必须一致重写——这一点在 String.md 中有专门强调equals相等的两个对象hashCode必须相等否则 HashMap 无法正确定位和取回元素。八、底层节点结构Node 与 TreeNode8.1 Node单向链表节点static class NodeK,V implements Map.EntryK,V { final int hash; 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; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue value; value newValue; return oldValue; } public final boolean equals(Object o) { if (o this) return true; if (o instanceof Map.Entry) { Map.Entry?,? e (Map.Entry?,?)o; if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue())) return true; } return false; } }Node 是对Map.Entry的实现结构非常清晰hash、key、value三个字段加上next指针很明显是一个单向链表结构正是它串起了transient NodeK,V[] table数组中的冲突元素。hashCode()由 key 和 value 的 hashCode 异或得到equals()则要求 key 和 value 同时相等。8.2 TreeNode红黑树节点/** * JDK8 加入的红黑树 TreeNode 内部类红黑树的方法比较复杂这里只展示一些重要的属性结构代码 */ 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 // 颜色true 红false 黑 boolean red; TreeNode(int hash, K key, V val, NodeK,V next) { super(hash, key, val, next); } }TreeNode 继承了LinkedHashMap.Entry即带 before/after 指针的双向链表节点并增加了parent、left、right、prev指针与red颜色标记兼具双向链表与红黑树两种结构的能力既服务于树的旋转、变色与查找又保留了链表的前后链接以便拆分、删除时快速断链。这也解释了为什么树化后仍然可以“还原”出有序链表。九、回顾数据结构红黑树红黑树是 HashMap 链表过长时的“进化形态”它是一种自平衡的二叉查找树比普通的二叉查找树效率更高可在O(logN) 时间内完成查找、增加、删除等操作。为什么需要它因为普通的二叉查找树在极端情况下如按有序序列插入会退化成链表导致增、删、查效率降至 O(N)。红黑树通过定义以下性质将任意节点的左右子树高度差控制在规定范围内以达到平衡状态节点是红色或黑色。根是黑色。所有叶子都是黑色叶子是 NIL 节点。每个红色节点必须有两个黑色的子节点从每个叶子到根的所有路径上不能有两个连续的红色节点。从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。红黑树的操作和其他树一样包括查找、插入、删除等。其查找过程和二叉查找树一样简单但插入和删除操作要复杂得多——这正是其为保持平衡性、不退化成长链表所付出的代价。红黑树为保持平衡性所进行的操作主要有旋转左旋、右旋和变色。红黑树的实现确实比较复杂光是理解其插入、删除的操作原理就颇为费劲。原文档作者在此处“挖了个坑”计划后续单独成文分析 HashMap 内部类 TreeNode 对红黑树数据结构的完整实现读者也可以带着上述五条性质结合putTreeVal、rotateLeft、rotateRight、balanceInsertion、balanceDeletion等方法自行研读。十、从 HashMap 看它的“家族成员”理解了 HashMap 之后会发现它是整个集合家族的“地基”仓库中的 HashSet.md 与 LinkedHashMap.md 都直接建立在其上HashSet 基于 HashMap 实现内部持有HashMapE, Object map所有元素作为 map 的key存储value 统一使用同一个静态PRESENT对象以节省内存从而天然获得“元素不重复”的特性。因为依赖 HashMap 的 key所以 HashSet 也是无序、非线程安全、允许一个 null 元素的。它的add就是map.put(e, PRESENT) nullcontains就是map.containsKey(o)几乎全部方法都是一行代理。LinkedHashMap 继承 HashMap底层数据结构与扩容机制与 HashMap 完全一致差异在于它额外用一条双向链表维护插入/访问顺序通过重写afterNodeInsertion、afterNodeRemoval、afterNodeAccess三个 hook 方法在增删查后维护链表当构造参数accessOrder true时每次get都会把节点移到链表尾部从而天然支持LRU 缓存的实现配合removeEldestEntry即可淘汰最久未使用的元素。ConcurrentHashMap 的并发升级同样是数组 链表 红黑树 TREEIFY_THRESHOLD 8但为线程安全做了改造空桶用CAS无锁写入冲突时用synchronized 局部锁锁住桶首节点扩容时其他线程可协助迁移helpTransfer相比 JDK7 的分段锁Segment 继承 ReentrantLock锁粒度更细、并发能力更强详见 ConcurrentHashMap.md。此外集合家族中 ArrayList.md 代表“动态数组”实现、LinkedList 代表“双向链表”实现配合本文的 HashMap可以横向对比“数组 vs 链表 vs 哈希表”三类容器在插入、查找、扩容上的不同取舍。十一、总结与面试要点数据结构JDK1.8 HashMap 动态数组 单向链表 红黑树table懒加载首次 put 才初始化。三个核心参数默认容量 16、负载因子 0.75、树化阈值 8容量始终是 2 的幂桶下标用(n - 1) hash定位hash 经高 16 位与低 16 位异或扰动且允许一个 null key。put 流程懒初始化 → 桶定位 → 空桶直接放入 / 首节点相同则更新 / TreeNode 走红黑树插入 / 链表尾插并计数链表达 8 时treeifyBin尝试树化最后size threshold触发扩容。get 流程hash 定位 → 比较首节点 → 按 TreeNode / 链表分别查找全程先比 hash 再比 key或equals。扩容容量与阈值双倍增长链表迁移利用(e.hash oldCap)拆分为 lo/hi 两条链表分别落在j与j oldCap保持原顺序树节点走TreeNode.split。与 JDK1.7 的差异1.8 引入红黑树、链表改尾插法、resize 保持节点相对顺序从设计层面缓解了 1.7 头插法在并发扩容时的环形链表问题但 HashMap 依旧非线程安全并发请用 ConcurrentHashMap。红黑树满足五条性质的二叉查找树增删查 O(logN)靠左旋、右旋、变色维持平衡。更完整的源码注解可回到 HashMap.md 原文对照阅读对集合家族感兴趣的同学建议按 HashSet → LinkedHashMap → ConcurrentHashMap 的顺序继续研读会发现处处都是 HashMap 的身影。【免费下载链接】source-code-hunter 从源码层面剖析挖掘互联网行业主流技术的底层实现原理为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶Mybatis、Netty、Dubbo 框架及 Redis、Tomcat 中间件等项目地址: https://gitcode.com/GitHub_Trending/so/source-code-hunter创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考