values - java map hashmap




HashMap Get/Put Komplexität (4)

Wir sind es gewohnt zu sagen, dass HashMap get/put Operationen O (1) sind. Es hängt jedoch von der Hash-Implementierung ab. Der Standardobjekt-Hash ist eigentlich die interne Adresse im JVM-Heap. Sind wir sicher, dass es gut genug ist, um zu behaupten, dass das get/put O (1) ist?

Verfügbarer Speicher ist ein anderes Problem. Wie ich von den Javadocs verstehe, sollte der HashMap Ladefaktor 0,75 sein. Was ist, wenn wir in JVM nicht genügend Speicher haben und der Ladefaktor das Limit überschreitet?

Es sieht also so aus, als wäre O (1) nicht garantiert. Macht es Sinn oder fehlt mir etwas?


Es hängt von vielen Dingen ab. Es ist normalerweise O (1), mit einem anständigen Hash, der selbst konstante Zeit ist ... aber Sie könnten einen Hash haben, der eine lange Zeit für die Berechnung benötigt, und wenn es mehrere Elemente in der Hash-Map gibt, die denselben Hash-Code zurückgeben, get muss über sie iterieren, indem sie bei jedem von ihnen gleiches aufruft, um eine Übereinstimmung zu finden.

Im schlimmsten Fall hat eine HashMap einen O (n) Lookup, weil sie alle Einträge im selben Hash-Bucket durchlaufen hat (zB wenn sie alle denselben Hash-Code haben). Glücklicherweise kommt dieses Worst-Case-Szenario nach meiner Erfahrung im wirklichen Leben nicht oft vor. Also nein, O (1) ist sicherlich nicht garantiert - aber normalerweise sollten Sie davon ausgehen, welche Algorithmen und Datenstrukturen zu verwenden sind.

In JDK 8 wurde HashMap so optimiert, dass, wenn Schlüssel zum Sortieren verglichen werden können, jeder dicht bevölkerte Bucket als Baum implementiert wird, so dass selbst bei vielen Einträgen mit demselben Hash-Code die Komplexität O ( log n). Das kann zu Problemen führen, wenn Sie einen Schlüsseltyp haben, bei dem die Gleichheit und die Reihenfolge natürlich unterschiedlich sind.

Und ja, wenn Sie nicht genug Speicher für die Hash-Karte haben, werden Sie in Schwierigkeiten geraten ... aber das wird wahr sein, egal welche Datenstruktur Sie verwenden.


Es wurde bereits erwähnt, dass Hashmaps durchschnittlich O(n/m) , wenn n die Anzahl der Items und m die Größe ist. Es wurde auch erwähnt, dass im Prinzip das Ganze in eine einfach verkettete Liste mit O(n) Abfragezeit kollabieren könnte. (Dies alles setzt voraus, dass das Berechnen des Hashs eine konstante Zeit ist).

Allerdings wird nicht oft erwähnt, dass mit der Wahrscheinlichkeit von mindestens 1-1/n (also für 1000 Elemente, die eine 99,9% Chance ist) der größte Eimer nicht mehr als O(logn) gefüllt wird! Daher entspricht die durchschnittliche Komplexität von binären Suchbäumen. (Und die Konstante ist gut, eine engere Grenze ist (log n)*(m/n) + O(1) ).

Alles, was für diese theoretische Grenze benötigt wird, ist, dass Sie eine einigermaßen gute Hash-Funktion verwenden (siehe Wikipedia: Universal Hashing . Es kann so einfach sein wie a*x>>m ). Und natürlich weiß die Person, die Ihnen die Werte zum Hash gibt, nicht, wie Sie Ihre zufälligen Konstanten ausgewählt haben.

TL; DR: Mit sehr hoher Wahrscheinlichkeit ist die Worst Case-Komplexität einer Hashmappe O(logn) .


Ich bin mir nicht sicher, ob der Standard-Hashcode die Adresse ist - ich habe vor einer Weile die OpenJDK-Quelle für die Hashcode-Generierung gelesen, und ich erinnere mich, dass es etwas komplizierter war. Immer noch nicht etwas, das eine gute Verteilung garantiert. Dies ist jedoch in gewisser Hinsicht problematisch, da nur wenige Klassen, die Sie als Schlüssel in einer Hashmap verwenden, den Standard-Hashcode verwenden - sie liefern ihre eigenen Implementierungen, was gut sein sollte.

Obendrein wissen Sie vielleicht nicht, dass HashMap den Hash vor der Verwendung der Entropie aus dem ganzen Wort in die unteren Bits mischt, wo es ist benötigt für alle außer den größten hashmaps. Das hilft, mit Hashes fertig zu werden, die das selbst nicht tun, obwohl ich mir keine üblichen Fälle vorstellen kann, in denen Sie das sehen würden.

Was schließlich passiert, wenn die Tabelle überladen ist, ist, dass sie in eine Reihe von parallel verknüpften Listen degeneriert - Leistung wird zu O (n). Insbesondere wird die Anzahl der durchlaufenen Verbindungen im Durchschnitt die Hälfte des Ladefaktors betragen.


In der Praxis ist es O (1), aber das ist tatsächlich eine schreckliche und mathematisch sinnlose Vereinfachung. Die O () Notation sagt aus, wie sich der Algorithmus verhält, wenn die Größe des Problems zu unendlich neigt. Hashmap get / put funktioniert wie ein O (1) -Algorithmus für eine begrenzte Größe. Die Grenze ist ziemlich groß vom Computerspeicher und vom Standpunkt der Adressierung, aber weit von der Unendlichkeit entfernt.

Wenn man sagt, dass hashmap get / put ist O (1), sollte es wirklich sagen, dass die für das get / put benötigte Zeit mehr oder weniger konstant ist und nicht von der Anzahl der Elemente in der hashmap abhängt, so weit das hashmap kann auf dem tatsächlichen Computersystem dargestellt werden. Wenn das Problem über diese Größe hinausgeht und wir größere hashmaps benötigen, wird nach einer Weile sicherlich auch die Anzahl der Bits, die ein Element beschreiben, zunehmen, wenn uns die möglichen beschreibbaren verschiedenen Elemente ausgehen. Wenn wir beispielsweise eine Hashmap zum Speichern von 32-Bit-Nummern verwenden und später die Problemgröße erhöhen, so dass mehr als 2 ^ 32 Bit-Elemente in der Hash-Map vorhanden sind, werden die einzelnen Elemente mit mehr als 32 Bit beschrieben.

Die Anzahl der Bits, die benötigt werden, um die einzelnen Elemente zu beschreiben, ist log (N), wobei N die maximale Anzahl von Elementen ist, daher sind get und put wirklich O (log N).

Wenn Sie es mit einem Baumsatz vergleichen, der O (log n) ist, dann ist der Hash-Satz O (long (max (n)) und wir fühlen einfach, dass dies O (1) ist, weil bei einer bestimmten Implementierung max (n) ist fest, ändert sich nicht (die Größe der Objekte, die wir speichern, gemessen in Bits) und der Algorithmus, der den Hash-Code berechnet, ist schnell.

Wenn schließlich ein Element in einer Datenstruktur O (1) wäre, würden wir Informationen aus der Luft schaffen. Mit einer Datenstruktur von n Element I kann ein Element auf n verschiedene Weise ausgewählt werden. Damit kann ich Log (n) -Bit-Informationen codieren. Wenn ich das im Null-Bit kodieren kann (das ist, was O (1) bedeutet), dann habe ich einen unendlich komprimierenden ZIP-Algorithmus erstellt.





complexity-theory