webentwicklung-frage-antwort-db.com.de

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 haben. Was sind Hashtables?

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());
908
Kevin

Alle drei Klassen implementieren die Schnittstelle Map und bieten größtenteils dieselbe Funktionalität. Der wichtigste Unterschied ist die Reihenfolge, in der die Einträge durchlaufen werden:

  • HashMap übernimmt keinerlei Garantie für die Iterationsreihenfolge. Es kann (und wird) sich sogar vollständig ändern, wenn neue Elemente hinzugefügt werden.
  • TreeMap iteriert entsprechend der "natürlichen Reihenfolge" der Schlüssel entsprechend ihrer compareTo() -Methode (oder einem extern bereitgestellten Comparator). Darüber hinaus implementiert es die Schnittstelle SortedMap , die Methoden enthält, die von dieser Sortierreihenfolge abhängen.
  • LinkedHashMap iteriert in der Reihenfolge, in der die Einträge in die Map eingefügt wurden

"Hashtable" ist der generische Name für Hash-basierte Maps. Im Kontext der Java-API ist Hashtable eine veraltete Klasse aus den Tagen von Java 1.1, bevor das Auflistungsframework existierte. Es sollte nicht mehr verwendet werden, da die API mit veralteten Methoden überfüllt ist, die die Funktionalität duplizieren, und die Methoden synchronisiert sind (was die Leistung verringern kann und im Allgemeinen unbrauchbar ist). Verwenden Sie ConcurrentHashMap anstelle von Hashtable.

1120

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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝
1542
Sergii Shevchyk

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

  1. HashMap ist eine Map, 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() haben, damit dies funktioniert.

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

  3. TreeMap ist eine baumbasierte Zuordnung. Seine Put/Get-Operationen benötigen O (log n) -Zeit. Es erfordert Elemente, die über einen Vergleichsmechanismus verfügen, entweder mit Comparable oder Comparator. Die Iterationsreihenfolge wird durch diesen Mechanismus bestimmt.

62
Eyal Schneider

Sehen Sie in der folgenden Abbildung, wo sich jede Klasse in der Klassenhierarchie befindet ( größere ). TreeMap implementiert SortedMap und NavigableMap, während HashMap dies nicht tut.

HashTable ist veraltet und die entsprechende Klasse ConcurrentHashMap sollte verwendet werden. enter image description here

44
pierrotlefou

HashMap

  • Es hat Paarwerte (Schlüssel, Werte)
  • KEINE doppelten Schlüsselwerte
  • ungeordnet unsortiert
  • es erlaubt einen Nullschlüssel und mehr als einen Nullwert

Hash-tabelle

  • das gleiche wie die Hash-Karte
  • es sind keine Nullschlüssel und Nullwerte zulässig

LinkedHashMap

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

TreeMap

  • Bestellte und sortierte Version
  • basierend auf Hash-Datenstrukturen
37
Prem Kumar

Noch ein paar Anmerkungen aus meiner eigenen Erfahrung mit Karten, wann ich jede verwenden würde:

  • HashMap - Am nützlichsten, wenn Sie nach einer (schnellen) Implementierung mit der besten Leistung suchen.
  • TreeMap (SortedMap-Schnittstelle) - Am nützlichsten, wenn ich in der Lage bin, die Schlüssel in einer von mir definierten Reihenfolge zu sortieren oder zu iterieren.
  • LinkedHashMap - Kombiniert die Vorteile einer garantierten Bestellung bei 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 hervorragenden Ausgangspunkt zum Erstellen eines Cache-Objekts durch Überschreiben der removeEldestEntry() -Methode. Auf diese Weise können Sie ein Cache-Objekt erstellen, dessen Daten nach bestimmten von Ihnen definierten Kriterien verfallen können.
35
Ogre Psalm33

Alle drei Klassen HashMap, TreeMap und LinkedHashMap implementieren die Schnittstelle Java.util.Map und repräsentieren die Zuordnung von eindeutigen Schlüsseln zu Werten.

