面试题：Java集合框架之HashMap源码与性能

Question

请简述Java中HashMap的底层数据结构，以及在扩容时具体的操作过程，同时分析扩容对其性能的影响。

Answer 1

HashMap的底层数据结构

HashMap底层是由数组加链表（JDK 1.7及之前）或数组加链表加红黑树（JDK 1.8及之后）组成。

1. 数组：数组的每个元素是一个Node（JDK 1.8 ）或Entry（JDK 1.7 ）对象，数组的大小始终是2的幂次方。
2. 链表：当发生哈希冲突（即不同的键计算出相同的哈希值）时，多个Node/Entry会以链表的形式存储在数组的同一个位置。
3. 红黑树：JDK 1.8中，当链表长度大于等于8且数组容量大于等于64时，链表会转化为红黑树，以提高查找效率。

扩容时具体的操作过程

1. 判断是否需要扩容：当HashMap中的元素个数（size）超过阈值（threshold = capacity * loadFactor）时，就会触发扩容。
2. 创建新的数组：新数组的容量是原来的2倍。例如，原来容量为16，新容量则变为32 。
3. 重新计算哈希值并迁移数据：
   • JDK 1.7：对每个Node/Entry进行重新哈希计算，将其放入新数组的相应位置。由于哈希算法的变化，原链表顺序可能发生变化，会出现链表倒置的情况。
   • JDK 1.8：当链表长度小于等于6时，直接将链表复制到新数组的对应位置；当链表长度大于6时，先判断是否需要转化为红黑树，然后根据哈希值的高位是否为1，将链表拆分成两个链表，分别放入新数组的不同位置，这样能减少重新哈希计算的开销，且不会出现链表倒置的问题。

扩容对其性能的影响

1. 时间性能：扩容过程中，重新计算哈希值和迁移数据需要消耗时间，特别是数据量较大时，扩容操作会比较耗时，导致put、get等操作的性能下降。不过，扩容后哈希冲突的概率降低，后续操作的平均时间复杂度会趋近于理想的O(1) 。
2. 空间性能：扩容会导致HashMap占用更多的内存空间，因为新数组的容量比原来大。但合理的扩容可以减少哈希冲突，提高空间利用率，避免因链表过长导致的内存浪费。