Per put e get operazioni OpenHashMap outperform HashMap di circa 5 volte: https://gist.github.com/1423303collection.mutable.OpenHashMap vs collection.mutable.HashMap
sono i casi in cui HashMap dovrebbe essere preferito su OpenHashMap?
Il codice corrisponde esattamente a uno dei casi d'uso di OpenHashMap. Il tuo codice:
println ("scala OpenHashMap: " + time (warmup) {
val m = new scala.collection.mutable.OpenHashMap[Int,Int];
var i = 0;
var start = System.currentTimeMillis();
while(i<100000) { m.put(i,i);i=i+1;};
})
La spiegazione di OpenHashMap (scaladoc):
Una mappa hash mutevole sulla base di uno schema di hashing aperta. Lo schema preciso non è definito, ma dovrebbe fare uno sforzo ragionevole per garantire che un inserto con codici hash consecutivi non sia penalizzato in modo non corretto. Nello specifico , le mappature dei tasti interi consecutivi dovrebbero funzionare senza la perdita di prestazioni significativa.
La mia enfasi. Che spiega le tue scoperte. Quando utilizzare OpenHashMap piuttosto che HashMap? Vedi Wikipedia. Da lì:
tabelle hash concatenati con liste collegate sono popolari perché richiedono strutture dati solo di base con semplici algoritmi, e possono utilizzare semplici funzioni hash che non sono adatti per altri metodi.
Il costo di un'operazione tabella è quello di analizzare le voci del bucket selezionato per la chiave desiderata. Se la distribuzione delle chiavi è sufficientemente uniforme, il costo medio di una ricerca dipende solo dal numero medio di chiavi per bucket, ovvero dal fattore di carico.
Le tabelle hash concatenate rimangono valide anche quando il numero di voci di tabella n è molto superiore al numero di slot. Le loro prestazioni si degradano in modo più lineare (linearmente) con il fattore di carico. Ad esempio, una tabella hash concatenata con 1000 slot e 10.000 chiavi memorizzate (carico fattore 10) è da cinque a dieci volte più lento di una tabella da 10.000 slot (carica fattore 1); ma ancora 1000 volte più veloce di un semplice elenco sequenziale, e forse anche più veloce di un albero di ricerca bilanciato.
Per separare-concatenamento, il caso peggiore è quando tutte le voci sono stati inseriti nello stesso bucket, in tale caso la tabella hash è inefficace e il costo è quello di cercare dati della benna struttura. Se quest'ultimo è un elenco lineare, la procedura di ricerca può eseguire la scansione di tutte le sue voci; quindi il costo del caso peggiore è proporzionale al numero n di voci nella tabella.
Questa è una spiegazione generica. Come sempre con queste cose, le tue prestazioni variano a seconda del caso d'uso, se ti interessa, devi misurarlo.