Java geordnete Karte

322

Gibt es in Java ein Objekt, das sich wie eine Map zum Speichern und Zugreifen auf Schlüssel / Wert-Paare verhält, jedoch eine geordnete Liste von Schlüsseln und eine geordnete Liste von Werten zurückgeben kann, sodass die Schlüssel- und Wertelisten in derselben Reihenfolge liegen?

Als Erklärung durch Code suche ich nach etwas, das sich wie meine fiktive OrderedMap verhält:

OrderedMap<Integer, String> om = new OrderedMap<>();
om.put(0, "Zero");
om.put(7, "Seven");

String o = om.get(7); // o is "Seven"
List<Integer> keys = om.getKeys();
List<String> values = om.getValues();

for(int i = 0; i < keys.size(); i++)
{
    Integer key = keys.get(i);
    String value = values.get(i);
    Assert(om.get(key) == value);
}
Was ist es
quelle
4
Wenn Sie nur beide gleichzeitig durchlaufen möchten, können Sie dies mit Map.entrySet () auf jeder Karte tun. Die LinkedHashMap hat eine genau definierte Reihenfolge, aber für jede Map spiegelt der Eintragssatz die Schlüssel / Wert-Paare wider.
Pete Kirkham
5
Dieser Code ist kein gutes Beispiel, da sich jede Map-Implementierung wie Ihr Beispielcode verhält. sortiert, bestellt oder nicht.
Peter Lawrey
2
In der Sun JDK-Implementierung werden die von getKeys- und getValues ​​() -Sätzen zurückgegebenen Mengen durch entrySet () in der Map unterstützt, sodass sie dieselbe Iterationsreihenfolge haben, die in Ihrem Beispiel getestet wird.
Pete Kirkham
4
Das ist interessant, das habe ich nie bemerkt. Nennen Sie mich trotzdem verrückt, aber ich ziehe es vor, keine Annahmen über die Implementierung zu treffen, die nicht explizit von der Schnittstelle überprüft werden. Ich bin in der Vergangenheit zu oft verbrannt worden.
Whatsit
2
Dies sollte als Java Sorted Map bezeichnet werden, da die geordnete Karte etwas anderes ist - siehe LinkedHashMap.
Ondra Žižka

Antworten:

397

Die SortedMap- Schnittstelle (mit der Implementierung TreeMap ) sollte Ihr Freund sein.

Die Schnittstelle hat die Methoden:

  • keySet() Dies gibt einen Satz der Schlüssel in aufsteigender Reihenfolge zurück
  • values() Dies gibt eine Sammlung aller Werte in aufsteigender Reihenfolge der entsprechenden Schlüssel zurück

Diese Schnittstelle erfüllt also genau Ihre Anforderungen. Die Schlüssel müssen jedoch eine aussagekräftige Reihenfolge haben. Andernfalls können Sie die LinkedHashMap verwenden, bei der die Reihenfolge durch die Einfügereihenfolge bestimmt wird.

dmeister
quelle
2
Beispiel: SortedMap <String, Object> map = new TreeMap <> ();
Ben
7
Um TreeMap verwenden zu können, muss die Schlüsselklasse eine vergleichbare Schnittstelle implementieren. Wenn nicht, wird eine Art RuntimeException ausgelöst. TreeMap ist auch eine sortierte Karte, aber ich denke, der Autor möchte nur eine geordnete (nicht sortierte) Karte verwenden. LinkedHashMap ist eine gute Wahl, um nur eine geordnete Karte zu erhalten (wie Sie sagten, "bestimmt durch die Einfügereihenfolge").
K. Gol
1
Diese Antwort könnte verbessert werden, indem gezeigt wird, wie man über keySet ()
4
Von Java 8 doc . LinkedHashMapderen Reihenfolge der Iteration ist die Reihenfolge, in der zuletzt auf seine Einträge zugegriffen wurde
TRiNE
1
@TRiNE Ich folge Ihrem Kommentar nicht, habe aber möglicherweise einen Kontext übersehen. Standardmäßig ist LinkedHashMapdie Iterationsreihenfolge die Einfügereihenfolge. Sie können jedoch stattdessen einen anderen Konstruktor verwenden, um die Zugriffsreihenfolge anzugeben. docs.oracle.com/javase/8/docs/api/java/util/…
Rob
212

