significato di "potenza di 2" nell'attuazione java.util.HashMap

Question

Eventuali duplicati:
Java HashMap Default Initial Capacity

stavo leggendo l'attuazione di HashMap in java.util.HashMap. La capacità iniziale, la capacità massima ecc. Sono due potenze.

Parti dichiarazione copiati da 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; 

I commenti indicano le dimensioni deve essere una potenza di due. Perché il potere di due ha tanta importanza?

Answer 1

L'utilizzo delle potenze di due semplifica l'implementazione e migliora le prestazioni.

E.g. per trovare un secchio da un codice hash può usare al posto di hash & (SIZE -1)abs(hash) % SIZE

Answer 2

Teoricamente parlando, siamo in grado di ammortizzare il costo di ampliare l'elenco solo se l'operazione diventa trascurabile, come il numero di elementi nella mappa aumenta. Raddoppiare le dimensioni ogni volta che viene raggiunto il fattore di carico è un modo per garantire l'espansione e il ricaricamento delle voci viene ammortizzato.

Il motivo per cui inizialmente è specificamente una potenza di due è che quando abbiamo un elemento hash, il numero intero risultante (32 bit) può essere troncato ai primi k-bit, dove k è il log (N) dove N è la capacità attuale.