7

重複の可能性:
Java HashMap のデフォルトの初期容量

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 のべき乗がそれほど重要視されるのでしょうか。

4

2 に答える 2

17

2 の累乗を使用すると、実装が簡素化され、パフォーマンスが向上します。

hash & (SIZE -1)たとえば、代わりに使用できるハッシュコードからバケットを見つけるにはabs(hash) % SIZE

于 2012-05-17T08:55:49.043 に答える
1

理論的に言えば、マップ内の要素の数が増加するにつれて操作が無視できるようになる場合にのみ、リストを拡張するコストを償却できます。ロード ファクターに達するたびにサイズを 2 倍にすることは、エントリの拡張と再ロードを償却する 1 つの方法です。

最初に具体的に 2 の累乗である理由は、要素をハッシュするときに、結果の整数 (32 ビット) を最初の k ビットに切り捨てることができるようにするためです。ここで、k は対数 (N) であり、N は現在の容量。

于 2012-05-17T09:04:31.533 に答える