Gibt es ein Objekt, das sich wie eine Map zum Speichern und Zugreifen auf Schlüssel / Wert-Paare verhält, aber eine geordnete Liste von Schlüsseln und eine geordnete Liste von Werten zurückgeben kann, sodass die Schlüssel- und Wertelisten in derselben Reihenfolge sind?

Sie suchen nach java.util.LinkedHashMap . Sie erhalten eine Liste der Map.Entry <K, V> -Paare, die immer in derselben Reihenfolge wiederholt werden. Diese Reihenfolge entspricht der Reihenfolge, in der Sie die Elemente eingeben . Alternativ können Sie auch die Datei java.util.SortedMap verwenden , bei der die Schlüssel entweder eine natürliche Reihenfolge haben oder durch a angegeben werden müssen Comparator.

John Feminella
quelle
14
Und damit der Leser dies nicht noch einmal überprüft, gibt die keySet()Methode effektiv ein LinkedHashSet zurück, das die Reihenfolge Ihrer put()Aufrufe widerspiegelt . Beachten Sie, dass wiederholte Anrufe put()für denselben Schlüssel die Reihenfolge nur ändern, wenn Sie zuvor remove()den Schlüssel eingegeben haben.
Glenn Lawrence
Von Java 8 doc . LinkedHashMapderen Reihenfolge der Iteration ist die Reihenfolge, in der zuletzt auf seine Einträge zugegriffen wurde
TRiNE
23

LinkedHashMap behält die Reihenfolge der Schlüssel bei.

java.util.LinkedHashMap scheint ansonsten genau wie eine normale HashMap zu funktionieren.

VoNWooDSoN
quelle
1
Dies gibt keine Antwort auf die Frage. Um einen Autor zu kritisieren oder um Klärung zu bitten, hinterlassen Sie einen Kommentar unter seinem Beitrag. Sie können jederzeit Ihre eigenen Beiträge kommentieren. Sobald Sie einen ausreichenden Ruf haben, können Sie jeden Beitrag kommentieren .
ianaya89
2
@ ianaya89 Ich denke, das ist eine echte Antwort, aber sie ist der Antwort von John Feminella sehr ähnlich !
T30
1
Wenn Sie eine geordnete Karte erhalten möchten, in der die Einträge in dieser Reihenfolge gespeichert werden, während Sie sie in die Karte einfügen, ist eine LinkedHashMap die richtige Antwort. Wenn Sie die Einträge in Ihrer Karte unabhängig von der Reihenfolge sortieren möchten, in der Sie sie eingegeben haben, ist eine SortedMap die richtige Antwort.
Ralph
@TRiNE Das von Ihnen verlinkte Java 8-Dokument gibt an, dass zwei Bestellmodi möglich sind: Einfügereihenfolge und Zugriffsreihenfolge. Sie denken an Letzteres, das durch die Verwendung eines speziellen Konstruktors public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder) aufgerufen wird. Der Standardkonstruktor erstellt eine LinkedHashMap-Instanz mit Einfügungsreihenfolge.
Artur Łysik
1
@ ArturŁysik ja das ist es. Es war ein Fehler, den ich vor Tagen gemacht habe. Ich werde es korrigieren. Ich lösche den Kommentar. da ich es nicht mehr bearbeiten kann
TRiNE
7

Ich denke, die nächste Sammlung, die Sie vom Framework erhalten, ist die SortedMap

bruno conde
quelle
3
Ich würde diese Antwort ablehnen, wenn ich der Meinung wäre, dass es sich lohnt, die Punkte dafür zu verlieren. Wie aus der obigen Antwort hervorgeht, fehlen Ihrer Antwort die richtigen Informationen zu LinkedHashMap, und eine kleine Erklärung von SortedMap wäre auch hilfreich.
CorayThan
@CorayThan, in diesem Fall stimmen Sie die besten Antworten ab, nicht andere, die richtig, aber nicht die besten sind ...
bruno conde
1
Das ist, was ich tat. Ich sage nur, ich kann verstehen, warum jemand darüber abstimmen würde.
CorayThan
5

Sie können die NavigableMap- Oberfläche nutzen, auf die in aufsteigender oder absteigender Schlüsselreihenfolge zugegriffen und diese durchlaufen werden kann. Diese Schnittstelle soll die SortedMap-Schnittstelle ersetzen. Die navigierbare Karte wird normalerweise nach der natürlichen Reihenfolge ihrer Schlüssel oder nach einem Komparator sortiert, der zum Zeitpunkt der Kartenerstellung bereitgestellt wird.

