Java 8 HashMap 重构引入红黑树解决链表过长性能退化问题，优化哈希算法减少碰撞，扩容机制采用尾插法避免死循环并利用位运算提升效率。源码层面分析了 Node、TreeNode 结构及 resize、treeifyBin 等核心逻辑。虽解决 Java 7 并发环状链表问题，但 HashMap 仍非线程安全，高并发场景建议使用 ConcurrentHashMap。
HashMap 是 Java 开发中使用最频繁的集合类之一，它基于哈希表实现 Map 接口，以键值对形式存储数据。在 Java 8 中，HashMap 的实现经历了自诞生以来最大的一次重构，引入了许多重要的优化和改进，旨在解决旧版本中存在的性能瓶颈和潜在问题。本文将从底层数据结构、哈希算法、扩容机制、线程安全性等多个维度，结合源码深入剖析 Java 8 中 HashMap 的变革，带你全面理解这些差异背后的设计思想。
在深入 Java 8 的改动之前，有必要先回顾一下 HashMap 的基本概念和 Java 7 及之前版本的核心实现。
Node<K,V>[] table容量 * 负载因子，当元素个数超过阈值时触发扩容。在哈希函数设计不佳或存在大量哈希冲突的情况下，链表会变得很长，使得查找、插入、删除操作的时间复杂度从 O(1) 退化到 O(n)。例如，攻击者可以构造大量哈希值相同的键，使 HashMap 退化成单链表，引发拒绝服务攻击。
Java 7 的 HashMap 在扩容迁移元素时，采用'头插法'将原链表中的节点插入新数组的对应桶中。头插法会导致链表反转，在多线程并发扩容时，两个线程可能同时操作链表，使链表形成环，导致后续查询时陷入死循环。这是 Java 7 HashMap 最著名的并发问题。
Java 7 的哈希函数通过多次异或和移位运算来扰动 hashCode，以减少碰撞，但效率相对较低。其代码如下：
static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
这种扰动函数虽然能够有效降低碰撞，但计算步骤较多。
Java 8 对 HashMap 进行了彻底的重写，主要变化体现在以下几个方面：
在 Java 8 中，当链表长度超过一定阈值（默认为 8）且数组长度大于等于 64 时，链表会转换为红黑树（Treeify），将查询时间复杂度从 O(n) 降低到 O(log n)。当红黑树节点数减少到 6 时，又会转换回链表（Untreeify）。引入红黑树的目的是在哈希碰撞严重的情况下，仍能保证良好的性能。
为什么选择红黑树？
树化阈值的选择：为什么是 8？ 官方注释中给出的解释是基于泊松分布的概率计算。在理想随机哈希码下，桶中节点个数的概率服从泊松分布，参数约为 0.5（负载因子 0.75 时的平均填充因子）。计算得到链表长度达到 8 的概率已经非常小（约 0.00000006），因此将 8 作为树化阈值，可以在保证性能的同时，避免过度树化带来的空间开销。
链表长度超过 8 但数组长度小于 64 时，不会立即树化，而是优先进行扩容（resize）。这是因为在数组容量较小时，扩容可以更有效地分散哈希冲突，避免不必要的树化开销。
Java 8 中对哈希函数的实现做了简化，将高位与低位进行异或，称为'扰动函数'：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
它将 key 的 hashCode 的高 16 位与低 16 位进行异或，使高位的特征也能影响最终的下标计算。相比 Java 7，这个扰动函数只做了一次右移和异或，性能更高，同时仍然能够有效减少碰撞（因为数组下标由哈希值的低位决定，高位特征丢失可能导致冲突）。
Java 8 对扩容过程进行了两方面的改进：
hash & oldCap 来判断元素的新位置。原理分析：
假设原数组容量为 n（2 的幂），扩容后容量为 2n。在计算元素存放位置时，使用的是 (n - 1) & hash。当容量翻倍后，新的掩码变为 (2n - 1)，相当于在原掩码的最高位增加了一个 1。因此，元素的新位置要么是原位置，要么是原位置加上旧容量 n。判断依据就是看哈希值在新增的那一位上是 0 还是 1：
hash & n == 0，说明新增位为 0，元素留在原索引 j；j + oldCap。这样，扩容时无需重新计算哈希值，只需遍历链表，按条件拆分成两条链表，分别插入新数组的两个对应桶中。同时，由于采用尾插法，链表在拆分后仍保持原来的顺序，这对于依赖顺序的场景（如迭代）更友好。
树化过程涉及 treeifyBin() 和 treeify() 方法。当链表长度达到 8 且数组长度 ≥ 64 时，putVal 方法会调用 treeifyBin 将链表转换为红黑树。转换时，先创建 TreeNode 对象（继承自 LinkedHashMap.Entry，而 LinkedHashMap.Entry 继承自 HashMap.Node），然后通过 treeify 方法构建红黑树，并设置桶的头节点为树的根节点。
去树化发生在扩容或删除元素时，如果红黑树节点数小于 6，untreeify 会将树转换回链表。注意，树化阈值与去树化阈值不同（8 和 6），中间留有缓冲，避免频繁树化和去树化带来的抖动。
由于引入了红黑树，HashMap 的迭代器（如 KeyIterator、ValueIterator、EntryIterator）以及 Java 8 新增的 Spliterator 都需要同时支持链表和树的遍历。TreeNode 本身是 Node 的子类，因此迭代器可以通过 nextNode 方法统一遍历，但树的遍历需要额外处理（树节点也有 next 指针，维护着链表顺序）。
为了更深入地理解上述改进，我们直接分析 Java 8 中 HashMap 的核心源码片段。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 默认初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树化阈值：链表长度超过 8 时考虑树化
static final int TREEIFY_THRESHOLD = 8;
// 去树化阈值：红黑树节点数小于 6 时退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树化容量：数组长度小于 64 时不进行树化，优先扩容
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储桶数组，每个元素是 Node 或 TreeNode
transient Node<K,V>[] table;
// entrySet 缓存
transient Set<Map.Entry<K,V>> entrySet;
// 元素个数
transient int size;
// 修改次数，用于 fail-fast 机制
transient int modCount;
// 扩容阈值 = capacity * load factor
int threshold;
// 负载因子
final float loadFactor;
// ...
}
链表节点 Node<K,V>：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// 构造器、getter、setter、equals、hashCode
}
红黑树节点 TreeNode<K,V> 继承自 LinkedHashMap.Entry<K,V>，而 LinkedHashMap.Entry 继承自 HashMap.Node，因此 TreeNode 同时拥有 next 指针（用于维护链表顺序）和树相关的属性（parent、left、right、prev、red）。这种设计使得树节点既能作为红黑树节点，又能作为链表节点，简化了遍历。
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 位有效，如果哈希值的高位变化而低位不变，就容易冲突。通过扰动，使低位也能混合高位的信息，降低碰撞概率。
put(K key, V value) 实际调用 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;
// 如果数组为空，则通过 resize 初始化
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;
// 如果桶的第一个节点与待插入键匹配，记录为 e
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是树节点，调用树的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 链表遍历
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表长度达到树化阈值（8），尝试树化
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
}
// 如果找到了相同键，更新值并返回旧值
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
++modCount;
// 元素个数超过阈值，扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
关键点：
treeifyBin 尝试树化。treeifyBin 内部会检查数组长度是否小于 64，若是则进行扩容（resize），否则才真正执行链表到树的转换。final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
// 如果数组为空或长度小于 MIN_TREEIFY_CAPACITY，优先扩容
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;
// 将链表节点依次替换为 TreeNode，并组成双向链表
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);
// 调用树节点的 treeify 方法构建红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
这里将普通 Node 替换为 TreeNode，同时维护了 prev 指针，形成双向链表，方便后续遍历和去树化。
扩容方法相对复杂，这里只分析关键部分，特别是元素迁移的优化：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 计算新容量和阈值...
// 创建新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
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;
// 判断 hash 与 oldCap 的位
if ((e.hash & oldCap) == 0) {
// 留在原索引的链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
// 移到原索引+oldCap 的链表
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;
}
关键优化点：
e.hash & oldCap 替代 e.hash & (newCap-1) 来区分高低位，避免重新计算哈希值。split 方法完成，类似于链表的拆分，但需要根据节点数决定是否需要去树化。final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 检查第一个节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 如果是树节点，在树中查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否则遍历链表
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
树查找通过 getTreeNode 调用 find 方法，在红黑树中二分查找，复杂度 O(log n)。
在极端哈希冲突的情况下，Java 7 的 HashMap 会退化为链表，查找复杂度 O(n)。假设有 10,000 个元素全部映射到同一个桶，一次查找需要遍历整个链表，耗时与元素数量成正比。而在 Java 8 中，当链表长度超过 8 且数组足够大时，链表会转换为红黑树，查找复杂度降为 O(log n)，10,000 个元素时最多比较 14 次，性能提升显著。
在正常哈希分布下，大多数桶的链表长度很短（0 或 1），此时 Java 8 的额外开销仅在于判断节点类型（是否是 TreeNode）和可能的一两次扰动计算，与 Java 7 相比差别不大。但由于红黑树的引入，内存占用略有增加（每个树节点比链表节点多存储 parent、left、right、red 等字段），但考虑到现代服务器内存容量，这点开销通常可以接受。
Java 8 的扩容不再重新计算哈希值，仅通过位运算判断新位置，效率更高。同时尾插法避免了死循环，但这也导致多线程环境下仍可能丢失数据（因为多个线程修改共享数组），所以 HashMap 依然不是线程安全的。
Java 8 的 HashMap 解决了 Java 7 中并发扩容导致死循环的问题，因为尾插法不会形成环。但这并不意味着 HashMap 可以在多线程环境下安全使用。例如：
因此，在多线程环境中，应使用 ConcurrentHashMap、Collections.synchronizedMap 或 Hashtable。特别地，Java 8 也对 ConcurrentHashMap 进行了大量优化，引入了红黑树和 CAS 操作，性能大幅提升。
与 Java 7 一样，Java 8 的 HashMap 允许一个 null 键和多个 null 值。null 键的哈希值为 0，因此总是存放在 table[0] 桶中。
最佳实践：如果已知存储元素数量，应指定初始容量，避免频繁扩容。负载因子的默认值 0.75 是时间和空间成本的折中，一般不建议修改。
HashMap 不保证迭代顺序，但随着 Java 8 的改进，由于链表尾插法，在扩容后链表顺序保持不变，但红黑树的存在使得迭代顺序更加复杂。总体而言，不应依赖 HashMap 的迭代顺序。
Java 8 为 Map 接口添加了一些默认方法，如 getOrDefault、putIfAbsent、remove（键值对）、replace 等，HashMap 实现了这些方法，方便了开发。
改进点：
仍然存在的问题：
hash & oldCap 判断，如果结果为 0 则留在原索引，否则移动到'原索引 + oldCap'。这是因为扩容后容量变为 2n，索引计算掩码新增了最高位，而该位的值正是 hash 在 oldCap 对应位上的值。Java 8 对 HashMap 的重构是一次经典的性能优化案例，它不仅解决了旧版本中存在的缺陷，还为后续的集合框架演进奠定了基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online