面试题：Java中HashMap的工作原理简述

Question

请简要阐述Java中HashMap的工作原理，包括如何存储键值对、哈希冲突如何解决、扩容机制是怎样的。

Answer 1

存储键值对

1. 哈希计算：HashMap使用键对象的hashCode()方法计算哈希值，该哈希值会经过一系列处理（如扰动函数）得到最终的哈希值，用于确定键值对在数组中的存储位置（桶索引）。
2. 存储位置确定：通过哈希值对数组长度取模（hash & (length - 1)，在Java 8及之后，使用这种更高效的按位与运算替代取模），得到的结果就是键值对要存储到数组中的索引位置。如果该位置为空，直接将键值对存入；如果不为空，会形成链表（Java 8之前）或红黑树（Java 8及之后，当链表长度大于8且数组长度大于64时转为红黑树）来存储多个键值对。

哈希冲突解决

1. 链表法：Java 8之前，当发生哈希冲突（不同键计算出相同的数组索引）时，新的键值对会以链表的形式链接到该索引位置已有的节点之后。遍历链表来查找特定键值对时，需要依次比较链表节点的键。
2. 红黑树优化：Java 8及之后，为了提升哈希冲突时查找效率，当链表长度大于8且数组长度大于64时，链表会转换为红黑树。红黑树具有自平衡特性，查找、插入和删除操作平均时间复杂度为O(log n)，相比于链表的O(n)效率更高。当红黑树节点数量小于6时，又会退化为链表。

扩容机制

1. 扩容条件：当HashMap中的元素数量（size）达到负载因子（loadFactor，默认0.75）与当前数组容量（capacity）的乘积时，就会触发扩容。例如，初始容量为16，负载因子为0.75，当元素数量达到16 * 0.75 = 12时，就会进行扩容。
2. 扩容过程：扩容时，新的数组容量是原来的2倍。然后重新计算每个键值对在新数组中的位置并重新分配，这个过程称为“重新哈希”。虽然重新哈希开销较大，但通过这种方式可以减少哈希冲突，提升HashMap的性能。