Prestazioni di HashMap con diversa capacità iniziale e fattore di carico

Question

Ecco la mia situazione. Sto usando due java.util.HashMap per memorizzare alcuni dati utilizzati di frequente in un'app Web Java in esecuzione su Tomcat. Conosco il numero esatto di voci in ogni Hashmap. Le chiavi saranno rispettivamente stringhe e int.

La mia domanda è, qual è il modo migliore per impostare la capacità iniziale e il load factor?

Devo impostare la capacità uguale al numero di elementi che avrà e la capacità di carico a 1.0? Mi piacerebbe la migliore performance assoluta senza usare troppa memoria. Tuttavia, temo che il tavolo non si riempia in modo ottimale. Con una tabella delle dimensioni esatte necessarie, non ci sarà la collisione tra le chiavi, causando una scansione (solitamente breve) per trovare l'elemento corretto?

Assumendo (e questo è un allungamento) che la funzione di hash è un semplice mod 5 dei tasti interi, non significherebbe che i tasti 5, 10, 15 colpiranno lo stesso bucket e quindi causeranno un tentativo di riempimento i secchi accanto a loro? Una maggiore capacità iniziale aumenterebbe le prestazioni?

Inoltre, se c'è una migliore infrastruttura di una hashmap per questo, sono completamente aperto anche a questo.

Answer 1

In assenza di una funzione di hashing perfetto per i vostri dati, e supponendo che questo non è davvero un micro-ottimizzazione di qualcosa che in realtà non importa, vorrei provare il seguente:

Assumere il carico di default la capacità (.75) utilizzata da HashMap è un buon valore nella maggior parte delle situazioni. Stando così le cose, puoi usarlo e impostare la capacità iniziale della tua HashMap basandoti sulla tua conoscenza di quanti oggetti manterrà: impostalo in modo che la capacità iniziale x .75 = numero di elementi (arrotondato per eccesso).

Se si trattasse di una mappa più grande, in una situazione in cui la ricerca ad alta velocità era davvero critica, suggerirei di utilizzare una sorta di trie anziché una mappa hash. Per le stringhe lunghe, nelle mappe di grandi dimensioni, è possibile risparmiare spazio e un po 'di tempo, utilizzando una struttura di dati più orientata alle stringhe, come un trie.

Answer 2

Le voci sono assegnate ai bucket in modo casuale. Pertanto, anche se si dispone di un numero di bucket pari a quello delle voci, alcuni dei bucket avranno collisioni.

Se si dispone di più bucket, si avranno meno collisioni. Tuttavia, più secchi significa che si diffondono nella memoria e quindi più lenti. Generalmente un fattore di carico compreso tra 0,7 e 0,8 è approssimativamente ottimale, quindi probabilmente non vale la pena cambiarlo.

Come sempre, probabilmente vale la pena profilare prima di rimanere attaccato al microtuning di queste cose.

Answer 3

Supponendo (e questo è un tratto) che la funzione hash è una semplice mod 5 delle chiavi intere

non lo è. Da HashMap.java:

static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

non ho nemmeno intenzione di far finta Lo capisco, ma sembra che è stato studiato per gestire questa situazione.

Si noti inoltre che il numero di benne è sempre una potenza di 2, indipendentemente dalle dimensioni richieste.

Answer 4

Trovo che sia meglio non giocherellare con le impostazioni predefinite a meno che non ne abbia davvero bisogno.

Hotspot fa un grande lavoro di fare ottimizzazioni per voi.

In ogni caso; Vorrei usare un profiler (Say Netbeans Profiler) per misurare il problema prima.

Memorizziamo regolarmente mappe con 10000 di elementi e se si dispone di una buona equità e implementazione di codice hash (e stringhe e numeri interi!), Questo sarà migliore di qualsiasi modifica di carico che si possa apportare.

Answer 5

Supponendo che la funzione di hash sia "buona", la cosa migliore da fare è impostare la dimensione iniziale sul numero previsto di elementi, supponendo che si possa ottenere una buona stima a basso costo. È una buona idea farlo perché quando un HashMap ridimensiona deve ricalcolare i valori hash per ogni chiave nella tabella.

Lascia il fattore di carico a 0.75. Il valore di 0.75 è stato scelto empiricamente come un buon compromesso tra le prestazioni di ricerca hash e l'utilizzo dello spazio per l'array di hash primario. Mentre si attiva il fattore di carico, il tempo di ricerca medio aumenterà in modo significativo.

Se si vuole scavare nella matematica del comportamento tabella di hash: Donald Knuth (1998). L'arte della programmazione informatica '. 3: Ordinamento e ricerca (2 ° ed.). Addison-Wesley. pp. 513-558. ISBN 0-201-89685-0.