Es gibt drei nützlichste Implementierungen davon: TreeMap , ImmutableSortedMap und ConcurrentSkipListMap .

TreeMap-Beispiel:

TreeMap<String, Integer> users = new TreeMap<String, Integer>();
users.put("Bob", 1);
users.put("Alice", 2);
users.put("John", 3);

for (String key: users.keySet()) {
  System.out.println(key + " (ID = "+ users.get(key) + ")");
}

Ausgabe:

Alice (ID = 2)
Bob (ID = 1)
John (ID = 3)
Vitalii Fedorenko
quelle
2

tl; dr

Damit Map< Integer , String >in einer Reihenfolge sortiert nach Schlüssel, verwenden Sie eine der beiden Klassen die Implementierung SortedMap/ NavigableMapSchnittstellen:

  • TreeMap
  • ConcurrentSkipListMap

Wenn Sie die Map innerhalb eines einzelnen Threads bearbeiten, verwenden Sie den ersten , TreeMap. Wenn Sie über mehrere Threads hinweg manipulieren, verwenden Sie die zweite Option.ConcurrentSkipListMap .

Einzelheiten finden Sie in der folgenden Tabelle und in der folgenden Diskussion.

Einzelheiten

Hier ist eine grafische Tabelle, die ich erstellt habe und die die Merkmale der Zehn zeigt Map mit Java 11 gebündelten Implementierungen .

Die NavigableMapSchnittstelle ist das, was SortedMapeigentlich hätte sein sollen. DasSortedMap sollte logisch entfernt werden, kann aber nicht sein, da einige Kartenimplementierungen von Drittanbietern möglicherweise eine Schnittstelle verwenden.

Wie Sie in dieser Tabelle sehen können, implementieren nur zwei Klassen die SortedMap/ NavigableMap-Schnittstellen:

Beide halten die Schlüssel in sortierter Reihenfolge, entweder nach ihrer natürlichen Reihenfolge (unter Verwendung der compareToMethode von Comparable( https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/). Comparable.html ) Schnittstelle) oder von einer ComparatorImplementierung, die Sie übergeben. Der Unterschied zwischen diesen beiden Klassen ist , dass die zweite, ConcurrentSkipListMapist threadsicher , hoch gleichzeitige .

Siehe auch die Spalte Iterationsreihenfolge in der folgenden Tabelle.

  • Die LinkedHashMapKlasse gibt ihre Einträge in der Reihenfolge zurück, in der sie ursprünglich eingefügt wurden .
  • EnumMapGibt Einträge in der Reihenfolge zurück, in der die Aufzählungsklasse des Schlüssels definiert ist . Beispielsweise verwendet eine Karte, deren Mitarbeiter welchen Wochentag abdeckt ( Map< DayOfWeek , Person >), die DayOfWeekin Java integrierte Enum-Klasse. Diese Aufzählung wird mit Montag zuerst und Sonntag zuletzt definiert. Einträge in einem Iterator werden also in dieser Reihenfolge angezeigt.

Die anderen sechs Implementierungen geben kein Versprechen über die Reihenfolge, in der sie ihre Einträge melden.

Tabelle der Kartenimplementierungen in Java 11 zum Vergleich ihrer Funktionen

Basil Bourque
quelle
0

Ich habe Simple Hash Map, verknüpfte Liste und Sammlungen verwendet , um eine Map nach Werten zu sortieren.

import java.util.*;
import java.util.Map.*;
public class Solution {

    public static void main(String[] args) {
        // create a simple hash map and insert some key-value pairs into it
        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("Python", 3);
        map.put("C", 0);
        map.put("JavaScript", 4);
        map.put("C++", 1);
        map.put("Golang", 5);
        map.put("Java", 2);
        // Create a linked list from the above map entries
        List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet());
        // sort the linked list using Collections.sort()
        Collections.sort(list, new Comparator<Entry<String, Integer>>(){
        @Override
         public int compare(Entry<String, Integer> m1, Entry<String, Integer> m2) {
        return m1.getValue().compareTo(m2.getValue());
        }
      });
      for(Entry<String, Integer> value: list) {
         System.out.println(value);
     }
   }
}

Die Ausgabe ist:

C=0
C++=1
Java=2
Python=3
JavaScript=4
Golang=5
Steffi Keran Rani J.
quelle