Unterschied zwischen HashMap, LinkedHashMap und TreeMap

Was ist der Unterschied zwischen HashMap , LinkedHashMap und TreeMap in Java? Ich sehe keinen Unterschied in der Ausgabe, da alle drei keySet und values . Was sind Hashtable ?

 Map m1 = new HashMap(); m1.put("map", "HashMap"); m1.put("schildt", "java2"); m1.put("mathew", "Hyden"); m1.put("schildt", "java2s"); print(m1.keySet()); print(m1.values()); SortedMap sm = new TreeMap(); sm.put("map", "TreeMap"); sm.put("schildt", "java2"); sm.put("mathew", "Hyden"); sm.put("schildt", "java2s"); print(sm.keySet()); print(sm.values()); LinkedHashMap lm = new LinkedHashMap(); lm.put("map", "LinkedHashMap"); lm.put("schildt", "java2"); lm.put("mathew", "Hyden"); lm.put("schildt", "java2s"); print(lm.keySet()); print(lm.values()); 

Alle drei classn implementieren die Map Schnittstelle und bieten meist die gleiche functionalität. Der wichtigste Unterschied ist die Reihenfolge, in der die Iteration durch die Einträge erfolgt:

  • HashMap gibt keinerlei Garantie für die Iterationsreihenfolge. Es kann (und wird) sich sogar komplett ändern, wenn neue Elemente hinzugefügt werden.
  • TreeMap wird gemäß der “natürlichen Ordnung” der Schlüssel gemäß ihrer compareTo() Methode (oder eines extern gelieferten Comparator ) iterieren. Darüber hinaus implementiert es die Schnittstelle ” SortedMap “, die Methoden enthält, die von dieser Sortierreihenfolge abhängen.
  • LinkedHashMap wird in der Reihenfolge LinkedHashMap , in der die Einträge in die Map LinkedHashMap wurden

“Hashtable” ist der generische Name für Hash-basierte Karten. Im Kontext der Java-API ist Hashtable eine veraltete class aus den Tagen von Java 1.1, bevor das Collections-Framework existierte. Es sollte nicht mehr verwendet werden, da seine API mit veralteten Methoden, die die functionalität duplizieren, überladen ist und ihre Methoden synchronisiert sind (was die performance verringern kann und im Allgemeinen nutzlos ist). Verwenden Sie ConcurrentHashMap anstelle von Hashtable.

Ich bevorzuge visuelle Präsentation:

 ╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗ ║ Property ║ HashMap ║ TreeMap ║ LinkedHashMap ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ Iteration ║ no guarantee order ║ sorted according ║ ║ ║ Order ║ will remain constant║ to the natural ║ insertion-order ║ ║ ║ over time ║ ordering ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ Get/put ║ ║ ║ ║ ║ remove ║ O(1) ║ O(log(n)) ║ O(1) ║ ║ containsKey ║ ║ ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ ║ ║ NavigableMap ║ ║ ║ Interfaces ║ Map ║ Map ║ Map ║ ║ ║ ║ SortedMap ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ ║ ║ ║ ║ ║ Null ║ allowed ║ only values ║ allowed ║ ║ values/keys ║ ║ ║ ║ ╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣ ║ ║ Fail-fast behavior of an iterator cannot be guaranteed ║ ║ Fail-fast ║ impossible to make any hard guarantees in the presence of ║ ║ behavior ║ unsynchronized concurrent modification ║ ╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣ ║ ║ ║ ║ ║ ║Implementation║ buckets ║ Red-Black Tree ║ double-linked ║ ║ ║ ║ ║ buckets ║ ╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣ ║ Is ║ ║ ║ synchronized ║ implementation is not synchronized ║ ╚══════════════╩═══════════════════════════════════════════════════════════════╝ 

Alle drei repräsentieren die Zuordnung von eindeutigen Schlüsseln zu Werten und implementieren daher die Map- Schnittstelle.

  1. HashMap ist eine Karte, die auf Hashing der Schlüssel basiert. Es unterstützt O (1) get / put Operationen. Schlüssel müssen konsistente Implementierungen von hashCode() und equals() damit dies funktioniert.

  2. LinkedHashMap ist HashMap sehr ähnlich, aber es erhöht die Aufmerksamkeit für die Reihenfolge, in der Elemente hinzugefügt werden (oder auf die zugegriffen wird). Daher entspricht die Iterationsreihenfolge der Einfügereihenfolge (oder der Zugriffsreihenfolge, abhängig von den Konstruktionsparametern).

  3. TreeMap ist ein baumbasiertes Mapping. Seine Put / Get-Operationen benötigen O (log n) -Zeit. Es erfordert, dass Elemente einen Vergleichsmechanismus haben, entweder mit Comparable oder Comparator. Die Iterationsreihenfolge wird durch diesen Mechanismus bestimmt.

