面试题：Java中HashMap扩容时元素的重新分布机制是什么

Question

请描述在Java的HashMap进行扩容操作时，原HashMap中的元素是如何重新分布到新的更大的数组中的，结合哈希算法和扩容的相关逻辑进行阐述。

Answer 1

1. 哈希算法基础：
   • 在Java的HashMap中，元素的存储位置是通过哈希算法计算得到的。具体来说，先对键对象调用hashCode()方法得到一个哈希码值，然后通过HashMap内部的hash()方法进一步处理这个哈希码。hash()方法的目的是为了让哈希码更加分散，减少哈希冲突。例如JDK 8中的hash()方法代码如下：

   static final int hash(Object key) {
       int h;
       return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
       // 这里通过异或操作让高位和低位信息都参与计算，使得哈希值分布更均匀
   }
   

   • 得到最终的哈希值后，通过取模运算（在HashMap中实际使用&运算代替取模，因为数组长度是2的幂次方，hash & (length - 1)等价于hash % length）来确定元素在数组中的存储位置，即index = hash & (length - 1)。
2. 扩容逻辑：
   • 当HashMap中的元素数量达到阈值（threshold = capacity * loadFactor）时，就会触发扩容操作。扩容是将原来的数组容量扩大为原来的2倍。例如，原来数组容量是16，扩容后变为32。
3. 元素重新分布：
   • 扩容后，原HashMap中的元素需要重新计算在新数组中的位置。因为数组容量变为原来的2倍，即newLength = oldLength * 2，所以newLength - 1的二进制表示比oldLength - 1多了一位。
   • 假设原来数组容量oldLength = 16（二进制10000），oldLength - 1 = 15（二进制1111），扩容后newLength = 32（二进制100000），newLength - 1 = 31（二进制11111）。
   • 对于原数组中的每个元素，其在新数组中的位置要么保持不变，要么移动到原位置加上原数组长度的位置。原因是新的取模运算（&运算）结果与原来相比，只有新增的那一位可能会影响结果。
   • 例如，原哈希值hash = 00110111，oldIndex = hash & (oldLength - 1) = 00110111 & 1111 = 0111，新数组中newIndex = hash & (newLength - 1) = 00110111 & 11111，如果新增位是0，newIndex与oldIndex相同；如果新增位是1，newIndex = oldIndex + oldLength。
   • 在JDK 8中，HashMap扩容时采用了更高效的方式，将链表节点按新增位是0还是1分为两个链表（分别叫做低位链表和高位链表），低位链表的节点在新数组中的位置不变，高位链表的节点在新数组中的位置为原位置加上原数组长度。这样减少了重新计算哈希值和移动元素的开销。