Java 8 中 HashMap 到底有啥不同？
HashMap 是 Java 开发中使用最频繁的集合类之一，它基于哈希表实现 Map 接口，以键值对形式存储数据。在 Java 8 中，HashMap 的实现经历了自诞生以来最大的一次重构，引入了许多重要的优化和改进，旨在解决旧版本中存在的性能瓶颈和潜在问题。本文将从底层数据结构、哈希算法、扩容机制、线程安全性等多个维度，结合源码深入剖析 Java 8 中 HashMap 的变革，带你全面理解这些差异背后的设计思想。
1. HashMap 基础回顾
在深入 Java 8 的改动之前，有必要先回顾一下 HashMap 的基本概念和 Java 7 及之前版本的核心实现。
- 存储结构：HashMap 内部维护一个
Node<K,V>[] table数组（也称为桶数组），每个数组元素是一个单链表的头节点或红黑树的根节点。当插入键值对时，根据键的 hashCode 计算出数组下标，如果该位置为空则直接放入；如果发生哈希冲突（多个键映射到同一桶），则采用链地址法，将新节点插入链表。 - 重要参数：
- 初始容量（initial capacity）：默认 16，必须是 2 的幂。
- 负载因子（load factor）：默认 0.75，衡量 HashMap 填充程度的指标。
- 阈值（threshold）：
容量 * 负载因子，当元素个数超过阈值时触发扩容。
- 扩容机制：当元素数量超过阈值，HashMap 会扩容为原容量的两倍，并将所有元素重新计算哈希值后分配到新数组中（rehash）。这个过程非常耗时。
- 线程安全性：HashMap 不是线程安全的。在多线程环境下，Java 7 的 HashMap 在并发扩容时可能形成环形链表，导致后续 get 操作死循环。
2. Java 7 及之前 HashMap 的局限
2.1 链表过长导致的性能退化
在哈希函数设计不佳或存在大量哈希冲突的情况下，链表会变得很长，使得查找、插入、删除操作的时间复杂度从 O(1) 退化到 O(n)。例如，攻击者可以构造大量哈希值相同的键，使 HashMap 退化成单链表，引发拒绝服务攻击。
2.2 扩容时头插法引发的死循环
Java 7 的 HashMap 在扩容迁移元素时，采用“头插法”将原链表中的节点插入新数组的对应桶中。头插法会导致链表反转，在多线程并发扩容时，两个线程可能同时操作链表，使链表形成环，导致后续查询时陷入死循环。这是 Java 7 HashMap 最著名的并发问题。
2.3 哈希算法不够高效
Java 7 的哈希函数通过多次异或和移位运算来扰动 hashCode，以减少碰撞，但效率相对较低。其代码如下：
java
static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
这种扰动函数虽然能够有效降低碰撞，但计算步骤较多。
3. Java 8 HashMap 的核心改进
Java 8 对 HashMap 进行了彻底的重写，主要变化体现在以下几个方面：
3.1 数据结构升级：数组 + 链表 + 红黑树
在 Java 8 中，当链表长度超过一定阈值（默认为 8）且数组长度大于等于 64 时，链表会转换为红黑树（Treeify），将查询时间复杂度从 O(n) 降低到 O(log n)。当红黑树节点数减少到 6 时，又会转换回链表（Untreeify）。引入红黑树的目的是在哈希碰撞严重的情况下，仍能保证良好的性能。
为什么选择红黑树？
- 平衡二叉搜索树（如 AVL 树）虽然查找更快（O(log n)），但插入/删除需要更多的旋转操作，综合性能不如红黑树。
- 红黑树是一种近似平衡的二叉搜索树，它能够以 O(log n) 的时间复杂度完成查找、插入和删除，且旋转次数相对较少。
- 在实际应用中，哈希碰撞的概率通常较低，大多数桶中链表长度很小，此时链表操作成本低于红黑树（树节点需要维护父节点、左右子节点、颜色等，占用空间更大）。因此，Java 8 只在链表过长时才启用树化，达到空间和时间的平衡。
树化阈值的选择：为什么是 8？
官方注释中给出的解释是基于泊松分布的概率计算。在理想随机哈希码下，桶中节点个数的概率服从泊松分布，参数约为 0.5（负载因子 0.75 时的平均填充因子）。计算得到链表长度达到 8 的概率已经非常小（约 0.00000006），因此将 8 作为树化阈值，可以在保证性能的同时，避免过度树化带来的空间开销。
链表长度超过 8 但数组长度小于 64 时，不会立即树化，而是优先进行扩容（resize）。这是因为在数组容量较小时，扩容可以更有效地分散哈希冲突，避免不必要的树化开销。
3.2 哈希算法的简化与优化
Java 8 中对哈希函数的实现做了简化，将高位与低位进行异或，称为“扰动函数”：
java
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
它将 key 的 hashCode 的高 16 位与低 16 位进行异或，使高位的特征也能影响最终的下标计算。相比 Java 7，这个扰动函数只做了一次右移和异或，性能更高，同时仍然能够有效减少碰撞（因为数组下标由哈希值的低位决定，高位特征丢失可能导致冲突）。
3.3 扩容机制的优化
Java 8 对扩容过程进行了两方面的改进：
- 去除了头插法，改用尾插法，从而避免多线程环境下的环形链表问题（但 HashMap 本身仍非线程安全）。
- 元素迁移不再重新计算哈希，而是利用扩容后容量是 2 的幂这一特点，通过
hash & oldCap来判断元素的新位置。
原理分析：
假设原数组容量为 n（2 的幂），扩容后容量为 2n。在计算元素存放位置时，使用的是 (n - 1) & hash。当容量翻倍后，新的掩码变为 (2n - 1)，相当于在原掩码的最高位增加了一个 1。因此，元素的新位置要么是原位置，要么是原位置加上旧容量 n。判断依据就是看哈希值在新增的那一位上是 0 还是 1：
- 如果
hash & n == 0，说明新增位为 0，元素留在原索引j； - 否则，新增位为 1，元素移动到
j + oldCap。
这样，扩容时无需重新计算哈希值，只需遍历链表，按条件拆分成两条链表，分别插入新数组的两个对应桶中。同时，由于采用尾插法，链表在拆分后仍保持原来的顺序，这对于依赖顺序的场景（如迭代）更友好。
3.4 树化与去树化的实现细节
树化过程涉及 treeifyBin() 和 treeify() 方法。当链表长度达到 8 且数组长度 ≥ 64 时，putVal 方法会调用 treeifyBin 将链表转换为红黑树。转换时，先创建 TreeNode 对象（继承自 LinkedHashMap.Entry，而 LinkedHashMap.Entry 继承自 HashMap.Node），然后通过 treeify 方法构建红黑树，并设置桶的头节点为树的根节点。
去树化发生在扩容或删除元素时，如果红黑树节点数小于 6，untreeify 会将树转换回链表。注意，树化阈值与去树化阈值不同（8 和 6），中间留有缓冲，避免频繁树化和去树化带来的抖动。
3.5 迭代器与 Spliterator 的适配
由于引入了红黑树，HashMap 的迭代器（如 KeyIterator、ValueIterator、EntryIterator）以及 Java 8 新增的 Spliterator 都需要同时支持链表和树的遍历。TreeNode 本身是 Node 的子类，因此迭代器可以通过 nextNode 方法统一遍历，但树的遍历需要额外处理（树节点也有 next 指针，维护着链表顺序）。
4. Java 8 HashMap 源码深度剖析
为了更深入地理解上述改进，我们直接分析 Java 8 中 HashMap 的核心源码片段。
4.1 基本属性定义
java
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; // ... }
4.2 节点定义
链表节点 Node<K,V>：
java
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）。这种设计使得树节点既能作为红黑树节点，又能作为链表节点，简化了遍历。
4.3 hash 方法
java
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 位有效，如果哈希值的高位变化而低位不变，就容易冲突。通过扰动，使低位也能混合高位的信息，降低碰撞概率。
4.4 put 方法流程
put(K key, V value) 实际调用 putVal 方法：
java
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) // -1 for 1st 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; }
关键点：
- 插入新节点时，如果链表长度达到 7（binCount 从 0 开始，到 7 时意味着链表已有 8 个节点），会调用
treeifyBin尝试树化。 treeifyBin内部会检查数组长度是否小于 64，若是则进行扩容（resize），否则才真正执行链表到树的转换。
4.5 treeifyBin 方法
java
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 指针，形成双向链表，方便后续遍历和去树化。
4.6 resize 扩容方法
扩容方法相对复杂，这里只分析关键部分，特别是元素迁移的优化：
java
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)来区分高低位，避免重新计算哈希值。 - 链表拆分时，保持了原来的顺序（尾插法），因此不会出现 Java 7 中的链表反转。
- 红黑树的拆分通过
split方法完成，类似于链表的拆分，但需要根据节点数决定是否需要去树化。
4.7 get 方法流程
java
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)。
5. 性能对比与分析
5.1 最坏情况下的性能提升
在极端哈希冲突的情况下，Java 7 的 HashMap 会退化为链表，查找复杂度 O(n)。假设有 10,000 个元素全部映射到同一个桶，一次查找需要遍历整个链表，耗时与元素数量成正比。而在 Java 8 中，当链表长度超过 8 且数组足够大时，链表会转换为红黑树，查找复杂度降为 O(log n)，10,000 个元素时最多比较 14 次，性能提升显著。
5.2 平均性能
在正常哈希分布下，大多数桶的链表长度很短（0 或 1），此时 Java 8 的额外开销仅在于判断节点类型（是否是 TreeNode）和可能的一两次扰动计算，与 Java 7 相比差别不大。但由于红黑树的引入，内存占用略有增加（每个树节点比链表节点多存储 parent、left、right、red 等字段），但考虑到现代服务器内存容量，这点开销通常可以接受。
5.3 扩容性能
Java 8 的扩容不再重新计算哈希值，仅通过位运算判断新位置，效率更高。同时尾插法避免了死循环，但这也导致多线程环境下仍可能丢失数据（因为多个线程修改共享数组），所以 HashMap 依然不是线程安全的。
6. 线程安全与并发问题
Java 8 的 HashMap 解决了 Java 7 中并发扩容导致死循环的问题，因为尾插法不会形成环。但这并不意味着 HashMap 可以在多线程环境下安全使用。例如：
- 两个线程同时执行 put 操作，可能都发现桶为空，然后各自插入自己的节点，导致数据覆盖。
- 扩容时多个线程同时修改 table 引用，可能导致数据丢失。
- 迭代器仍然是 fail-fast 的，如果在迭代过程中被其他线程修改，会抛出 ConcurrentModificationException。
因此，在多线程环境中，应使用 ConcurrentHashMap、Collections.synchronizedMap 或 Hashtable。特别地，Java 8 也对 ConcurrentHashMap 进行了大量优化，引入了红黑树和 CAS 操作，性能大幅提升。
7. 其他细节变化
7.1 键和值的 null 处理
与 Java 7 一样，Java 8 的 HashMap 允许一个 null 键和多个 null 值。null 键的哈希值为 0，因此总是存放在 table[0] 桶中。
7.2 初始容量与负载因子
最佳实践：如果已知存储元素数量，应指定初始容量，避免频繁扩容。负载因子的默认值 0.75 是时间和空间成本的折中，一般不建议修改。
7.3 迭代顺序
HashMap 不保证迭代顺序，但随着 Java 8 的改进，由于链表尾插法，在扩容后链表顺序保持不变，但红黑树的存在使得迭代顺序更加复杂。总体而言，不应依赖 HashMap 的迭代顺序。
7.4 新增的 API
Java 8 为 Map 接口添加了一些默认方法，如 getOrDefault、putIfAbsent、remove（键值对）、replace 等，HashMap 实现了这些方法，方便了开发。
8. 总结：Java 8 HashMap 的改进与不足
改进点：
- 引入红黑树，解决链表过长导致的性能问题，将最坏情况时间复杂度从 O(n) 降到 O(log n)。
- 优化哈希算法，简化计算同时保持低位随机性。
- 改进扩容机制，采用位运算判断新位置，避免重新计算哈希，且使用尾插法消除死循环风险。
- 引入树化阈值和去树化阈值，平衡时间和空间。
- 增加新的实用方法，提升 API 友好性。
仍然存在的问题：
- 非线程安全，并发环境下仍需使用 ConcurrentHashMap。
- 内存占用：红黑树节点比链表节点更占内存，但在大多数情况下可接受。
- 树化条件限制：当数组长度较小时，即使链表很长也不树化，而是先扩容，这可能导致在特定场景下性能下降（例如数组大小固定为 16 且无法扩容时，链表会一直很长）。不过这种情况较少见。
9. 面试常见问题与回答思路
- Q：Java 8 中 HashMap 为什么要引入红黑树？
A：为了防止哈希冲突严重时链表过长，导致查找效率低下。红黑树能够提供 O(log n) 的查找性能，而链表是 O(n)。通过设置阈值，只在必要时树化，平衡性能与空间。 - Q：树化阈值为什么是 8？
A：根据泊松分布，在理想随机哈希码下，链表长度达到 8 的概率已经非常低（约 0.00000006），因此将 8 作为阈值可以在保证性能的同时避免过度树化。同时，如果数组长度小于 64，会优先扩容，因为扩容能更好地分散数据。 - Q：Java 8 中 HashMap 是如何解决扩容死循环问题的？
A：Java 8 改用尾插法，且扩容时不会改变链表顺序，因此不会形成环形链表。但 HashMap 本身仍不是线程安全的，多线程下仍可能出现数据丢失等问题。 - Q：Java 8 的 HashMap 扩容时如何确定元素新位置？
A：通过hash & oldCap判断，如果结果为 0 则留在原索引，否则移动到“原索引 + oldCap”。这是因为扩容后容量变为 2n，索引计算掩码新增了最高位，而该位的值正是 hash 在 oldCap 对应位上的值。 - Q：HashMap 的哈希函数为什么要高 16 位异或低 16 位？
A：为了使高位也能参与数组下标计算，减少冲突。因为数组下标由 hash 的低 n 位决定，如果哈希值的高位变化而低位相同，容易发生碰撞。通过异或，将高位的特征混合到低位，提高散列性。 - Q：HashMap 和 ConcurrentHashMap 在 Java 8 中的改进有何异同？
A：两者都引入了红黑树，但 ConcurrentHashMap 在 Java 8 中采用了 CAS + synchronized 实现更细粒度的并发控制，并取消了分段锁，结构更简单，并发性能更好。
10. 结语
Java 8 对 HashMap 的重构是一次经典的性能优化案例，它不仅解决了旧版本中存在的缺陷，还为后续的集合框架演进奠定了基础。
