摘要：我们来详细讲解JDK 1.7 的 HashMap 数组扩容原理。JDK 1.7 和 JDK 1.8 在 HashMap 的扩容机制上有一些重要的区别，理解 JDK 1.7 的扩容方式有助于对比学习，并了解 HashMap 的演进过程。
我们来详细讲解 JDK 1.7 的 HashMap 数组扩容原理。JDK 1.7 和 JDK 1.8 在 HashMap 的扩容机制上有一些重要的区别，理解 JDK 1.7 的扩容方式有助于对比学习，并了解 HashMap 的演进过程。
JDK 1.7 HashMap 扩容概述
在 JDK 1.7 中，HashMap 的底层数据结构仍然是 数组 + 链表。当 HashMap 中存储的键值对数量达到一定程度时，为了保证性能，需要对底层的数组进行扩容。扩容的主要目的是：
减少哈希冲突: 扩容后，数组容量变大，键值对会重新分布到更多的桶中，从而降低哈希冲突的概率，减少链表长度，提高查找效率。提高性能: 通过减少哈希冲突，HashMap 的 get, put 等操作的平均时间复杂度可以保持接近 O(1)。JDK 1.7 HashMap 扩容的关键步骤
JDK 1.7 的 HashMap 扩容主要涉及以下几个关键步骤：
扩容触发条件: 判断是否需要扩容。计算新的容量: 确定扩容后的新数组容量。创建新的数组: 根据新的容量创建新的数组。Rehash (重新哈希): 将旧数组中的所有键值对重新计算哈希值，并根据新的数组容量计算新的索引位置。迁移数据: 将旧数组中的键值对迁移到新的数组中对应的索引位置。我们来逐个步骤详细分析 JDK 1.7 的源码实现 (基于 JDK 1.7 的 HashMap 源码):
1. 扩容触发条件 (在 put 操作中检查)
在 JDK 1.7 的 HashMap 中，扩容的触发条件主要在 put 方法中进行检查。每次 put 操作成功添加一个键值对后，都会检查当前 HashMap 的大小 (size) 是否超过了扩容阈值 (threshold).
java复制代码 public V put(K key, V value) {// ... 省略部分代码 ...if (size >= threshold) { // 检查是否需要扩容resize(2 * table.length); // 调用 resize 方法进行扩容，新的容量通常是原来的 2 倍return put(key, value); // 扩容后，需要重新 put 当前的键值对 (因为 rehash 后索引可能改变)}createEntry(hash, key, value, bucketIndex); // 创建 Entry 并添加到链表头部return null;}size >= threshold: size 是 HashMap 中键值对的数量，threshold 是扩容阈值。当 size 大于等于 threshold 时，就会触发扩容。resize(2 * table.length): 调用 resize 方法进行扩容，参数 2 * table.length 表示新的容量通常是当前数组容量的两倍。return put(key, value): 扩容后，由于数组容量改变，所有键值对都需要重新计算索引位置 (rehash)。为了确保当前 put 操作的键值对也能正确地放入新的数组中，put 方法会递归调用自身，重新执行 put 操作。2. 计算新的容量 (在 resize 方法中)
resize(int newCapacity) 方法负责计算新的容量。在 JDK 1.7 中，新的容量通常是 当前容量的两倍。
java复制代码 void resize(int newCapacity) {Entry oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) { // 如果旧容量已经达到最大容量，则不再扩容threshold = Integer.MAX_VALUE;return;}Entry newTable = new Entry[newCapacity]; // 创建新的 Entry 数组，容量为 newCapacitytransfer(newTable); // 调用 transfer 方法将旧数组的数据迁移到新数组table = newTable; // 将新数组赋值给 table，替换旧数组threshold = (int)(newCapacity * loadFactor); // 重新计算扩容阈值}int newCapacity: resize 方法接收一个 int newCapacity 参数，表示新的容量。在 put 方法中调用 resize 时，通常传入 2 * table.length，即当前容量的两倍。Entry oldTable = table; int oldCapacity = oldTable.length;: 保存旧的数组 table 和旧的容量 oldCapacity。if (oldCapacity == MAXIMUM_CAPACITY): 如果旧容量已经达到 HashMap 的最大容量 MAXIMUM_CAPACITY (通常是 2^30)，则不再进行扩容，只将 threshold 设置为 Integer.MAX_VALUE，阻止后续的扩容操作。Entry newTable = new Entry[newCapacity];: 创建一个新的 Entry 数组 newTable，容量为 newCapacity。transfer(newTable);: 调用 transfer 方法，将旧数组 oldTable 中的所有键值对迁移到新数组 newTable 中。这是扩容的核心步骤。table = newTable;: 将新创建的数组 newTable 赋值给 HashMap 的 table 成员变量，替换掉旧的数组 oldTable。threshold = (int)(newCapacity * loadFactor);: 根据新的容量 newCapacity 和负载因子 loadFactor，重新计算扩容阈值 threshold。3. Rehash 和数据迁移 (在 transfer 方法中)
transfer(Entry newTable) 方法负责将旧数组 table 中的所有键值对 重新哈希 (rehash) 并迁移到新的数组 newTable 中。JDK 1.7 的 transfer 方法是单线程的，并且在多线程环境下扩容可能会导致死循环 (JDK 1.7 HashMap 的一个著名问题)。
java复制代码 void transfer(Entry newTable) {Entry src = table; // src 指向旧数组int newCapacity = newTable.length;for (int j = 0; j e = src[j]; // e 指向旧数组当前桶的链表头节点if (e != null) {src[j] = null; // 将旧数组当前桶置空，方便 GC 回收do {Entry next = e.next; // 保存当前节点的下一个节点int i = indexFor(e.hash, newCapacity); // 重新计算当前节点在新数组中的索引位置e.next = newTable[i]; // 将当前节点的 next 指向新数组 i 位置的链表头节点 (头插法)newTable[i] = e; // 将当前节点 e 设置为新数组 i 位置的链表头节点e = next; // e 指向下一个节点，继续处理链表} while(e != null);}}}Entry src = table; int newCapacity = newTable.length;: src 指向旧数组 table，newCapacity 是新数组的容量。Entry e = src[j];: e 指向旧数组 src 的索引 j 位置的链表的头节点。if (e != null): 如果当前桶 src[j] 不为空 (即存在链表)。src[j] = null;: 将旧数组 src 的当前桶 src[j] 置为 null，目的是断开旧数组对链表的引用，方便垃圾回收器 (GC) 回收旧数组中的链表节点。do { ... } while(e != null);: 遍历旧数组当前桶 src[j] 的链表。Entry next = e.next;: 保存当前节点 e 的下一个节点 next，因为在迁移过程中会修改 e.next 指针。int i = indexFor(e.hash, newCapacity);: 重新计算当前节点 e 在新数组 newTable 中的索引位置 i。indexFor(e.hash, newCapacity) 方法使用 (newCapacity - 1) & e.hash 位运算来计算索引，与 HashMap 的哈希寻址算法相同。e.next = newTable[i];: 将当前节点 e 的 next 指针指向新数组 newTable 的索引 i 位置的链表的头节点。如果 newTable[i] 原本为空，则 e.next 指向 null；如果 newTable[i] 原本已经有链表，则 e.next 指向原链表的头节点。这里使用的是头插法 (头插法在 JDK 1.7 中会导致多线程并发扩容时可能出现循环链表的问题)。newTable[i] = e;: 将当前节点 e 设置为新数组 newTable 的索引 i 位置的链表的头节点。e = next;: 将 e 指向下一个节点 next，继续处理链表的下一个节点。4. indexFor(int h, int length) 方法 (计算索引)
indexFor(int h, int length) 方法用于根据哈希值 h 和数组长度 length 计算索引位置。
java复制代码 static int indexFor(int h, int length) {return h & (length-1); // 位运算，等价于 h % length (当 length 为 2 的幂次方时)}h & (length-1): 使用位运算 & 计算索引。当 length 为 2 的幂次方时，h & (length-1) 等价于 h % length，但位运算效率更高。JDK 1.7 扩容的特点和潜在问题
多线程并发扩容可能导致死循环 (JDK 1.7 HashMap 的著名问题): 在多线程环境下，如果多个线程同时对 HashMap 进行 put 操作，并且触发了扩容，可能会导致多个线程同时执行 resize 和 transfer 操作。由于 JDK 1.7 的 transfer 方法使用头插法，并且没有进行线程安全控制，可能会导致链表成环，形成循环链表，从而在后续的 get 操作时，可能会进入死循环，导致 CPU 占用率飙升。这是 JDK 1.7 HashMap 在并发环境下最严重的问题。JDK 1.8 扩容的改进 (对比 JDK 1.7)
JDK 1.8 对 HashMap 的扩容机制进行了改进，主要体现在以下几个方面：
尾插法 (JDK 1.8): JDK 1.8 的 transfer 方法 (实际上在 JDK 1.8 中 transfer 方法的逻辑被融入到了 resize 方法中) 使用 尾插法 迁移链表节点。尾插法在多线程并发扩容时，不会改变链表的节点顺序，避免了循环链表的产生，解决了 JDK 1.7 的并发扩容死循环问题。引入红黑树: JDK 1.8 引入了红黑树来优化哈希冲突的处理。当链表长度超过阈值时，会将链表转换为红黑树，提高查找效率。红黑树的引入也使得 JDK 1.8 的 HashMap 在哈希冲突严重的情况下，性能更加稳定。并发安全性 (ConcurrentHashMap): JDK 1.8 提供了线程安全的 ConcurrentHashMap 来替代 HashMap 在并发环境下的使用。ConcurrentHashMap 使用分段锁 (JDK 1.7) 或 CAS + synchronized (JDK 1.8) 等机制来保证线程安全，并且在扩容时也进行了并发优化，避免了 JDK 1.7 的并发扩容问题。总结：JDK 1.7 HashMap 扩容原理
JDK 1.7 的 HashMap 扩容主要包括以下步骤：
触发条件: 当 HashMap 的键值对数量 size 超过扩容阈值 threshold 时触发。计算新容量: 新容量通常是当前容量的两倍。创建新数组: 创建新的 Entry 数组，容量为新容量。Rehash 和迁移 (transfer 方法): 遍历旧数组的每个桶，对每个桶的链表进行 rehash，重新计算每个节点在新数组中的索引位置，并使用 头插法 将节点迁移到新数组的对应位置。更新引用和阈值: 将 HashMap 的 table 引用指向新数组，并重新计算扩容阈值。多线程并发扩容可能导致死循环: 由于 JDK 1.7 的 transfer 方法使用头插法，并且没有线程安全控制，在多线程并发扩容时，可能会导致循环链表，引发死循环问题。因此，在多线程环境下，绝对不能使用 JDK 1.7 的 HashMap。为了解决 JDK 1.7 HashMap 的并发问题和性能问题，JDK 1.8 对 HashMap 进行了重大改进，引入了红黑树、尾插法等优化，并提供了线程安全的 ConcurrentHashMap。在实际开发中，应该优先使用 JDK 1.8 或更高版本的 HashMap 或 ConcurrentHashMap。
来源：孙青讲一下