面试题：Java HashMap哈希算法中容量与哈希值计算的关系

Question

在Java的HashMap中，哈希算法的计算与HashMap的容量（capacity）之间存在怎样的关系？当容量发生变化（如扩容）时，哈希算法是如何重新调整元素存储位置的？

Answer 1

1. 哈希算法计算与容量的关系：
   • 在Java的HashMap中，哈希算法用于将键的哈希码（hashCode）映射到哈希表的特定位置。哈希算法的计算结果会与HashMap的容量相关。具体来说，通过将键的哈希码与HashMap容量减1（capacity - 1）进行按位与操作（&）来确定元素在哈希表中的存储位置，即index = hash & (capacity - 1) 。这样做是因为在HashMap中，容量（capacity）始终是2的幂次方，当capacity为2的幂次方时，capacity - 1的二进制表示为全1，按位与操作能确保计算出的索引值在0到capacity - 1的范围内，均匀地分布元素。
2. 容量变化（扩容）时哈希算法对元素存储位置的调整：
   • 当HashMap扩容时，新的容量是原来容量的2倍。由于容量变为原来的2倍，capacity - 1的二进制表示中多了一位1。例如，原来容量capacity为8（二进制1000），capacity - 1为7（二进制0111）；扩容后容量为16（二进制10000），capacity - 1为15（二进制1111）。
   • 对于原哈希表中的每个元素，重新计算其存储位置。假设原哈希值为hash，原索引为index = hash & (oldCapacity - 1) ，扩容后新索引计算为newIndex = hash & (newCapacity - 1) 。因为新容量是旧容量的2倍，所以新索引要么等于原索引，要么等于原索引加上旧容量。这是因为多出来的那一位（扩容后capacity - 1新增的最高位1）在按位与操作时，要么为0（此时新索引等于原索引），要么为1（此时新索引等于原索引加上旧容量）。所以在扩容时，不需要重新计算所有元素的哈希值，只需要根据新增的这一位来决定元素是留在原位置还是移动到原位置加上旧容量的新位置，从而提高了扩容的效率。