面试题：Java中HashMap如何通过初始容量优化性能

Question

在Java的HashMap中，初始容量的设置对性能有重要影响。请阐述如何根据预估数据量合理设置初始容量以优化HashMap的性能，并举例说明如果初始容量设置不当可能会引发什么问题。

Answer 1

合理设置初始容量优化性能

1. 计算方式：在Java的HashMap中，当我们能够预估数据量时，为了避免频繁的扩容操作带来的性能损耗，应根据如下公式来设置初始容量：
   • 假设预估数据量为n，理想情况下，HashMap的初始容量initialCapacity应该设置为大于等于n且最接近n的2的幂次方数。可以使用(int) Math.ceil(n / 0.75f) & (Integer.MAX_VALUE - 1) 来计算合适的初始容量（0.75f是HashMap默认的负载因子）。
   • 例如，如果预估数据量n为100，(int) Math.ceil(100 / 0.75f) = 134，134 & (Integer.MAX_VALUE - 1) 得到128，128是2的7次方，这就是合适的初始容量。
2. 原理：HashMap在元素数量达到负载因子（默认0.75）与容量的乘积时会进行扩容。扩容操作涉及到重新计算哈希值、重新分配元素到新的桶数组等操作，开销较大。通过合理设置初始容量，可以减少扩容次数，提高性能。

初始容量设置不当引发的问题

1. 初始容量过大：
   • 浪费内存：如果初始容量设置得比实际数据量所需大很多，会造成大量的内存浪费。例如，预估数据量为10，但设置初始容量为1024。这意味着HashMap会预先分配一个长度为1024的桶数组，大部分桶在很长时间内甚至整个生命周期内都可能为空，占据了不必要的内存空间。
2. 初始容量过小：
   • 频繁扩容：若初始容量设置过小，当元素数量快速增长达到负载因子与容量的乘积时，HashMap会频繁进行扩容。例如，初始容量设为16，假设负载因子为0.75，当元素数量达到12时就会扩容。频繁扩容导致大量的元素重新哈希和重新分配，严重影响性能，使得插入、查找等操作的时间复杂度上升，效率降低。