HashMap

  1. Ein HashMap enthält Werte, die auf dem Schlüssel basieren.

  2. Es enthält nur eindeutige Elemente.

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

  4. Es bleibt keine Reihenfolge .

    public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

  1. Ein LinkedHashMap enthält Werte basierend auf dem Schlüssel.
  2. Es enthält nur eindeutige Elemente.
  3. Es kann einen Nullschlüssel und mehrere Nullwerte haben.
  4. Es ist dasselbe wie bei HashMap, das stattdessen die Einfügereihenfolge beibehält. // Siehe Klassenverzögerung unten

    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

TreeMap

  1. Ein TreeMap enthält Werte basierend auf dem Schlüssel. Es implementiert die NavigableMap-Schnittstelle und erweitert die AbstractMap-Klasse.
  2. Es enthält nur eindeutige Elemente.
  3. Es kann keinen Nullschlüssel, aber mehrere Nullwerte haben.
  4. Es ist dasselbe wie HashMap, behält stattdessen aufsteigende Reihenfolge (Sortiert nach der natürlichen Reihenfolge von sein Schlüssel.).

    public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

Hashtable

  1. Eine Hashtable ist ein Array von Listen. Jede Liste wird als Bucket bezeichnet. Die Position des Buckets wird durch Aufrufen der hashcode () -Methode identifiziert. Eine Hashtabelle enthält Werte, die auf dem Schlüssel basieren.
  2. Es enthält nur eindeutige Elemente.
  3. Möglicherweise hat es keinen Nullschlüssel oder -wert.
  4. Es ist synchronisiert .
  5. Es ist eine Legacy-Klasse.

    public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

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

17
roottraveller

HashMap übernimmt keinerlei Gewähr für die Iterationsreihenfolge. Es kann (und wird) sich sogar vollständig ändern, wenn neue Elemente hinzugefügt werden. TreeMap iteriert entsprechend der "natürlichen Reihenfolge" der Schlüssel gemäß ihrer compareTo () - Methode (oder einem extern bereitgestellten Komparator). Darüber hinaus wird die SortedMap-Schnittstelle implementiert, die Methoden enthält, die von dieser Sortierreihenfolge abhängen. LinkedHashMap iteriert in der Reihenfolge, in der die Einträge in die Map eingefügt wurden

Sehen Sie sich an, wie unterschiedlich die Leistung ist. enter image description here

Baumkarte, die eine Implementierung der sortierten Karte ist. Die Komplexität der Operation put, get und containKey ist aufgrund der Natural-Reihenfolge O (log n)

@Amit: SortedMap ist eine Schnittstelle, während TreeMap eine Klasse ist, die die Schnittstelle SortedMap implementiert. Das heißt, wenn das Protokoll befolgt wird, das SortedMap von seinen Implementierern verlangt. Ein Baum, der nicht als Suchbaum implementiert ist, kann keine geordneten Daten liefern, da es sich bei dem Baum um einen beliebigen Baum handeln kann. Damit TreeMap wie eine sortierte Reihenfolge funktioniert, wird SortedMap implementiert (z. B. Binary Search Tree - BST, ausgeglichenes BST wie AVL und R-B Tree, sogar Ternary Search Tree - wird meistens für iterative Suchen in geordneter Reihenfolge verwendet).

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

In NUT-Shell HashMap: gibt Daten in O(1) ohne Reihenfolge an

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

LinkedHashMap: Ist eine Hash-Tabelle mit verknüpfter Liste (denken Sie an indexed-SkipList), um Daten so zu speichern, wie sie in den Baum eingefügt werden. Am besten geeignet für die Implementierung von LRU (zuletzt verwendet).

9
siddhusingh

