Parametri di inizializzazione di HashMap (load / initialcapacity)

Question

Quali valori devo passare per creare un'efficace struttura basata su HashMap / HashMap per N articoli?

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

Answer 1

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

  

Come regola generale, il fattore di carico predefinito (.75) offre un buon compromesso tra tempo e costi di spazio. Valori più alti riducono il sovraccarico di spazio ma aumentano i costi di ricerca (riflessi nella maggior parte delle operazioni della classe HashMap, incluso get e put). Il numero previsto di voci nella mappa e il relativo fattore di carico devono 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 rehash.

Significato, il fattore di carico non dovrebbe essere modificato da .75 , a meno che tu non abbia qualche ottimizzazione specifica che stai per fare. La capacità iniziale è l'unica cosa che desideri modificare e impostala in base al valore N , ovvero (N / 0.75) + 1 o qualcosa in quella zona. Ciò garantirà che la tabella sia sempre abbastanza grande e che non si verifichi alcun rimodellamento.

Answer 2

Ho eseguito alcuni unit test per vedere se queste risposte erano corrette e si è scoperto che usando:

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

poiché la capacità iniziale fornisce ciò che desideri per un HashMap o un Hashtable . Di " cosa vuoi " Voglio dire che l'aggiunta di elementi requiredCapacity alla mappa non farà ridimensionare l'array che sta avvolgendo e l'array non sarà più grande del necessario. Poiché la capacità di carico predefinita è 0,75, l'inizializzazione di una HashMap in questo modo funziona:

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

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

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

La risposta di @Yuval Adam è corretta per tutti i casi tranne dove (richiestoCapacità / 0,75) è una potenza di 2, nel qual caso alloca troppa memoria.
La risposta di @ NotEdible utilizza troppa memoria in molti casi, poiché lo stesso costruttore di HashMap affronta i problemi che desidera che l'array di mappe abbia una dimensione che sia una potenza di 2.

Answer 3

Nelle librerie guava di Google c'è 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" abbastanza elevata che dovrebbe contenere elementi previsti Dimensione senza crescita ...

Answer 4

È anche degno di nota il fatto che avere una HashMap sul lato piccolo rende più probabili le collisioni di hash, il che può rallentare la ricerca. Quindi, se ti preoccupi davvero della velocità della mappa e meno delle sue dimensioni, potrebbe valere la pena renderlo un po 'troppo grande per i dati che deve contenere. Poiché la memoria è economica, in genere inizializzo HashMaps per un numero noto di elementi con

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

Sentiti libero di non essere d'accordo, infatti mi piacerebbe molto che questa idea fosse verificata o respinta.

Answer 5

La risposta che Yuval ha dato è corretta solo per Hashtable. HashMap utilizza due secchi di potenza, quindi per HashMap Zarkonnen è in realtà corretto. Puoi verificarlo dal codice sorgente:

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

Quindi, sebbene il fattore di carico di 0.75f ??sia 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à la massima velocità get / put.

Answer 6

  

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

Ehm, no, a meno che non fraintenda quello che stai dicendo qui. Quando passi un numero intero nel costruttore dell'Arraylist, creerà un array sottostante esattamente di quella dimensione. Se risulta che è necessario anche un singolo elemento aggiuntivo, ArrayList dovrà ridimensionare l'array sottostante alla prossima 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 tale costruttore di Arraylist. E in questo caso, come sottolineato da Hank, l'analogo costruttore di una mappa sarebbe N e 1.0f. Questo dovrebbe funzionare ragionevolmente anche se ti capita di superare N (anche se ti aspetti che ciò avvenga su base regolare, potresti voler passare un numero maggiore per la dimensione iniziale).

Il fattore di carico, nel caso tu non fossi a conoscenza, è il punto in cui la sua capacità della mappa sarà aumentata, come una frazione della capacità totale.

Modifica : Yuval ha probabilmente ragione sul fatto che è una buona idea lasciare il fattore di carico intorno a 0,75 per una mappa di uso generale. Un fattore di carico di 1,0 funzionerebbe in modo brillante se le tue chiavi avessero hashcode sequenziali (come chiavi intere sequenziali), ma per qualsiasi altra cosa probabilmente ti imbatterai in collisioni con i secchi hash, il che significa che le ricerche richiedono più tempo per alcuni elementi. La creazione di più bucket di quanto sia strettamente necessario ridurrà questa possibilità di collisione, il che significa che ci sono più possibilità che gli elementi siano nei loro bucket e che possano quindi essere recuperati 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 da una prematura ottimizzazione!) Puoi enfatizzarlo; in caso contrario, mantieni l'impostazione predefinita.

Answer 7

Sarà utile fare riferimento al codice sorgente di HashMap.

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 ripassaggi man mano che le voci crescono.

Answer 8

Nella maggior parte dei casi è possibile inizializzare List e Map per creare List o Map con i seguenti parametri di dimensione.

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

segue la regola .75 e salva un po 'di overhead sull'operazione * 2 sopra descritta.

Answer 9

Per HashMap di grandi dimensioni in sistemi critici, dove sbagliare la capacità iniziale può essere molto problematico, potresti aver bisogno di informazioni empiriche per determinare il modo migliore di inizializzare la tua Mappa.

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