HashMap Komplexität erhalten / setzen

Wir sind es gewohnt zu sagen, dass HashMap get/putOperationen O (1) sind. Dies hängt jedoch von der Hash-Implementierung ab. Der Standardobjekt-Hash ist tatsächlich die interne Adresse im JVM-Heap. Sind wir sicher, dass es gut genug ist zu behaupten, dass get/putes sich um O (1) handelt?

Der verfügbare Speicher ist ein weiteres Problem. Wie ich aus den Javadocs verstehe, HashMap load factorsollte der Wert 0,75 sein. Was ist, wenn wir nicht genügend Speicher in JVM haben und load factordas Limit überschreitet?

Es sieht also so aus, als ob O (1) nicht garantiert ist. 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 eine konstante Zeit ist ... aber Sie könnten einen Hash haben, dessen Berechnung lange dauert, und wenn die Hash-Map mehrere Elemente enthält, die denselben Hash-Code zurückgeben, getmuss über sie iterieren und equalsjeden von ihnen anrufen , um eine Übereinstimmung zu finden.

Im schlimmsten Fall HashMaphat a eine O (n) -Suche, da alle Einträge im selben Hash-Bucket durchlaufen werden (z. B. wenn alle denselben Hash-Code haben). Glücklicherweise kommt dieses Worst-Case-Szenario meiner Erfahrung nach im wirklichen Leben nicht sehr oft vor. Nein, O (1) ist sicherlich nicht garantiert - aber normalerweise sollten Sie davon ausgehen, welche Algorithmen und Datenstrukturen verwendet werden sollen.

In JDK 8 HashMapwurde optimiert, dass, wenn Schlüssel für die Bestellung verglichen werden können, jeder dicht bestückte Bucket als Baum implementiert wird, sodass die Komplexität O (log) ist, selbst wenn viele Einträge mit demselben Hashcode vorhanden sind n). Dies kann zu Problemen führen, wenn Sie einen Schlüsseltyp haben, bei dem Gleichheit und Reihenfolge natürlich unterschiedlich sind.

Und ja, wenn Sie nicht genug Speicher für die Hash-Map haben, werden Sie in Schwierigkeiten geraten ... aber das gilt unabhängig von der verwendeten Datenstruktur.

Ich bin mir nicht sicher, ob der Standard-Hashcode die Adresse ist. Ich habe vor einiger Zeit die OpenJDK-Quelle für die Hashcode-Generierung gelesen und erinnere mich, dass dies etwas komplizierter war. Vielleicht immer noch nichts, was eine gute Verteilung garantiert. Dies ist jedoch bis zu einem gewissen Grad umstritten, da nur wenige Klassen, die Sie als Schlüssel in einer Hashmap verwenden würden, den Standard-Hashcode verwenden - sie liefern ihre eigenen Implementierungen, was gut sein sollte.

Darüber hinaus wissen Sie möglicherweise nicht (dies basiert wiederum auf der Lesequelle - es ist nicht garantiert), dass HashMap den Hash vor der Verwendung umrührt, um Entropie aus dem gesamten Wort in die unteren Bits zu mischen, wo es sich befindet benötigt für alle außer den größten Hashmaps. Das hilft beim Umgang mit Hashes, die das speziell nicht selbst tun, obwohl ich mir keine häufigen Fälle vorstellen kann, in denen Sie das sehen würden.

Wenn die Tabelle überlastet ist, degeneriert sie schließlich zu einer Reihe parallel verknüpfter Listen - die Leistung wird zu O (n). Insbesondere beträgt die Anzahl der durchquerten Verbindungen im Durchschnitt die Hälfte des Auslastungsfaktors.

Die HashMap-Operation ist ein abhängiger Faktor der HashCode-Implementierung. Für das ideale Szenario sagen wir, die gute Hash-Implementierung, die für jedes Objekt einen eindeutigen Hash-Code bereitstellt (keine Hash-Kollision), dann wäre das beste, schlechteste und durchschnittliche Szenario O (1). Betrachten wir ein Szenario, in dem eine fehlerhafte Implementierung von hashCode immer 1 oder einen solchen Hash zurückgibt, der eine Hash-Kollision aufweist. In diesem Fall wäre die zeitliche Komplexität O (n).

Kommen wir nun zum zweiten Teil der Frage zum Speicher, dann würde sich JVM um die Speicherbeschränkung kümmern.

Es wurde bereits erwähnt, dass Hashmaps O(n/m)im Durchschnitt sind, wenn nes sich um die Anzahl der Elemente und mdie Größe handelt. Es wurde auch erwähnt, dass das Ganze im Prinzip zu einer einfach verknüpften Liste mit O(n)Abfragezeit zusammenfallen könnte. (Dies alles setzt voraus, dass die Berechnung des Hashs eine konstante Zeit ist).

