Parametri di inizializzazione HashMap (caricamento / capacità iniziale)

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

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

Per quanto riguarda il fattore di carico, citerò semplicemente il javadoc di HashMap :

Come regola generale, il load factor predefinito (.75) offre un buon compromesso tra costi di spazio e tempo. Valori più alti riducono l’overhead dello spazio ma aumentano il costo di ricerca (riflesso nella maggior parte delle operazioni della class 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 dovrebbe essere modificato da .75 , a meno che non si disponga di un’ottimizzazione specifica che si intende fare. 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.

Ho eseguito alcuni test unitari per vedere se queste risposte fossero corrette e si è scoperto che utilizzando:

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

poiché la capacità iniziale dà quello che vuoi sia per HashMap che per Hashtable . Con “cosa vuoi” intendo che aggiungere gli elementi requiredCapacity alla mappa non causerà la ridimensionamento della matrice che sta eseguendo il wrapping e l’array non sarà più grande del necessario. Poiché la capacità di caricamento predefinita è 0,75, l’inizializzazione di una HashMap come questa funziona:

 ... = new HashMap((int) Math.ceil(requiredCapacity / 0.75)); 

Dato che un HashSet è effettivamente solo un wrapper per una HashMap, la stessa logica si applica anche lì, ovvero puoi build un HashSet in modo efficiente come questo:

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

La risposta di @Yuval Adam è corretta per tutti i casi tranne dove (requiredCapacity / 0.75) è una potenza di 2, nel qual caso assegna troppa memoria.
@ La risposta di NotEdible utilizza troppa memoria in molti casi, poiché il costruttore di HashMap si occupa dei problemi che vuole che l’array di mappe abbia una dimensione che è una potenza di 2.

Nelle librerie guava di Google esiste una funzione che crea una HashMap ottimizzata per un numero previsto di elementi: newHashMapWithExpectedSize

dai documenti:

Crea un’istanza di HashMap, con una “capacità iniziale” sufficientemente elevata che dovrebbe contenere elementi previsti Size senza crescita …

È anche degno di nota il fatto che avere una HashMap sul lato piccolo rende più probabili le collisioni hash, che possono rallentare la ricerca. Quindi, se ti preoccupi veramente della velocità della mappa e meno delle sue dimensioni, potrebbe valere la pena renderla un po ‘troppo grande per i dati che deve contenere. Poiché la memoria è a buon mercato, di solito inizializzo HashMaps con un numero noto di elementi

 HashMap myMap = new HashMap(numberOfElements * 2); 

Sentiti libero di non essere d’accordo, infatti mi piacerebbe molto avere questa idea verificata o buttata fuori.

La risposta che Yuval ha dato è corretta solo per Hashtable. HashMap utilizza power-of-two bucket, quindi per HashMap, Zarkonnen è effettivamente corretto. Puoi verificarlo dal codice sorgente:

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

Quindi, anche se il fattore di caricamento di 0.75f ​​è sempre lo stesso tra Hashtable e HashMap, dovresti usare una capacità iniziale n * 2 dove n è il numero di elementi che prevedi di archiviare in HashMap. Ciò garantirà le velocità di entrata / uscita più veloci.

In ArrayList, 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 d’altra parte stai parlando del tuo valore di N tenendo conto della crescita – allora sì, se puoi garantire che il valore non andrà mai al di sopra di questo, chiamare un costruttore di Arraylist è appropriato. 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 in cui non si fosse a conoscenza, è il punto in cui la mappa avrà la sua capacità aumentata, come una frazione della capacità totale.

Modifica : probabilmente Yuval ha ragione che è un’idea migliore 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 ansible. 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.

Fare riferimento al codice sorgente di HashMap aiuterà.

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

È sicuro nella maggior parte dei casi di inizializzazione di List e Map per creare l’ List o la Map con i seguenti parametri di dimensione.

 List(numElements + (numElements / 2)); Map(numElements + (numElements / 2)); 

questo segue la regola .75 e salva un piccolo overhead rispetto all’operazione * 2 descritta sopra.

Per HashMaps molto grandi in sistemi critici, dove ottenere la capacità iniziale errata può essere molto problematico, potresti avere bisogno di informazioni empiriche per determinare il modo migliore per inizializzare la tua mappa.

CollectionSpy ( collectionspy.com ) è un nuovo profiler Java che ti consente di vedere in un battito di ciglia che HashMaps è vicino 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à.