面试题：Java中HashMap利用链地址法解决哈希冲突的原理

Question

请详细阐述在Java的HashMap中，当发生哈希冲突时，链地址法是如何工作的，包括数据结构的变化以及相关操作的流程。

Answer 1

1. 数据结构变化：
   • HashMap底层是数组加链表（JDK1.8 后引入红黑树优化）。数组的每个元素是一个链表的头节点。当发生哈希冲突时，即不同的键通过哈希函数计算得到相同的数组索引位置。此时，新的键值对会以链表节点的形式，被添加到该索引位置对应的链表中。例如，假设数组索引为i，已经有一个键值对(key1, value1)通过哈希计算映射到了该位置，此时又有一个键值对(key2, value2)也映射到位置i，那么(key2, value2)就会被添加到(key1, value1)所在链表的末尾（JDK1.8 前）或头部（JDK1.8 及以后）。
   • 当链表长度达到一定阈值（JDK1.8 中为 8）且数组容量达到一定大小（JDK1.8 中为 64）时，链表会转化为红黑树，以提高查找效率。这样，在该索引位置上的数据结构就从链表变成了红黑树。
2. 相关操作流程：
   • 插入操作：
     • 首先，通过键的hashCode()方法计算哈希值，然后经过HashMap内部的哈希算法处理，得到数组的索引位置。
     • 如果该索引位置没有元素，直接将键值对封装成节点放入该位置。
     • 如果该索引位置已有元素（即发生哈希冲突），则将新的键值对封装成节点，根据 JDK 版本不同，将节点添加到链表的头部（JDK1.8 前）或尾部（JDK1.8 及以后）。如果此时链表长度达到转化为红黑树的阈值（链表长度 >= 8 且数组容量 >= 64），则将链表转化为红黑树。
   • 查找操作：
     • 同样先计算键的哈希值，确定数组索引位置。
     • 如果该位置为空，直接返回null。
     • 如果该位置是链表，则从链表头开始遍历链表，逐个比较节点的键是否与要查找的键相等（通过equals方法）。如果找到相等的键，则返回对应的 value。
     • 如果该位置是红黑树，按照红黑树的查找方式查找，比较键值来找到对应的节点，返回其 value。
   • 删除操作：
     • 计算键的哈希值，确定数组索引位置。
     • 如果该位置为空，直接返回。
     • 如果是链表，从链表头开始遍历，找到要删除的节点，修改链表指针，跳过该节点。如果删除节点后链表长度小于 6（JDK1.8），且该红黑树的父节点也是红黑树，且节点数小于 6，那么红黑树会退化为链表。
     • 如果是红黑树，按照红黑树的删除算法删除节点。删除节点后，若红黑树节点数小于 6（JDK1.8），且该红黑树的父节点也是红黑树，红黑树会退化为链表。