Was jedoch nicht oft erwähnt wird, ist, dass mit einer Wahrscheinlichkeit von mindestens 1-1/n(für 1000 Artikel ist dies eine 99,9% ige Chance) der größte Eimer nicht mehr gefüllt wird als O(logn)! Dies entspricht der durchschnittlichen 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 erforderlich ist, 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 für Hash gibt, nicht, wie Sie Ihre zufälligen Konstanten ausgewählt haben.

TL; DR: Mit sehr hoher Wahrscheinlichkeit ist die Worst-Case-Get / Put-Komplexität einer Hashmap der schlechteste O(logn).

Ich bin einverstanden mit:

• die allgemein amortisierte Komplexität von O (1)
• Eine schlechte hashCode()Implementierung kann zu mehreren Kollisionen führen, was bedeutet, dass im schlimmsten Fall jedes Objekt in denselben Bucket geht, also O ( N ), wenn jeder Bucket durch a gesichert ist List.
• HashMapErsetzt seit Java 8 dynamisch die in jedem Bucket verwendeten Knoten (verknüpfte Liste) durch TreeNodes (rot-schwarzer Baum, wenn eine Liste größer als 8 Elemente wird), was zu einer schlechtesten Leistung von O ( logN ) führt.

Aber dies ist NICHT die volle Wahrheit, wenn wir 100% genau sein wollen. Die Implementierung hashCode()und die Art des Schlüssels Object(unveränderlich / zwischengespeichert oder als Sammlung) können sich auch streng auf die tatsächliche Komplexität auswirken.

Nehmen wir die folgenden drei Fälle an:

1. HashMap<Integer, V>
2. HashMap<String, V>
3. HashMap<List<E>, V>

Haben sie die gleiche Komplexität? Nun, die amortisierte Komplexität der ersten ist erwartungsgemäß O (1). Im Übrigen müssen wir aber auch hashCode()das Lookup-Element berechnen , was bedeutet, dass wir möglicherweise Arrays und Listen in unserem Algorithmus durchlaufen müssen.

Nehmen wir an, dass die Größe aller oben genannten Arrays / Listen k ist . Dann HashMap<String, V>und HashMap<List<E>, V>wird O (k) Komplexität amortisiert und in ähnlicher Weise O ( k + logN ) Worst Case in Java8.

* Beachten Sie, dass die Verwendung eines StringSchlüssels ein komplexerer Fall ist, da er unveränderlich ist und Java das Ergebnis hashCode()in einer privaten Variablen zwischenspeichert hash, sodass es nur einmal berechnet wird.

/** Cache the hash code for the string */
    private int hash; // Default to 0

Das oben Genannte hat jedoch auch seinen eigenen schlimmsten Fall, da die String.hashCode()Implementierung von Java hash == 0vor dem Rechnen prüft, ob hashCode. Aber hey, es gibt nicht leere Strings, die eine hashcodeNull ausgeben , wie z. B. "f5a5a608", siehe hier . In diesem Fall ist das Auswendiglernen möglicherweise nicht hilfreich.

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

Wenn man sagt, dass Hashmap get / put O (1) ist, sollte man wirklich sagen, dass die für get / put benötigte Zeit mehr oder weniger konstant ist und nicht von der Anzahl der Elemente in der Hashmap abhängt, soweit die Hashmap möglich ist auf dem eigentlichen Computersystem vorgestellt. 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 unterschiedlichen Elemente ausgehen. Wenn wir beispielsweise eine Hashmap zum Speichern von 32-Bit-Zahlen verwendet haben und später die Problemgröße erhöhen, sodass die Hashmap mehr als 2 ^ 32-Bit-Elemente enthält, werden die einzelnen Elemente mit mehr als 32 Bit beschrieben.

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

Wenn Sie es mit einer Baummenge vergleichen, die O (log n) ist, dann ist die Hashmenge O (lang (max (n)) und wir glauben 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 zur Berechnung des Hash-Codes ist schnell.

Wenn schließlich das Finden eines Elements in einer Datenstruktur O (1) wäre, würden wir Informationen aus dem Nichts erstellen. Mit einer Datenstruktur von n Elementen kann ich ein Element auf n verschiedene Arten auswählen. Damit kann ich log (n) Bit-Informationen codieren. Wenn ich das in Nullbit codieren kann (das bedeutet O (1)), habe ich einen unendlich komprimierenden ZIP-Algorithmus erstellt.