In che modo l'implementazione di LinkedHashMap è diversa da HashMap?

Question

Se la complessità temporale di LinkedHashMap è uguale alla complessità di HashMap, perché abbiamo bisogno di HashMap? Quali sono le overhead extra che LinkedHashMap ha rispetto a HashMap in Java?

Answer 1

LinkedHashMap richiederà più memoria. Ogni voce in un normale HashMap ha solo la chiave e il valore. Ogni voce LinkedHashMap ha quei riferimenti e riferimenti alle voci successive e precedenti. C'è anche un po 'di pulizie in più da fare, anche se di solito è irrilevante.

Answer 2

• LinkedHashMap mantiene inoltre un elenco doppiamente collegato che attraversa tutte le sue voci, che fornirà un ordine riproducibile. Questo elenco collegato definisce l'ordine di iterazione, che è normalmente l'ordine in cui le chiavi sono state inserite nella mappa (ordine di inserimento).
• HashMap non ha questi costi aggiuntivi (runtime, spazio) e dovrebbe preferire su LinkedHashMap quando non ti interessa l'ordine di inserimento.

Answer 3

LinkedHashMap è una struttura dati utile quando è necessario conoscere l'ordine di inserimento delle chiavi sulla mappa. Un caso d'uso adatto è per l'implementazione di una cache LRU. A causa del mantenimento dell'ordine di LinkedHashMap, la struttura dei dati richiede memoria aggiuntiva rispetto a HashMap. Nel caso in cui l'ordine di inserimento non fosse un requisito, dovresti sempre scegliere HashMap.

Answer 4

Se la complessità temporale di LinkedHashMap è uguale alla complessità di HashMap, perché è necessario HashMap?

Non si deve confondere la complessità con le prestazioni. Due algoritmi possono avere la stessa complessità, ma uno può costantemente ottenere risultati migliori rispetto agli altri.

Ricorda che f(N) is O(N) significa che:

C1*N <= limit(f(N), N -> infinity) <= C2*N 

dove C1 e C2 sono rigorosamente costanti positive. La complessità non dice nulla su quanto piccoli o grandi siano i valori C. Per due diversi algoritmi, le costanti saranno probabilmente diverse.

(E ricordate che O-grande complessità è circa il comportamento/performance come N diventa molto grande. Ti dice nulla circa il comportamento/prestazioni per i piccoli N valori.)

---

Detto questo, la differenza di prestazioni tra le operazioni HashMap e LinkedHashMap in equivalenti casi d'uso è relativamente piccola. Spesso, le spese generali extra di memoria sono più rilevanti.

Answer 5

C'è un'altra importante differenza tra HashMap e LinkedHashMap: L'iterazione è più efficiente in caso di LinkedHashMap.

come elementi LinkedHashMap sono collegati tra loro in modo iterazione richiede tempo proporzionale alla dimensione della mappa, indipendentemente dalla sua capacità. Ma in caso di HashMap; poiché non esiste un ordine fisso, quindi l'iterazione su di esso richiede tempo proporzionale alla sua capacità.

Ho messo più dettagli sul mio blog.

Answer 6

• Ridimensionamento dovrebbe essere più veloce come un'iterazione sua lista doppio-linked per trasferire il contenuto in una nuova matrice di tabella.
• containsValue() è sovrascritto per sfruttare l'iteratore più veloce.
• LinkedHashMap può anche essere utilizzato per creare una cache LRU. Un costruttore speciale LinkedHashMap (capacity, loadFactor, accessOrderBoolean) viene fornito per creare una mappa hash collegata il cui ordine di iterazione è l'ordine in cui le ultime voci sono state l 'ultimo accesso, da accesso meno recente a più di recente. In questo caso, solo interrogare la mappa con get() è una modifica strutturale.

Answer 7

LinkedHashMap eredita HashMap, ovvero utilizza un'implementazione esistente di HashMap per memorizzare chiavi e valori in un nodo (oggetto voce). Oltre a ciò, memorizza un'implementazione separata con un elenco a doppia connessione per mantenere l'ordine di inserimento in cui sono state immesse le chiavi.

Sembra che questo:

nodo intestazione < ---> nodo 1 < ---> nodo 2 < ---> nodo 3 < ----> nodo 4 < ---> intestazione nodo.

Un ulteriore sovraccarico consente di mantenere l'inserimento e la cancellazione in questa lista doppiamente collegata. Il vantaggio è: L'ordine di iterazione è garantito come ordine di inserzione, che non è in HashMap.

Answer 8

HashMap non mantiene l'ordine di inserzione, quindi non mantiene alcuna lista doppiamente collegata.

La caratteristica più saliente di LinkedHashMap è che mantiene l'ordine di inserimento delle coppie chiave-valore. LinkedHashMap utilizza l'Elenco collegato doppiamente per farlo.

Ingresso di LinkedHashMap assomiglia a questo:

static class Entry<K, V> { 
    K key; 
    V value; 
    Entry<K,V> next; 
    Entry<K,V> before, after;  //For maintaining insertion order  
    public Entry(K key, V value, Entry<K,V> next){ 
     this.key = key; 
     this.value = value; 
     this.next = next; 
    } 
    } 

Utilizzando prima e dopo - teniamo traccia di voce appena aggiunta in LinkedHashMap, che ci aiuta a mantenere ordine di inserimento.

Prima di fare riferimento alla voce precedente e dopo si riferisce alla voce successiva in LinkedHashMap.

Schemi e spiegazione passo passo si veda http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html