Prestazioni HashMap vs LinkedHashMap in iterazione su valori()

Question

Esiste una differenza di prestazioni tra HashMap e LinkedHashMap per attraversare la funzione values()?

Answer 1

penso che il LinkedHashMap deve essere più veloce in attraversamento a causa di un nextEntry implementazione superiore nella sua Iterator

Ecco perché:

andiamo passo dopo passo dal values implementazione.
La HashMap attuazione del values è questo:

public Collection<V> values() { 
     Collection<V> vs = values; 
     return (vs != null ? vs : (values = new Values())); 
    } 

Il LinkedHashMap estende da HashMap e eredita la stessa implementazione.

La differenza è nell'implementazione Iterator per il Values in entrambi.

per HashMap si estende da java.util.HashMap.HashIterator

private final class ValueIterator extends HashIterator<V> { 
     public V next() { 
      return nextEntry().value; 
     } 
    } 

ma per LinkedHashMap si estende da java.util.LinkedHashMap.LinkedHashIterator

private class ValueIterator extends LinkedHashIterator<V> { 
     public V next() { return nextEntry().value; } 
    } 

così la differenza riduce essenzialmente a nextEntry attuazione.

Per LinkedHashMap è solo chiamando e.after dove e è la Entry, ma per HashMap c'è qualche lavoro coinvolti nella attraversando la matrice Entry[] per trovare il prossimo successiva.

UPDATE: Codice per nextEntry() in HashMap

final Entry<K,V> nextEntry() { 
      if (modCount != expectedModCount) 
       throw new ConcurrentModificationException(); 
      Entry<K,V> e = next; 
      if (e == null) 
       throw new NoSuchElementException(); 

      if ((next = e.next) == null) { 
       Entry[] t = table; 
       while (index < t.length && (next = t[index++]) == null) 
        ; 
      } 
      current = e; 
      return e; 
     } 

La Voce [] non è un negozio attiguo. (Ci potrebbero essere valori nulli in mezzo). Se date un'occhiata al codice sopra, ciò che fa è puntare vicino a corrente e trovare il prossimo dopo iterando sopra la voce [].

Ma Penso che questo guadagno di prestazioni arriverà al costo dell'inserimento.Guarda il metodo addEntry in entrambe le classi come esercizio.

Answer 2

Il miglior consiglio sarebbe "Non aver paura di provarlo", ma sono abbastanza sicuro che siano molto simili. Getter per il set di valori è O (1) e quindi ogni passo iteratore. L'iterazione attraverso una lista concatenata è tanto banale quanto l'iterazione attraverso i bucket hash, con un possibile piccolo vantaggio in favpr dell'elenco collegato.

Answer 3

Quasi non importa. La domanda è: cosa ti serve? Se l'ordine degli elementi è rilevante, è necessario utilizzare LinkedHashMap. Altrimenti non ne hai bisogno, quindi usa HashMap.

Answer 4

Ho provato in un test unitario, valori ripetuti() 10000 volte, i millisecondi: 806 vs 902. È quasi la stessa cosa.

Answer 5

Sì, ci sarà la stessa differenza di prestazioni come si ottiene in tutte le iterazioni su HashMap contro LinkedHashMap: HashMap vorrà del tempo proporzionale al numero di voci più la dimensione della tabella hash, e LinkedHashMap vorrà solo tempo proporzionale il numero di voci.

Answer 6

Ho scritto un piccolo programma di creazione di profili creando 1 milione di chiavi (numero intero) vs Booleano.TRUE, ripetendo 100 volte. Trovato il seguente:

HashMap:- 
Create: 3.7sec 
Iterate: 1.1sec 
Access: 1.5sec 
Total: 6.2sec 

LinkedHashMap:- 
Create: 4.7sec (30% slower) 
Iterate: 0.5sec (50% faster) 
Access: 0.8sec (50% faster) 
Total : 6.0sec 

garbage collection non fatto inquina i numeri un po ', ma penso che LinkedHashMap ha il vantaggio rispetto HashMap e userò che nel codice futuro.