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

hashtable hashmap java hash

2022-09-01 01:35:39

当我看到以下内容时，我正在浏览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 的幂？

此外，当执行自动重述时，究竟会发生什么？哈希函数是否也已更改？

答案 1

映射必须确定要对任何给定键使用哪个内部表索引，将任何值（可以是负数）映射到范围中的值。当是二的幂时，可以非常便宜地完成 - 并且是，在：int[0, table.length)table.lengthindexFor

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

使用不同的表长度，您需要计算余数并确保其为非负数。这绝对是一个微优化，但可能是一个有效的:)

此外，当执行自动重述时，究竟会发生什么？哈希函数是否也已更改？

我不太清楚你的意思。使用相同的哈希代码（因为它们只是通过调用每个键来计算），但由于表长度的变化，它们在表中的分布会有所不同。例如，当表长度为 16 时，哈希代码 5 和 21 最终都存储在表条目 5 中。当表长度增加到 32 时，它们将位于不同的条目中。hashCode

答案 2

理想的情况实际上是对的支持数组使用质数大小。这样，您的密钥将更自然地分布在阵列中。然而，这与mod division一起工作，并且随着Java的每个版本，该操作变得越来越慢。从某种意义上说，2 方法的幂是你能想象到的最差的表大小，因为使用较差的哈希码实现更有可能在数组中产生关键的 collosion。HashMap

因此，您将在Java的实现中找到另一个非常重要的方法，即，它可以补偿较差的哈希码。HashMaphash(int)