Das Laden von 1 000 000 Zahlen dauert 2 Sekunden, um in eine Treemap (binärer Suchbaum) geladen zu werden, benötigt aber Millisekunden, um in eine hashmap (in Java) geladen zu werden.
Der einzige Unterschied zwischen den beiden ist, dass ich sehen kann, ob ich die Anfangsgröße einer Hashmappe festlegen kann, damit sie nicht ständig neu skaliert werden muss.
Ist es falsch zu vermuten, dass die Anfangsgröße eines TreeMap-Arrays eingestellt werden kann? Gibt es einen anderen Grund, dass es so langsam ist? Gibt es einen logischen Grund dafür, warum man die Größe von TreeMaps oder generischen binären Suchbäumen nicht einstellen kann, oder ist das falsch?
Im Gegensatz zu HashMap , das seine Interna neu zuweist, wenn neue eingefügt werden, weist% ce_de% seine Knoten im Allgemeinen nicht neu zu, wenn neue hinzugefügt werden. Der Unterschied kann sehr locker dargestellt werden als der zwischen einem TreeMap und einem ArrayList : der erste wird zur Größenänderung neu zugeordnet, während der zweite nicht. Aus diesem Grund ist die anfängliche Größe von LinkedList ungefähr so bedeutungslos wie die anfängliche Größe von TreeMap .
Die Geschwindigkeitsdifferenz ist auf die unterschiedliche Zeitkomplexität der beiden Container zurückzuführen: Einfügen von LinkedList nodes in N ist HashMap , während für O(n) TreeMap ist, was für 1000000 Knoten grob ist 20-mal asymptotisch Unterschied. Obwohl der Unterschied in der asymptotischen Komplexität aufgrund unterschiedlicher, von den einzelnen Algorithmen vorgegebener Konstanten nicht direkt in die Zeitdifferenz übergeht, dient er als eine gute Möglichkeit, zu entscheiden, welcher Algorithmus bei sehr großen Eingaben schneller ist.
Ist es falsch zu vermuten, dass die Anfangsgröße eines TreeMap-Arrays eingestellt werden kann?
Ja. A TreeMap hat kein Array. A TreeMap verwendet binäre Knoten mit 2 Kindern.
Wenn Sie vorschlagen, dass die Anzahl der untergeordneten Elemente in einem Baumknoten ein Parameter sein soll, müssen Sie herausfinden, wie sich dies auf die Suchzeit auswirkt. Und ich denke, dass es die Suchzeit von O(log2N) nach O(log2M * log2(N/M)) dreht, wobei N die Anzahl der Elemente und M die durchschnittliche Anzahl der Knotenkinder ist. (Und ich mache einige optimistische Annahmen ...) Das ist kein "Gewinn".
Gibt es einen anderen Grund, dass es so langsam ist?
Ja. Der Grund dafür, dass eine (große) TreeMap relativ zu einer (großen) HashMap unter optimalen Umständen langsam ist, ist, dass für die Suche mit einer ausgeglichenen Binärstruktur log2N tree-Knoten betrachtet werden müssen. Im Gegensatz dazu beinhaltet eine Suche in einem optimalen HashMap (guter Ladefaktor und keine Kollisions-Hotspots) 1 Hashcode-Berechnung und betrachtet O(1) Hashchain-Knoten.
Anmerkungen:
TreeMap verwendet eine binäre Baumorganisation, die ausgeglichene Bäume ergibt, daher ist O(log2N) die schlechteste Nachschlagezeit. HashMap Leistung hängt von der Kollisionsrate der Hash-Funktion und des Schlüsselraums ab. Im schlimmsten Fall, wenn alle Schlüssel in derselben Hash-Kette enden, hat HashMap O(N) lookup. Eine Treemap ist immer ausgewogen. Jedes Mal, wenn Sie einen Knoten zum Baum hinzufügen, muss sichergestellt werden, dass alle Knoten vom angegebenen Vergleicher in der richtigen Reihenfolge sind. Sie haben keine bestimmte Größe, da die Treemap für eine reibungslos sortierte Gruppe von Knoten ausgelegt ist und die Knoten problemlos durchqueren kann.
Eine Hashmap muss über einen großen freien Speicherplatz für die darin gespeicherten Objekte verfügen. Mein Professor hat mir immer gesagt, dass es das 5-fache an Speicherplatz benötigt, den die Objekte oder was auch immer Sie darin speichern, hashmap. Wenn Sie also die Größe ab der ersten Erstellung der Hashmap angeben, wird die Geschwindigkeit Ihrer Hashmap verbessert. Andernfalls, wenn Sie mehr Objekte in eine Hashmap aufnehmen als geplant, muss die Hashmap "größer werden".
(für die Rechtschreibung bearbeitet)