Wann wird HashMap über LinkedList oder ArrayList verwendet und umgekehrt?

80

Was ist der Grund, warum wir eine HashMap nicht immer verwenden können, obwohl sie beim Hinzufügen und Entfernen von Operationen viel effizienter ist als ArrayList oder LinkedList, auch unabhängig von der Anzahl der Elemente.

Ich habe es gegoogelt und einige Gründe gefunden, aber es gab immer eine Problemumgehung für die Verwendung von HashMap, wobei die Vorteile noch bestehen.

java arrays arraylist linked-list hashmap
quelle
11
Listsund Mapssind zwei völlig unterschiedliche Datenstrukturen mit unterschiedlichen Operationen und Invarianten. Können Sie den Kontext / die Anforderungen erklären, an die Sie denken, wo beide akzeptable Lösungen wären?
Mark Peters
3
Anscheinend mussten Sie nie eine Reihe von Dingen in einer bestimmten Reihenfolge halten ...
Brian Roach
52
Downvote, warum? Ich denke, das ist eine richtige Frage. Zeigt zwar mangelndes Wissen, aber auf SO sollte die Frage nicht wegen mangelnden Wissens herabgestuft werden. Tatsächlich ist eine Frage immer ein Ergebnis mangelnden Wissens.

Antworten:

96

Listen repräsentieren eine sequentielle Reihenfolge von Elementen. Karten werden verwendet, um eine Sammlung von Schlüssel / Wert-Paaren darzustellen.

Während Sie eine Karte als Liste verwenden könnten, gibt es einige eindeutige Nachteile.

Reihenfolge beibehalten: - Eine Liste wird per Definition bestellt. Sie fügen Elemente hinzu und können dann die Liste in der Reihenfolge durchlaufen, in der Sie die Elemente eingefügt haben. Wenn Sie einer HashMap Elemente hinzufügen, wird nicht garantiert, dass Sie die Elemente in derselben Reihenfolge abrufen, in der Sie sie abgelegt haben. Es gibt Unterklassen von HashMap wie LinkedHashMap, die die Reihenfolge beibehalten, aber im Allgemeinen wird die Reihenfolge mit einer Map nicht garantiert.

Schlüssel- / Wertsemantik: - Der Zweck einer Karte besteht darin, Elemente basierend auf einem Schlüssel zu speichern, mit dem das Element zu einem späteren Zeitpunkt abgerufen werden kann. Eine ähnliche Funktionalität kann mit einer Liste nur in dem begrenzten Fall erreicht werden, in dem der Schlüssel zufällig die Position in der Liste ist.

Lesbarkeit des Codes Betrachten Sie die folgenden Beispiele. 

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

Sammlungsfunktionalität Einige großartige Dienstprogrammfunktionen stehen für Listen über die Sammlungsklasse zur Verfügung. Zum Beispiel ...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);

Hoffe das hilft,

Polster
quelle
LinkedLists werden häufig aufgrund von Leistungsproblemen als schlecht bezeichnet. Aufgrund der Reihenfolge der Elemente verwende ich häufig LinkedLists über ArrayLists. Wäre es besser (für Leistung und Speicher), wenn ich HashMaps mit Positionen als Schlüssel verwenden würde?
Cesar Castro
33

Listen und Karten sind unterschiedliche Datenstrukturen. Karten werden verwendet, wenn Sie einen Schlüssel einem Wert zuordnen möchten und Listen eine geordnete Sammlung sind.

Map ist eine Schnittstelle im Java Collection Framework und eine HashMap ist eine Implementierung der Map-Schnittstelle. HashMap ist effizient zum Auffinden eines Werts basierend auf einem Schlüssel und zum Einfügen und Löschen von Werten basierend auf einem Schlüssel. Die Einträge einer HashMap sind nicht geordnet.

ArrayList und LinkedList sind eine Implementierung der List-Schnittstelle. LinkedList bietet sequenziellen Zugriff und ist im Allgemeinen effizienter beim Einfügen und Löschen von Elementen in die Liste, jedoch weniger effizient beim Zugriff auf Elemente in einer Liste. ArrayList bietet Direktzugriff und ist effizienter beim Zugriff auf Elemente, beim Einfügen und Löschen von Elementen jedoch im Allgemeinen langsamer.

Jazzdawg
quelle
0

Der Nachteil von ArrayList und LinkedList besteht darin, dass beim Durchlaufen je nach Suchalgorithmus die Zeit zum Auffinden eines Elements mit der Größe der Liste zunimmt.

Das Schöne am Hashing ist, dass Sie zwar etwas mehr Zeit für die Suche nach dem Element opfern, die benötigte Zeit jedoch nicht mit der Größe der Karte wächst. Dies liegt daran, dass die HashMap Informationen findet, indem sie das gesuchte Element direkt in den Index konvertiert, damit der Sprung ausgeführt werden kann.

Lange Rede, kurzer Sinn ... LinkedList : Verbraucht etwas mehr Speicher als ArrayList, geringe Kosten für Einfügungen (Hinzufügen und Entfernen) ArrayList : Verbraucht wenig Speicher, ähnelt jedoch LinkedList und benötigt zusätzliche Zeit für die Suche, wenn sie groß ist. HashMap : Kann einen Sprung zum Wert ausführen, wodurch die Suchzeit für große Karten konstant bleibt. Verbraucht mehr Speicher und dauert länger, um den Wert zu finden als kleine Listen.

Simon Walker
quelle
0

Ich werde hier einige reale Fallbeispiele und Szenarien vorstellen, wann das eine oder andere verwendet werden soll. Dies könnte für jemand anderen hilfreich sein:

HashMap

Wenn Sie den Cache in Ihrer Anwendung verwenden müssen. Redis und membase sind eine Art erweiterte HashMap. (Unabhängig von der Reihenfolge der Elemente benötigen Sie einen schnellen (O (1)) Lesezugriff (einen Wert) mit einem Schlüssel.)

LinkedList

Wenn die Reihenfolge wichtig ist (sie werden so sortiert, wie sie zur LinkedList hinzugefügt wurden), ist die Anzahl der Elemente unbekannt (keine Speicherzuweisung verschwenden) und Sie benötigen eine schnelle Einfügezeit (O (1)). Ein gutes Beispiel ist eine Liste von Aufgaben, die beim Hinzufügen nacheinander aufgelistet werden können.

vhbazan
quelle