Was sind die Unterschiede zwischen den verschiedenen Map-Implementierungen in Dart?

Question

Dart hat einen Map-Typ mit Implementierungen wie HashMap, LinkedHashMap und SplayTreeMap. Was ist der Unterschied zwischen diesen verschiedenen Map-Implementierungen?

Answer 1

Dart hat integrierte Unterstützung für Sammlungen wie Liste, Satz und Karte. Dart verfügt über verschiedene Map-Implementierungen. Wenn Sie die Vor- und Nachteile von Implementierungen verstehen, können Sie eine fundierte Entscheidung treffen.

. (Anmerkung: das um die Zeit der Dart M3 geschrieben ist, so folgt, was man nicht die Dokumentation in diesem Moment entspricht)

Was ist eine Karte?

Eine Map ist ein assoziativer Container, der den Schlüsseln Werte zuordnet. Schlüssel sind eindeutig und können auf einen einzigen Wert verweisen. Ein Schlüssel darf nicht null sein, aber ein Wert kann null sein.

Karte Literale

Dart unterstützt Karte Literale, wie folgt aus:

var accounts = {'323525': 'John Smith', '588982': 'Alice Jones'}; 

Die Spezifikation sagt, dass Karte Literale Auftrag pflegen müssen. Dies bedeutet, dass accounts eine Instanz von ist.

Die Spezifikation besagt auch, dass Map-Literalschlüssel Strings sein müssen. Dies könnte sich in Zukunft ändern.

neue Karte()

Dart unterstützt Werksbauer, so dass Sie eine neue Instanz der Karte wie folgt erstellen:

var accounts = new Map(); 

Die Map Klasse ist abstrakt, die die Fabrik Konstruktor bedeutet eine tatsächlich schafft Instanz einer Unterklasse von Map. Was ist der tatsächliche Typ von accounts?

Frühere Versionen von Dart erstellten eine neue Instanz von HashMap aus dem new Map() Konstruktor. Dart bug 5803 besagt jedoch, dass {} und new Map denselben Typ zurückgeben, new Map bald eine Instanz.zurückgeben wird.

LinkedHashMap (oder InsertionOrderedMap)

A LinkedHashMap iteriert durch Schlüssel und Werte in der gleichen Reihenfolge, wie sie eingesetzt wurden.

Hinweis: LinkedHashMap wird wahrscheinlich in InsertionOrderedMap umbenannt. Folgen Sie für den Fortschritt. Hier

ein Beispiel:

import 'dart:collection'; 
main() { 
    var ordered = new LinkedHashMap(); 
    ordered['32352'] = 'Alice'; 
    ordered['95594'] = 'Bob'; 

    for (var key in ordered.keys) { 
    print(key); 
    } 

    // guaranteed to print 32352, then 95594 
} 

Hier ist die source code for LinkedHashMap. (Wenn dieser Link nicht mehr funktioniert, ist es wahrscheinlich, weil die Klasse umbenannt wurde)

HashMap

A HashMap hat keine Garantie für Auftrag erhalten.Wenn Sie die Schlüssel oder Werte einer HashMap durchlaufen, können Sie keine bestimmte Reihenfolge erwarten.

Eine HashMap wird mit einem hash table implementiert. Hier

ist ein Beispiel für eine neue HashMap zu schaffen:

import 'dart:collection'; 
main() { 
    var accounts = new HashMap(); 
} 

Wenn Sie nicht über die Aufrechterhaltung Auftrag ist es egal, verwenden HashMap.

Hier ist die source code of HashMap.

SplayTreeMap

Ein Spreizfuß Baum ist ein Balancierter Baum mit der zusätzlichen Eigenschaft, die vor kurzem zugegriffen Elemente wieder schnell zugänglich sind. Es führt grundlegende Operationen wie Einfügen, Nachschlagen und Entfernen in O (log (n)) amortisierten Zeit durch.

import 'dart:collection'; 
main() { 
    var accounts = new SplayTreeMap(); 
} 

Eine SplayTreeMap erfordert, dass alle Schlüssel vom selben Typ sind.

Ein Splay-Tree ist eine gute Wahl für Daten, die häufig gespeichert und abgerufen werden, wie Caches. Der Grund ist, dass sie Baumrotationen verwenden, um ein Element für bessere Zugriffe auf die Wurzel zu bringen. Die Leistung kommt von der Selbstoptimierung des Baumes. Das heißt, Elemente, auf die häufig zugegriffen wird, werden näher an den Anfang verschoben. Wenn jedoch der Baum überall gleich häufig aufgerufen wird, ist es wenig sinnvoll, eine Splay-Tree-Map zu verwenden.

Ein Beispielfall ist ein Modemrouter, der Netzwerkpakete mit sehr hohen Raten empfängt. Das Modem muss entscheiden, welches Paket in welcher Leitung geht. Es kann eine Map-Implementierung verwenden, bei der der Schlüssel die IP und der Wert das Ziel ist. Eine Splay-Tree-Map ist eine gute Wahl für dieses Szenario, da die meisten IP-Adressen mehr als einmal verwendet werden und diese daher im Stammverzeichnis der Baumstruktur gefunden werden können.