Bedeutung von "Potenz von 2" in java.util.HashMap Implementierung

Question

Mögliche Duplizieren:
Java HashMap Default Initial Capacity

Ich war die Umsetzung der HashMap in java.util.HashMap lesen. Die Anfangskapazität, die maximale Kapazität usw. sind Zweierpotenzen.

Teile der Deklaration kopiert von 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; 

Die Kommentare deuten die Größen eine Zweierpotenz sein muss. Warum wird Zweierpotenz so wichtig?

Answer 1

Die Verwendung von Zweierpotenzen vereinfacht die Implementierung und verbessert die Leistung.

z. einen Eimer aus einem Hash-Code zu finden, es hash & (SIZE -1) statt abs(hash) % SIZE

Answer 2

Theoretisch verwenden können, können wir die Kosten für die Erweiterung der Liste nur dann, wenn der Betrieb vernachlässigbar, wenn die Anzahl der Elemente in der Karte erhöht sich amortisieren. Die Verdoppelung der Größe bei jedem Erreichen des Lastfaktors ist eine Möglichkeit, um die Erweiterung und das erneute Laden von Einträgen zu amortisieren.

Der Grund, warum es zunächst eine Potenz von zwei ist, ist so, dass beim Hashing eines Elements die resultierende Ganzzahl (32-Bit) auf die ersten k-Bits abgeschnitten werden kann, wobei k der Log (N) ist wo N ist die aktuelle Kapazität.