Im folgenden Diagramm sehen Sie, wo sich jede class in der classnhierarchie befindet ( größer ). TreeMap implementiert SortedMap und NavigableMap während HashMap das nicht tut.

HashTable ist veraltet und die entsprechende ConcurrentHashMap class sollte verwandt werden. Bildbeschreibung hier eingeben

Nur ein wenig mehr Input aus meiner eigenen Erfahrung mit Karten, wann ich sie benutzen würde:

  • HashMap – Am nützlichsten bei der Suche nach einer (schnellen) Best-Performance-Implementierung.
  • TreeMap (SortedMap-Schnittstelle) – Am nützlichsten, wenn ich in der Lage bin, die Schlüssel in einer bestimmten von mir definierten Reihenfolge zu sortieren oder zu iterieren.
  • LinkedHashMap – Kombiniert Vorteile der garantierten Bestellung von TreeMap ohne die erhöhten Kosten für die Pflege der TreeMap. (Es ist fast so schnell wie die HashMap). Insbesondere bietet die LinkedHashMap auch einen guten Ausgangspunkt für das Erstellen eines Cache-Objekts durch Überschreiben der removeEldestEntry() -Methode. Auf diese Weise können Sie ein Cache-Objekt erstellen, das Daten anhand bestimmter von Ihnen definierter Kriterien ablaufen lässt.

HashMap

  • Es hat Paarwerte (Schlüssel, Werte)
  • KEINE Duplikationsschlüsselwerte
  • ungeordnet unsortiert
  • Es erlaubt einen Null-Schlüssel und mehrere Null-Werte

Hash-tabelle

  • Gleich wie Hash-Karte
  • Es erlaubt keine Null-Schlüssel und Null-Werte

LinkedHashMap

  • Es ist eine geordnete Version der Kartenimplementierung
  • Basierend auf verknüpften Listen- und Hashing-Datenstrukturen

Baumkarte

  • Bestellte und sortierte Version
  • basierend auf Hashing-Datenstrukturen

Alle drei classn HashMap , TreeMap und LinkedHashMap implementieren die java.util.Map Schnittstelle und repräsentieren die Zuordnung von einem eindeutigen Schlüssel zu Werten.

HashMap

  1. Eine HashMap enthält Werte basierend auf dem Schlüssel.

  2. Es enthält nur einzigartige Elemente.

  3. Es kann einen Nullschlüssel und mehrere Nullwerte haben.

  4. Es behält keine Reihenfolge bei .

    public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

LinkedHashMap

  1. Eine LinkedHashMap enthält Werte basierend auf dem Schlüssel.
  2. Es enthält nur einzigartige Elemente.
  3. Es kann einen Nullschlüssel und mehrere Nullwerte haben.
  4. Es ist dasselbe wie HashMap stattdessen die Reihenfolge der Anzeigen verwaltet. // Siehe classnverzögerung unten

    public class LinkedHashMap extends HashMap implements Map

Baumkarte

  1. Eine TreeMap enthält Werte basierend auf dem Schlüssel. Es implementiert die NavigableMap-Schnittstelle und erweitert die AbstractMap-class.
  2. Es enthält nur einzigartige Elemente.
  3. Es kann keinen Null-Schlüssel haben, aber mehrere Null-Werte haben.
  4. Es ist dasselbe wie HashMap stattdessen aufsteigende Reihenfolge verwaltet (Sortiert mit der natürlichen Reihenfolge seines Schlüssels).

    public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, Serializable

Hash-tabelle

  1. Ein Hashtable ist ein Array von Listen. Jede Liste wird als Bucket bezeichnet. Die Position des Buckets wird durch Aufrufen der Methode hashcode () ermittelt. Eine Hashtabelle enthält Werte basierend auf dem Schlüssel.
  2. Es enthält nur einzigartige Elemente.
  3. Es darf keinen Nullschlüssel oder -wert haben.
  4. Es ist synchronisiert .
  5. Es ist eine Legacy-class.

    public class Hashtable extends Dictionary implements Map, Cloneable, Serializable

