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

Question

当我看到以下内容时,我正在浏览Java的HashMap源代码

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

我的问题是为什么这个要求首先存在？我还看到允许创建具有自定义容量的HashMap的构造函数将其转换为2的幂:

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

为什么容量总是必须是2的幂？

此外,当执行自动重新散列时,究竟会发生什么？哈希函数也改变了吗？

Answer 1

映射必须计算出用于任何给定键的内部表索引,将任何int值(可能为负)映射到范围中的值[0, table.length).何时table.length是2的幂,这可以非常便宜地完成- 并且在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)，它可以补偿不良的哈希码。