Parametri di inizializzazione HashMap (caricamento/capacità iniziale)

Question

Quali valori devo passare per creare una struttura efficiente HashMap/HashMap basata su N elementi?

In un ArrayList, il numero efficiente è N (N presuppone già una crescita futura). Quali dovrebbero essere i parametri per un HashMap? ((int) (N * 0,75 d), 0,75 d)? Di Più? Di meno? Qual è l'effetto del cambiamento del fattore di carico?

Answer 1

Per quanto riguarda il fattore di carico, io semplicemente citazione dal HashMap javadoc:

Come regola generale, il fattore di carico di default (0,75) offre un buon compromesso tra costi di tempo e di 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). Il numero previsto di voci nella mappa e il suo fattore di carico dovrebbero essere presi in considerazione quando si imposta la sua capacità iniziale, in modo da ridurre al minimo il numero di operazioni di 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.

Significato, il fattore di carico non deve essere modificato da .75, a meno che non si disponga di un'ottimizzazione specifica che si intende eseguire. La capacità iniziale è l'unica cosa che si desidera modificare e impostarla in base al valore N, ovvero (N/0.75) + 1 o qualcosa in quell'area. Ciò assicurerà che la tabella sia sempre sufficientemente grande e che non si verifichi alcun rimbalzo.

Answer 2

In una lista di array, il numero efficiente è N (N presuppone già una crescita futura).

Ehm, no, a meno che non fraintenda quello che stai dicendo qui. Quando si passa un numero intero nel costruttore Arraylist, verrà creato un array sottostante di esattamente quella dimensione. Se risulta che hai bisogno anche di un singolo elemento extra, ArrayList dovrà ridimensionare l'array sottostante alla successiva chiamata add(), facendo sì che questa chiamata impieghi molto più tempo del solito.

Se invece stai parlando del tuo valore di N tenendo conto della crescita - allora sì, se puoi garantire che il valore non andrà mai oltre questo, allora è appropriato chiamare un costruttore di Arraylist. E in questo caso, come sottolineato da Hank, il costruttore analogo di una mappa sarebbe N e 1.0f. Questo dovrebbe funzionare ragionevolmente anche se si verifica un superamento di N (anche se si prevede che ciò avvenga su base regolare, si potrebbe desiderare di inserire un numero maggiore per la dimensione iniziale).

Il fattore di carico, nel caso non lo sapessi, è il punto in cui la mappa avrà la sua capacità aumentata, come frazione della capacità totale.

Modifica: Yuval probabilmente ha ragione che è una buona idea lasciare il fattore di carico intorno a 0,75 per una mappa generale. Un fattore di carico di 1.0 si comporterebbe in modo brillante se le tue chiavi avessero hash code sequenziali (come le chiavi in ​​sequenza sequenziali), ma per qualsiasi altra cosa potresti incorrere in collisioni con i bucket hash, il che significa che le ricerche richiedono più tempo per alcuni elementi. La creazione di più bucket di quanto strettamente necessario ridurrà questa possibilità di collisione, il che significa che ci sono più possibilità che gli elementi siano nei propri bucket e quindi siano recuperabili nel più breve tempo possibile. Come dicono i documenti, questo è un compromesso tra tempo e spazio. Se uno dei due è particolarmente importante per te (come mostrato da un profiler piuttosto che ottimizzarlo prematuramente!), Puoi sottolinearlo; in caso contrario, attenersi al valore predefinito.

Answer 3

E 'notevole anche che avere un HashMap sul lato piccolo rende le collisioni hash più probabile, che può rallentare ricerca. Quindi, se davvero preoccupare la velocità della mappa, e meno sulla sua dimensione, potrebbe essere la pena di fare un po 'troppo grande per i dati di cui ha bisogno per tenere. Dal momento che la memoria è a buon mercato, io di solito inizializzo HashMaps per un numero limitato di elementi con

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2); 

Sentitevi liberi di non essere d'accordo, in realtà mi piacerebbe molto piace avere questa idea verificati e buttato fuori.

Answer 4

riferimento al codice sorgente HashMap aiuterà.

Se il numero di voci raggiunge la soglia (capacità * fattore di carico), rimaneggiamento è fatto automaticamente. Ciò significa che un fattore di carico troppo piccolo può comportare frequenti rilasci con l'aumento delle voci.

Answer 5

Per molto grandi HashMaps nei sistemi critici, in cui trovare il torto capacità iniziale può essere molto problematico, potrebbe essere necessario informazioni empiriche per determinare il modo migliore per inizializzare il Map.

CollectionSpy (collectionspy.com) è un nuovo profiler Java che consente di vedere in un batter d'occhio quali HashMaps sono vicini al bisogno di rimodellare, quante volte sono state rimaneggiate in passato e altro ancora. Uno strumento ideale per determinare argomenti di capacità iniziale sicuri per i costruttori di container basati sulla capacità.

Answer 6

La risposta Yuval dato è corretto solo per Hashtable. HashMap utilizza power-of-two bucket, quindi per HashMap, Zarkonnen è effettivamente corretto. È possibile verificare questo dal codice sorgente:

// Find a power of 2 >= initialCapacity 
    int capacity = 1; 
    while (capacity < initialCapacity) 
    capacity <<= 1; 

Così, anche se il fattore di carico di 0.75f ​​è sempre lo stesso tra il Hashtable e HashMap, è necessario utilizzare una capacità iniziale n * 2 dove n è il numero di elementi hai intenzione di archiviare in HashMap. Ciò garantirà le velocità di entrata/uscita più veloci.

Answer 7

E 'sicuro nella maggior parte dei casi di List e Map l'inizializzazione di rendere il List o Map con le seguenti dimensioni params.

List<T>(numElements + (numElements/2)); 
Map<T,T>(numElements + (numElements/2)); 

questo segue la regola .75 nonché salva un overhead poco sopra l'operazione * 2 sopra descritto.

Answer 8

Ho eseguito qualche unit tests per vedere se queste risposte erano corrette e si è scoperto che utilizzando:

(int) Math.ceil(requiredCapacity/loadFactor); 

come la capacità iniziale dà ciò che si desidera sia per una HashMap o un Hashtable. Con "cosa vuoi" intendo che l'aggiunta di elementi requiredCapacity alla mappa non causerà il ridimensionamento della matrice che sta eseguendo il wrapping e la matrice non sarà più grande del necessario. Poiché la capacità di carico di default è 0,75, inizializzazione di una HashMap questo modo funziona:

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity/0.75)); 

poiché un HashSet è efficace solo un involucro per un HashMap, la stessa logica vale anche lì, cioèè possibile costruire un HashSet in modo efficiente in questo modo: la risposta di

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity/0.75)); 

@Yuval Adam sia corretta per tutti i casi eccetto dove (requiredCapacity/0.75) è una potenza di 2, nel qual caso si alloca troppa memoria.
@ risposta di NotEdible utilizza troppa memoria, in molti casi, come costruttore di HashMap in sé occupa di questioni che vogliono la matrice mappe per avere una dimensione che è una potenza di 2.

Answer 9

Nel guava libraries da parte di Google non ci sta una funzione che crea una HashMap ottimizzata per un numero previsto di articoli: newHashMapWithExpectedSize

dalla documentazione:

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