Ref: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

HashMap gibt absolut keine Garantie für die Iterationsreihenfolge. Es kann (und wird) sich sogar komplett ändern, wenn neue Elemente hinzugefügt werden. TreeMap wird gemäß der “natürlichen Ordnung” der Schlüssel gemäß ihrer compareTo () – Methode (oder eines extern gelieferten Komparators) iterieren. Darüber hinaus implementiert es die Schnittstelle “SortedMap”, die Methoden enthält, die von dieser Sortierreihenfolge abhängen. LinkedHashMap wird in der Reihenfolge durchlaufen, in der die Einträge in die Map eingefügt wurden

Schau dir an, wie die performance variiert .. Bildbeschreibung hier eingeben

Baumkarte, die eine Implementierung der sortierten Karte ist. Die Komplexität der Operationen put, get und containsKey ist O (log n) aufgrund der natürlichen Reihenfolge

Lass es mich einfach sagen:

  • HashMap ist als Hash-Tabelle implementiert, und es gibt keine Reihenfolge für Schlüssel oder Werte.
  • TreeMap wird basierend auf der rot-schwarzen Baumstruktur implementiert und ist nach dem Schlüssel geordnet.
  • LinkedHashMap behält den Anzeigenauftrag bei
  • Hashtable ist im Gegensatz zu HashMap synchronisiert. Es hat einen Overhead für die Synchronisation. Dies ist der Grund, dass HashMap verwendet werden sollte, wenn das Programm Thread-sicher ist.

@Amit: SortedMap ist eine Schnittstelle, während TreeMap eine class ist, die die Schnittstelle ” SortedMap implementiert. Das bedeutet, wenn das Protokoll folgt, das SortedMap seinen Implementierern verlangt. Ein Baum, sofern er nicht als Suchbaum implementiert ist, kann keine geordneten Daten liefern, da der Baum ein beliebiger Baum sein kann. Damit TreeMap wie Sorted order arbeitet, implementiert es SortedMap (zB Binary Search Tree – BST, balanced BST wie AVL und RB Tree, sogar Ternary Search Tree – wird meist für geordnete Suche in geordneter Weise verwendet).

 public class TreeMap extends AbstractMap implements SortedMap, Cloneable, Serializable 

In NUT-SHELL HashMap : gibt Daten in O (1), keine Reihenfolge

TreeMap : gibt Daten in O (log N), Basis 2. mit geordneten Schlüsseln

LinkedHashMap : ist Hash-Tabelle mit verknüpfter Liste (denke an indizierte-SkipList) -function zum Speichern von Daten in der Art, wie es in den Baum eingefügt wird. Bestens geeignet für die Implementierung von LRU (zuletzt verwendet).

Die folgenden Unterschiede bestehen zwischen HashMap und TreeMap

  1. HashMap behält keine Reihenfolge bei. Mit anderen Worten, HashMap bietet keine Garantie dafür, dass das zuerst eingefügte Element zuerst gedruckt wird, sondern genauso wie TreeSet auch TreeMap-Elemente nach der natürlichen Reihenfolge ihrer Elemente sortiert werden

  2. Die interne HashMap-Implementierung verwendet Hashing und TreeMap verwendet intern die Rot-Schwarz-Baumimplementierung.

  3. HashMap kann einen Nullschlüssel und viele Nullwerte speichern. TreeMap kann keine Nullschlüssel enthalten, aber viele Nullwerte.

  4. HashMap nimmt konstante Zeit für die grundlegenden Operationen wie get und put, dh O (1). Laut Oracle Docs bietet TreeMap garantierte log (n) Zeit Kosten für die Get und Put-Methode.

  5. HashMap ist viel schneller als TreeMap, da die performanceszeit von HashMap für die meisten Operationen gegenüber der Protokollierungszeit TreeMap konstant ist.

  6. HashMap verwendet die equals () -Methode im Vergleich, während TreeMap die compareTo () -Methode zur Aufrechterhaltung der Reihenfolge verwendet.

  7. HashMap implementiert die Map-Schnittstelle, während TreeMap die NavigableMap-Schnittstelle implementiert.

Dies sind verschiedene Implementierungen der gleichen Schnittstelle. Jede Implementierung hat einige Vorteile und einige Nachteile (schnelles Einfügen, langsame Suche) oder umgekehrt.

Für Details sehen Sie sich das Javadoc von TreeMap , HashMap , LinkedHashMap an .

