意義

Question

可能性の重複：
Java HashMap Default Initial Capacity

私はjava.util.HashMapをでのHashMapの実装を読んでいました。初期容量、最大容量などは2の累乗です。 java.util.HashMapを

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


/** 
* The maximum capacity, used if a higher value is implicitly specified 
* by either of the constructors with arguments. 
* MUST be a power of two <= 1<<30. 
*/ 
static final int MAXIMUM_CAPACITY = 1 << 30; 


/** 
* The table, resized as necessary. Length MUST Always be a power of two. 
*/ 
transient Entry[] table; 

コメントからコピーされた宣言の

部品のサイズは、2の累乗でなければならない示唆しています。なぜ2つのパワーが重要なのですか？

Answer 1

2の累乗を使用すると、実装が簡単になり、パフォーマンスが向上します。

など。ハッシュコードからバケットを見つけるにはabs(hash) % SIZE

Answer 2

の代わりに理論的に言えば、マップの要素数が増えるにつれて操作が無視できるほど小さくなる場合のみ、リストを展開するコストを償却することができます。負荷率に達するたびにサイズを2倍にすることは、エントリの展開と再読み込みが償却されることを保証する1つの方法です。

要素をハッシュすると、結果の整数（32ビット）を最初のkビットに切り捨てることができるので、kはlog（N）です。 Nは現在の容量です。