Differenza tra nuova HashMap (int) e guava Maps.newHashMapWithExpectedSize (int)

Question

In Java, è possibile creare un nuovo HashMap per contenere un numero specifico di elementi in questo modo:

Map m = new HashMap(100); 

Guava fornisce un metodo Maps.newHashMapWithExpectedSize(int), che mi aspetterei di chiamare semplicemente HashMap(int). Ma non lo fa, invece calcola la propria capacità e la usa.

Perché lo newHashMapWithExpectedSize fa le sue cose e perché dovrei usarlo chiamando direttamente lo new HashMap(int)?

Answer 1

Hai letto il metodo Javadoc?

crea un'istanza HashMap, con una "capacità iniziale" abbastanza alto che dovrebbe detenere expectedSize elementi senza crescita.

Nota che il parametro "dimensione iniziale" del new HashMap(int) del costruttore specifica la dimensione iniziale della tabella di hash che le voci sono memorizzati in, che è fondamentalmente un dettaglio di implementazione che non si dovrebbero avere a cuore. La tabella hash verrà ridimensionata quando supera il fattore di carico della mappa (che per impostazione predefinita è 0,75), il che significa che se si specifica una capacità iniziale di 16 e quindi si aggiungono 16 voci alla mappa, la tabella hash verrà quasi certamente ridimensionata.

Con il metodo di Guava, se si specifica una dimensione atteso di 16 e poi aggiungere 16 voci, la tabella hash dovrebbe non ridimensionamento.

Answer 2

Guava semplicemente moltiplica la dimensione passata per 2 (in modo sicuro) e chiama il normale costruttore di hashmap. Ciò lo rende più scarso quindi ci sono meno collisioni durante l'hashing.

La javadoc sul calcolo della capacità indica che calcola un valore per la capacità in modo che l'hashmap sia tra il 25% e il 50% pieno, che è molto lontano dalla soglia che potrebbe innescare un ridimensionamento.

La libreria standard arrotonda la dimensione prevista fino alla potenza più vicina di 2 e la assegna come dimensione, quindi imposta la soglia per il ridimensionamento al 75%. Se avessimo chiesto casualmente delle taglie, la libreria standard si ridimensionerebbe nel 50% dei casi.

Se evitare la soglia sarebbe l'unica considerazione, moltiplicando con 1,34 sarebbe sufficiente disporre di spazio sufficiente per evitare il ridimensionamento sul riempimento con la dimensione prevista degli elementi.

Sembra il tipico rapporto velocità/spazio e gli ingegneri di Google sono più appassionati di velocità e gli ingegneri Sun/Oracle hanno più spazio.

Answer 3

L'argomento del costruttore HashMap è la capacità della mappa, ovvero il numero di bucket.

Quindi, se si passa 10 come argomento e si memorizzano 8 chiavi nella mappa, verrà raggiunta la soglia di restituzione (75% per impostazione predefinita) e la mappa verrà sottoposta a restituzione.

D'altra parte, l'argomento passato a newHashMapWithExpectedSize() è la dimensione prevista della mappa.Quindi, se superi 10, Guava creerà una mappa con un numero sufficiente di bucket per assicurarsi che la mappa non riduca quando si inseriscono 10 elementi: almeno 14 bucket.