为什么 HashMap 要求初始容量是 2 的幂? [英] Why does HashMap require that the initial capacity be a power of two?

问题描述

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

I was going through Java's HashMap source code when I saw the following

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

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

My question is why does this requirement exists in the first place? I also see that the constructor which allows creating a HashMap with a custom capacity converts it into a power of two:

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

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

Why does the capacity always has to be a power of two?

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

Also, when automatic rehashing is performed, what exactly happens? Is the hash function altered too?

推荐答案

映射必须计算出任何给定键使用哪个内部表索引，映射任何 int 值(可能是负数)到 [0, table.length) 范围内的值.当 table.length 是 2 的幂时，这可以真正便宜地完成 - 而且在 indexFor 中:

The map has to work out which internal table index to use for any given key, mapping any int value (could be negative) to a value in the range [0, table.length). When table.length is a power of two, that can be done really cheaply - and is, in indexFor:

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

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

With a different table length, you'd need to compute a remainder and make sure it's non-negative . This is definitely a micro-optimization, but probably a valid one :)

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

Also, when automatic rehashing is performed, what exactly happens? Is the hash function altered too?

我不太清楚你的意思.使用相同的哈希码(因为它们只是通过在每个键上调用 hashCode 来计算的)，但由于表长度的变化，它们在表中的分布不同.例如，当表长为16时，5和21的hash码最终都存放在表项5中.当表长增加到32时，它们将在不同的表项中.

It's not quite clear to me what you mean. The same hash codes are used (because they're just computed by calling hashCode on each key) but they'll be distributed differently within the table due to the table length changing. For example, when the table length is 16, hash codes of 5 and 21 both end up being stored in table entry 5. When the table length increases to 32, they will be in different entries.

这篇关于为什么 HashMap 要求初始容量是 2 的幂?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！