Betrachten Sie die folgende Java HashMap.

Map<String, String> unsortMap = new HashMap<String, String>();
unsortMap.put("Z", "z");
unsortMap.put("B", "b");
unsortMap.put("A", "a");
unsortMap.put("C", "c");

Jetzt möchte ich diese Karte nach Schlüssel sortieren. Eine Möglichkeit besteht darin, für diesen Zweck eine TreeMap zu verwenden.

Map<String, String> treeMap = new TreeMap<String, String>(unsortMap);

Eine andere Möglichkeit ist für mich, Java-Streams mit Sorted () wie folgt zu verwenden.

Map<String, Integer> sortedMap = new HashMap<>();
unsortMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey())
    .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));

Welche dieser beiden Optionen wird bevorzugt und warum (möglicherweise in Bezug auf die Leistung)?

Vielen Dank

3
Keet Sugathadasa 19 Jän. 2019 im 07:00

3 Antworten

Beste Antwort

Wie andere betonten, würde das Ablegen des sortierten Eintragsstroms in ein reguläres HashMap nichts bewirken ... LinkedHashMap ist die logische Wahl.

Eine Alternative zu den oben genannten Ansätzen besteht jedoch darin, die Stream Collectors - API vollständig zu nutzen.

Collectors verfügt über eine toMap -Methode, mit der Sie eine alternative Implementierung für Map bereitstellen können. Anstelle eines HashMap können Sie also nach einem LinkedHashMap fragen:

unsortedMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey())
    .collect(Collectors.toMap(
       Map.Entry::getKey,
       Map.Entry::getValue,
       (v1, v2) -> v1, // you will never merge though ask keys are unique.
       LinkedHashMap::new
    ));

Zwischen der Verwendung einer TreeMap und der LinkedHashMap ... Die Komplexität der Konstruktion ist wahrscheinlich dieselbe wie bei O (n log n) ... Offensichtlich ist die TreeMap -Lösung ein besserer Ansatz, wenn Sie weitere Elemente hinzufügen möchten dazu ... Ich denke, Sie hätten in diesem Fall mit einem TreeMap beginnen sollen. Die Option LinkedHashMap hat den Vorteil, dass die Suche auf der verknüpften oder der ursprünglichen unsortierten Karte O (1) ist, während TreeMap so etwas wie O(log n) ist, wenn Sie die unsortierte Karte beibehalten müssen Für eine effiziente Suche. Wenn Sie jedoch die LinkedHashMap erstellen, können Sie die ursprüngliche unsortierte Karte wegwerfen (wodurch Speicherplatz gespart wird).

Um die Effizienz mit LinkedHashMap zu verbessern, sollten Sie einen guten Schätzer für die erforderliche Größe bei der Erstellung bereitstellen, damit keine dynamische Größenänderung erforderlich ist. Anstelle von LinkedHashMap::new sagen Sie also () -> new LinkedHashMap<>(unsortedMap.size()) .

Ich bin der Meinung, dass die Verwendung eines TreeMap ordentlicher ist ... da der Code kleiner bleibt. Wenn also kein tatsächliches Leistungsproblem vorliegt, das mit dem unsortierten und sortierten Ansatz für verknüpfte Karten behoben werden könnte, würde ich den {{ X1}}.

2
Valentin Ruano 19 Jän. 2019 im 05:35

Ihr Stream-Code sortiert die Karte nicht einmal, da er die Operation für ein HashMap ausführt, das von Natur aus unsortiert ist. Damit Ihr zweites Stream-Beispiel funktioniert, können Sie LinkedHashMap verwenden, wodurch die Einfügereihenfolge beibehalten wird:

Map<String, Integer> sortedMap = new LinkedHashMap<>();
unsortMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey())
    .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));

Aber jetzt sind Ihre beiden Beispiele nicht einmal dieselbe zugrunde liegende Datenstruktur. Ein TreeMap wird von einem Baum unterstützt (rot schwarz, wenn ich mich richtig erinnere). Sie würden ein TreeMap verwenden, wenn Sie in der Lage sein möchten, sortiert zu iterieren oder schnell nach einem Schlüssel zu suchen. Eine LinkedHashMap ist eine Hashmap mit einer verknüpften Liste. Sie würden dies verwenden, wenn Sie die Einfügereihenfolge beibehalten müssen, beispielsweise beim Implementieren einer Warteschlange.

1
Tim Biegeleisen 19 Jän. 2019 im 04:06

Der zweite Weg funktioniert nicht. Wenn Sie HashMap#put aufrufen, wird die Put-Reihenfolge nicht gespeichert. Möglicherweise benötigen Sie LinkedHashMap.

TreeMap v.s. Stream (LinkedHashMap):

  1. Codestil. Die Verwendung von TreeMap ist sauberer, da Sie dies in einer Zeile erreichen können.
  2. Raumkomplexität. Wenn die ursprüngliche Zuordnung HashMap ist, müssen Sie mit beiden Methoden eine neue Map erstellen. Wenn Wenn die ursprüngliche Karte LinkedHashMap ist, müssen Sie nur beim ersten Ansatz ein neues Map erstellen. Sie können das LinkedHashMap mit dem zweiten Ansatz wiederverwenden.
  3. zeitliche Komplexität. Sie sollten beide O (nln (n)) haben.
1
xingbin 19 Jän. 2019 im 04:21