Hash-Map behält den Anzeigenauftrag nicht bei.
Beispiel. Hashmap Wenn Sie Schlüssel als einfügen

 1 3 5 9 4 6 7 15 3 10 

Es kann es als speichern

 4 6 5 9 3 10 1 3 7 15 

Verknüpfte Hashmap behält die Reihenfolge der Anzeigen bei.

Beispiel.
Wenn Sie Schlüssel einfügen

 1 3 5 9 4 6 7 15 3 10 

Es speichert es als

 1 3 5 9 4 6 7 15 3 10 

So wie wir einfügen.

Die Baumkarte speichert die Werte in der Reihenfolge der Schlüssel. Beispiel.
Wenn Sie Schlüssel einfügen

 1 3 5 9 4 6 7 15 3 10 

Es speichert es als

 1 3 3 10 4 6 5 9 7 15 

Alle bieten eine Key-> Value-Map und eine Möglichkeit, die Schlüssel zu durchlaufen. Die wichtigste Unterscheidung zwischen diesen classn sind die Zeitgarantien und die Reihenfolge der Schlüssel.

  1. HashMap bietet 0 (1) Nachschlagen und Einfügen. Wenn Sie jedoch die Schlüssel durchlaufen, ist die Reihenfolge der Schlüssel im Wesentlichen beliebig. Es wird durch ein Array von verknüpften Listen implementiert.
  2. TreeMap bietet O (log N) Lookup und Einfügen. Die Schlüssel sind geordnet. Wenn Sie also die Schlüssel in sortierter Reihenfolge durchlaufen müssen, können Sie das tun. Dies bedeutet, dass Schlüssel die Vergleichsschnittstelle implementieren müssen. TreeMap wird von einem Rot-Schwarz-Baum implementiert.
  3. LinkedHashMap bietet 0 (1) Nachschlagen und Einfügen. Schlüssel werden nach ihrem Anzeigenauftrag sortiert. Es wird von doppelt verbundenen Buckets implementiert.

Stellen Sie sich vor, Sie haben eine leere TreeMap, HashMap und LinkedHashMap in die folgende function übergeben:

 void insertAndPrint(AbstractMap map) { int[] array= {1, -1, 0}; for (int x : array) { map.put(x, Integer.toString(x)); } for (int k: map.keySet()) { System.out.print(k + ", "); } } 

Die Ausgabe für jedes wird wie folgt aussehen.

Für HashMap war die Ausgabe in meinen eigenen Tests {0, 1, -1}, aber es könnte eine beliebige Reihenfolge sein. Es gibt keine Garantie auf die Bestellung.
Treemap, die Ausgabe war, {-1, 0, 1}
LinkedList, die Ausgabe war {1, -1, 0}

  • HashMap:

    • Auftrag wird nicht aufrechterhalten
    • Schneller als HashMap und LinkedHashMap
    • Wird für den Heapspeicher von Objekten verwendet
  • LinkedHashMap:

    • Der LinkedHashMap-Anzeigenauftrag wird beibehalten
    • Langsamer als HashMap und schneller als TreeMap
    • Wenn Sie einen Anzeigenauftrag beibehalten möchten, verwenden Sie diesen.
  • Baumkarte:

    • TreeMap ist ein baumbasiertes Mapping
    • TreeMap folgt der natürlichen Reihenfolge der Schlüssel
    • Langsamer als HashMap und LinkedHashMap
    • Verwenden Sie TreeMap, wenn Sie eine natürliche (Standard) Bestellung durchführen müssen

HashMap
Kann einen Nullschlüssel enthalten.

HashMap behält keine Reihenfolge bei.

Baumkarte

TreeMap darf keinen Nullschlüssel enthalten.

TreeMap wird in aufsteigender Reihenfolge verwaltet.

LinkedHashMap

LinkedHashMap kann verwendet werden, um die Reihenfolge der Einfügungen zu verwalten, auf denen Schlüssel in Map eingefügt werden, oder es kann auch verwendet werden, um eine Zugriffsreihenfolge aufrechtzuerhalten, auf die auf Schlüssel zugegriffen wird.

Beispiele ::

1) HashMap map = neue HashMap ();

  map.put(null, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir");`enter code here` map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 

2) TreeMap Karte = neue TreeMap ();

  map.put(1, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir"); map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 

3) LinkedHashMap map = neu LinkedHashMap ();

  map.put(1, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir"); map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); }