Ich bin auf der Suche nach einer Java-Klasse mit den Eigenschaften von C ++ std :: map üblichen Implementierung (wie ich es verstehe, eine selbstbalancierende binäre Suchbaum):
Ich suche nach Implementierungen mit Open-Source- oder Design-Dokumenten; Ich werde wahrscheinlich meine eigene Unterstützung für primitive Schlüssel / Werte rollen.
Der Stil dieser Frage ähnelt: Java entspricht std :: deque , dessen Antwort war "ArrayDeque from Primitive Collections for Java".
ConcurrentSkipListMap ist eine sortierte Map, die mit einem Skip-Befehl versehen ist Liste (eine selbstbalancierende baumartige Struktur mit O (log n) -Leistung). Im Allgemeinen sind die Grenzen auf CSLM enger als TreeMap (das ist ein sich selbst ausbalancierender Rot-Schwarz-Baumimpl), so dass es wahrscheinlich bessere Ergebnisse liefert, mit dem Nebenvorteil, threadsicher und gleichzeitig zu sein, was TreeMap nicht ist. CSLM wurde in JDK 1.6 hinzugefügt.
Fund enthält eine Reihe von Sammlungen für primitive Typen und einige andere interessante Varianten der gängigen Java-Collection-Typen.
Zu den weiteren interessanten Sammlungsbibliotheken gehören die Google Collection-Bibliothek und Apache Commons Sammlungen .
Die am nächsten zu einer Binärstruktur in den Java-Standardbibliotheken stehende Klasse ist java.util.TreeMap, unterstützt jedoch keine primitiven Typen, außer durch Boxen (dh int wird als Integer, Double als Double usw. umschlossen).
java.util.HashMap bietet wahrscheinlich eine bessere Leistung für große Karten. Theoretisch ist es O (1), aber seine genauen Leistungsmerkmale hängen von dem (den) Algorithmus (en) für die Erzeugung des Hash-Codes für die Schlüsselklasse (n) ab.
Laut Einführung in Sammlungen : "Arrays ... sind die einzige Sammlung, die unterstützt wird primitive Datentypen speichern. "
Sie können sich commons-collections ansehen FastTreeMap auch.
Ich bezweifle, dass Sie viele Sammlungen finden werden, die primitive Typen ohne Boxen unterstützen, also leben Sie einfach damit. Und das ist nicht unbedingt notwendig, wegen Autoboxing .
> Wenn Sie wirklich primitive Elemente verwenden möchten (nachdem Sie Benchmarks erstellt haben, die eine unzureichende Performance aufweisen!), können Sie die Quelle von FastTreeMap sehen und Methoden zum Bearbeiten von Primitiven hinzufügen.
Tags und Links java collections binary-tree stdmap