Es folgen die wichtigsten Unterschiede 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. Wie TreeSet werden auch TreeMap-Elemente nach der natürlichen Reihenfolge ihrer Elemente sortiert

  2. Interne HashMap-Implementierung verwendet Hashing und TreeMap verwendet intern die Rot-Schwarz-Baum-Implementierung.

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

  4. HashMap benötigt eine konstante Zeitleistung für die grundlegenden Operationen wie get und put, d. H. O (1). Gemäß Oracle-Dokumenten bietet TreeMap garantierte Protokollzeitkosten für die get- und put-Methode.

  5. HashMap ist viel schneller als TreeMap, da die Leistungszeit von HashMap für die meisten Vorgänge gegenüber der Protokollzeit von TreeMap konstant ist.

  6. HashMap verwendet im Vergleich die Methode equals (), während TreeMap die Methode compareTo () verwendet, um die Reihenfolge aufrechtzuerhalten.

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

6
Vijay Barot

Dies sind verschiedene Implementierungen derselben Schnittstelle. Jede Implementierung hat einige Vor- und einige Nachteile (schnelles Einfügen, langsame Suche) oder umgekehrt.

Einzelheiten finden Sie im Javadoc von TreeMap , HashMap , LinkedHashMap .

5
tangens
  • HashMap:

    • Bestellung nicht aufrechterhalten
    • Schneller als LinkedHashMap
    • Wird für den Speicherhaufen von Objekten verwendet
  • LinkedHashMap:

    • Die Anzeigereihenfolge von LinkedHashMap wird beibehalten
    • Langsamer als HashMap und schneller als TreeMap
    • Wenn Sie einen Anzeigenauftrag pflegen möchten, verwenden Sie diesen.
  • TreeMap:

    • TreeMap ist eine baumbasierte Zuordnung
    • TreeMap folgt der natürlichen Reihenfolge der Schlüssel
    • Langsamer als HashMap und LinkedHashMap
    • Verwenden Sie TreeMap, wenn Sie die natürliche (Standard-) Reihenfolge beibehalten möchten
4
Premraj

Die Hash-Map behält die Einfügereihenfolge nicht bei.
Beispiel. Hashmap Wenn Sie Schlüssel einfügen als

1  3
5  9
4   6
7   15
3   10

Es kann es speichern als

4  6
5  9
3  10
1  3
7  15

Verknüpfte Hashmap behält die Einfügereihenfolge bei.

Beispiel.
Wenn Sie Schlüssel einfügen

1  3
5  9
4   6
7   15
3   10

Es wird gespeichert als

1  3
5  9
4   6
7   15
3   10

das gleiche wie wir einfügen.

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

1  3
5  9
4   6
7   15
3   10

Es wird gespeichert als

1  3
3  10
4   6
5   9
7   15
3
Shivam Shukla

Alle bieten eine Schlüssel-> Wertzuordnung und eine Möglichkeit, die Schlüssel zu durchlaufen. Der wichtigste Unterschied zwischen diesen Klassen 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 eine Reihe von verknüpften Listen implementiert.
  2. TreeMap bietet das Nachschlagen und Einfügen von O (log N). Die Schlüssel sind sortiert. Wenn Sie also die Schlüssel in sortierter Reihenfolge durchlaufen müssen, können Sie dies tun. Dies bedeutet, dass Schlüssel die Schnittstelle Comparable implementieren müssen. TreeMap wird von einem Rot-Schwarz-Baum implementiert.
  3. LinkedHashMap bietet 0(1) Nachschlagen und Einfügen. Die Schlüssel werden in der Reihenfolge ihrer Einfügung sortiert. Es wird durch doppelt verknüpfte Buckets implementiert.

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

void insertAndPrint(AbstractMap<Integer, String> 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 Element sieht wie folgt aus.

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

1
Jitendra

HashMap
kann einen Nullschlüssel enthalten.

HashMap behält keine Reihenfolge bei.

TreeMap

TreeMap darf keinen Nullschlüssel enthalten.

TreeMap behält die aufsteigende Reihenfolge bei.

LinkedHashMap

LinkedHashMap kann verwendet werden, um die Einfügereihenfolge beizubehalten, in der die Schlüssel in Map eingefügt werden, oder um eine Zugriffsreihenfolge beizubehalten, in der auf die Schlüssel zugegriffen wird.

Beispiele ::

1) HashMap map = new 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 map = new 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 = new 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());
    }
0
Kamran