为什么HashMap要求初始容量是2的幂次？

Question

我正想通过Java的HashMap的源代码，当我看到下面

//The default initial capacity - MUST be a power of two. 
static final int DEFAULT_INITIAL_CAPACITY = 16; 

我的问题是，为什么摆在首位不存在这个要求？我也看到，它允许使用自定义能力创建一个HashMap构造函数将其转换成二的幂：

int capacity = 1; 
while (capacity < initialCapacity) 
    capacity <<= 1; 

为什么总是有能力为二的幂？

此外，当执行自动重新刷新时，到底发生了什么？哈希函数是否也改变了？

Answer 1

该映射必须计算出哪个内部表索引可用于任何给定键，将任何int值（可能为负）映射到[0, table.length)范围内的值。当table.length是两个电源，可以做真的便宜 - 并且是在indexFor：

static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

具有不同表的长度，你需要计算余数，并确保它的非负面的。这绝对是一个微型优化，但可能是一个有效的:)

此外，什么时候执行自动刷新，究竟发生了什么？哈希函数是否也改变了？

这对我来说不太清楚你的意思。使用相同的哈希码（因为它们只是通过在每个键上调用hashCode来计算），但是由于表长度的改变，它们将在表内以不同的方式分布。例如，当表长度为16时，5和21的散列码最终都会存储在表项5中。当表长度增加到32时，它们将处于不同的条目中。

Answer 2

理想情况实际上是使用素数大小作为HashMap的支持阵列。这样你的密钥将更自然地分布在阵列中。然而，这与mod分区协同工作，并且随着每个Java版本的发布，操作变得越来越慢。 从某种意义上说，2种方法的威力是您可以想象的最差的表格大小，因为糟糕的哈希码实现更有可能在阵列中产生关键的爆炸。

为此，你会发现在Java的HashMap实现，这是hash(int)，用于补偿差哈希码另一种非常重要的方法。