La migliore capacità iniziale di HashMap durante l'indicizzazione di un elenco

Question

Ho una lista (List<T> list) e desidero indicizzare gli oggetti tramite i relativi ID utilizzando una mappa (HashMap<Integer, T> map). Io uso sempre list.size() come capacità iniziale nel costruttore HashMap, come nel codice qui sotto. È questa la migliore capacità iniziale da utilizzare in questo caso?

Nota: Non sarò mai aggiungere altri elementi alla mappa.

List<T> list = myList; 
Map<Integer, T> map = new HashMap<Integer, T>(list.size()); 
for(T item : list) { 
    map.put(item.getId(), item); 
} 

Answer 1

Se si vuole evitare rimasticare il HashMap, e si sa che nessun altro elementi saranno inseriti nel HashMap, allora si deve prendere in considerazione il fattore di carico, così come la capacità iniziale. Il fattore di carico for a HashMap defaults to 0.75.

Il calcolo per determinare se il rehashing è necessario si verifica ogni volta che viene aggiunta una nuova voce, ad es. put inserisce una nuova chiave/valore. Pertanto, se si specifica una capacità iniziale di list.size() e un fattore di caricamento pari a 1, verrà eseguito il rehash dopo l'ultimo put. Quindi, per evitare il rimbalzo, utilizzare un fattore di carico di 1 e una capacità di list.size() + 1.

EDIT

Guardando il codice sorgente di HashMap, sarà rimaneggiamento se il vecchio dimensioni soddisfa o supera la soglia, in modo da non rivangare sull'ultimo put. Quindi sembra che una capacità di list.size() dovrebbe andare bene.

HashMap<Integer, T> map = new HashMap<Integer, T>(list.size(), 1.0); 

Ecco il pezzo rilevante del codice sorgente di HashMap:

void addEntry(int hash, K key, V value, int bucketIndex) { 
    Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<>(hash, key, value, e); 
    if (size++ >= threshold) 
     resize(2 * table.length); 
} 

Answer 2

Quello che stai facendo va bene. In questo modo sei sicuro che la mappa hash ha almeno una capacità sufficiente per i valori iniziali pari a. Se si dispone di maggiori informazioni sui modelli di utilizzo della mappa hash (esempio: è aggiornato frequentemente? Sono aggiunti molti nuovi elementi frequentemente?), Si potrebbe voler impostare una capacità iniziale più grande (ad esempio, list.size() * 2), ma mai inferiore. Utilizzare un profiler per determinare se la capacità iniziale sta scendendo troppo presto.

UPDATE

Grazie a @PaulBellora per suggerendo che la capacità iniziale deve essere impostato (int)Math.ceil(list.size()/loadFactor) (tipicamente, il fattore di carico di default è 0.75) al fine di evitare un ridimensionamento iniziale.

Answer 3

Guava di Maps.newHashMapWithExpectedSize utilizza questo metodo di supporto per calcolare la capacità iniziale per il fattore di carico di default di 0.75, sulla base di un numero previsto di valori:

/** 
* Returns a capacity that is sufficient to keep the map from being resized as 
* long as it grows no larger than expectedSize and the load factor is >= its 
* default (0.75). 
*/ 
static int capacity(int expectedSize) { 
    if (expectedSize < 3) { 
     checkArgument(expectedSize >= 0); 
     return expectedSize + 1; 
    } 
    if (expectedSize < Ints.MAX_POWER_OF_TWO) { 
     return expectedSize + expectedSize/3; 
    } 
    return Integer.MAX_VALUE; // any large value 
} 

di riferimento: source

Dalla documentazione newHashMapWithExpectedSize:

Crea un'istanza HashMap, con un elevato eno ugh "capacità iniziale" che è contenere gli elementi expectedSize senza crescita. Questo comportamento non può essere ampiamente garantito, ma si verifica che sia vero per OpenJDK 1.6. Inoltre, non è possibile garantire che il metodo non sia inavvertitamente oversize la mappa restituita.

Answer 4

Secondo il reference documentation of java.util.HashMap:

Il numero atteso di voci nella mappa e il suo fattore di carico deve essere preso in considerazione quando si imposta la sua capacità iniziale, in modo da ridurre al minimo il numero di operazioni rehash. Se la capacità iniziale è maggiore del numero massimo di voci diviso per il fattore di carico, non si verificherà mai alcuna operazione di restringimento.

Questo significa che, se si conosce in anticipo, quante voci HashMap dovrebbe conservare, è possibile impedire rimaneggiamento scegliendo un adeguato capacità iniziale e fattore di carico. Tuttavia:

Come regola generale, il fattore di carico predefinito (.75) offre un buon compromesso tra costi di tempo e spazio.Valori più alti riducono l'overhead dello spazio ma aumentano il costo di ricerca (riflesso nella maggior parte delle operazioni della classe HashMap, inclusi get e put).

Answer 5

La parola chiave 'capacità' non è corretto, per definizione, e non viene utilizzato nel modo tipicamente previsto.

Per impostazione predefinita, il "fattore di carico" di una HashMap è 0,75, ciò significa che quando il numero di voci in una HashMap raggiunge il 75% della capacità fornita, ridimensionerà l'array e il rehash.

Per esempio, se faccio:

Map<Integer, Integer> map = new HashMap<>(100); 

Quando sto aggiungendo la voce 75 °, la mappa sarà ridimensionare la tabella Ingresso 2 * map.size() (o 2 * table.length). Così possiamo fare un paio di cose:

1. Cambiare il fattore di carico - questo potrebbe influire sulle prestazioni della mappa
2. Impostare la capacità iniziale di list.size()/0,75 + 1

l'opzione migliore è il secondo dei due, vorrei spiegare che cosa sta succedendo qui:

list.size()/0.75 

Questa list.size tornerà() + 25% di list.size(), per esempio se la mia lista ha avuto un dimensione di 100 restituirebbe 133. Noi quindi aggiungi 1 ad esso mentre la mappa viene ridimensionata se la sua dimensione è pari al 75% della capacità iniziale, quindi se avessimo una lista con una dimensione di 100, imposteremo la capacità iniziale a 134, questo significherebbe che l'aggiunta di tutte le 100 voci dalla lista non comporterebbe alcun ridimensionamento della mappa.

Risultato finale:

Map<Integer, Integer> map = new HashMap<>(list.size()/0.75 + 1);