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

问题描述

  //默认的初始容量 - 必须是一个两个幂。 
 static final int DEFAULT_INITIAL_CAPACITY = 16; 
  

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

  int capacity = 1; 
 while（容量容量<= 1; 
  

为什么容量必须是2的乘方？

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

解决方案

映射必须确定哪个内部表索引可用于任何给定的键，映射在 [0，table.length）范围内的任何 int 值（可能为负值）。当 table.length 是2的幂时，可以很便宜地完成 indexFor

  static int indexFor（int h，int length）{
 return h& （长度-1）; 
 
 
 
 
 
 $ b 
使用不同的表长度，你需要计算余数并使肯定它是非负面的。这绝对是一个微型优化，但可能是一个有效的优化：）
 
 
 
 
另外，当执行自动刷新时，会发生什么？哈希函数是否也改变了？
 
 
我不清楚你的意思。使用相同的哈希码（因为它们只是通过在每个键上调用 hashCode 来计算），但是由于表长度的改变，它们将在表内以不同方式分布。例如，当表长度为16时，5和21的散列码最终都会存储在表条目5中。当表长度增加到32时，它们将位于不同的条目中。
 
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;
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;
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?
解决方案
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?
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屋！