面试题：Java中HashMap扩容机制的基本原理是什么

Question

请简述Java中HashMap扩容机制的基本原理，包括何时会触发扩容以及扩容过程中对数据的处理方式。

Answer 1

1. 何时触发扩容

• 负载因子与容量：HashMap 中有两个关键参数影响扩容，分别是负载因子（load factor）和当前容量（capacity）。默认的负载因子为 0.75，当 HashMap 中存储的键值对数量（size）达到当前容量（capacity）与负载因子（load factor）的乘积时，就会触发扩容。例如，当前容量为 16，负载因子为 0.75，那么当 size 达到 16 * 0.75 = 12 时，就会触发扩容。

2. 扩容过程中对数据的处理方式

• 创建新的数组：扩容时，会创建一个新的数组，新数组的容量是原来数组容量的两倍。例如原来容量为 16，扩容后容量变为 32。
• 重新计算哈希值与位置：对于原数组中的每个键值对，会重新计算其在新数组中的位置。在 JDK 1.7 及之前，需要重新计算哈希值并通过哈希值与新容量取模来确定新位置。而在 JDK 1.8 中，利用元素的哈希值和原数组容量进行比较，如果哈希值和原数组容量按位与结果为 0，则元素在新数组中的位置和原数组相同；如果结果不为 0，则新位置是原位置加上原数组容量。这种方式减少了重新计算哈希值的开销，提高了扩容效率。例如原数组容量为 16（二进制 10000），某个元素哈希值为 10101，10101 & 10000 = 10000，不为 0，若原位置为 5，新位置则为 5 + 16 = 21 。
• 迁移数据：将原数组中的键值对迁移到新数组对应的位置上。在 JDK 1.7 中，迁移过程采用头插法，在多线程环境下可能会形成环形链表，导致死循环。而 JDK 1.8 采用尾插法，避免了这个问题。