wake-up-neo.com

HashMap holt / holt Komplexität

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

Der verfügbare Speicher ist ein weiteres Problem. Wie ich aus den Javadocs verstehe, sollte HashMapload factor 0,75 sein. Was ist, wenn in JVM nicht genügend Speicher vorhanden ist und load factor Das Limit überschreitet?

Es sieht also so aus, als ob O(1) nicht garantiert ist. Ergibt es einen Sinn oder fehle ich etwas?

112
Michael

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, nd, falls vorhanden Befinden sich mehrere Elemente in der Hash-Map, die denselben Hash-Code zurückgeben, muss get über sie iterieren und equals auf jedem von ihnen aufrufen, um eine Übereinstimmung zu finden.

Im schlimmsten Fall hat ein HashMap eine O(n) Lookup-Funktion, da alle Einträge im selben Hash-Bucket durchlaufen werden (z. B. wenn alle denselben Hash-Code haben). Glücklicherweise taucht dieses Worst-Case-Szenario meiner Erfahrung nach im wirklichen Leben nicht sehr häufig auf. Also nein, O(1) sicherlich nicht garantiert - aber es ist normalerweise das, was Sie sollten nehmen Sie an, wenn Sie überlegen, welche Algorithmen und Datenstrukturen verwendet werden sollen.

In JDK 8 wurde HashMap so angepasst, dass, wenn Schlüssel für die Bestellung verglichen werden können, jeder dicht bevölkerte Bucket als Baum implementiert wird, sodass selbst bei vielen Einträgen mit demselben Hash-Code Die Komplexität ist O (log n). Das 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 wird zutreffen, egal welche Datenstruktur Sie verwenden.

194
Jon Skeet

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 es etwas komplizierter war. Vielleicht immer noch nicht etwas, das eine gute Verteilung garantiert. Dies ist jedoch 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 stellen ihre eigenen Implementierungen bereit, die gut sein sollten.

Darüber hinaus wissen Sie möglicherweise nicht, dass HashMap den Hash vor der Verwendung aufrührt, um Entropie aus dem gesamten Wort in die untersten Bits zu mischen benötigt für alle außer den gewaltigsten Hashmaps. Das hilft, mit Hashes umzugehen, die das nicht selbst tun, obwohl mir keine gängigen Fälle einfallen, in denen Sie das sehen würden.

Wenn die Tabelle überladen ist, degeneriert sie schließlich in eine Reihe paralleler verknüpfter Listen - die Leistung wird zu O (n). Insbesondere wird die Anzahl der durchquerten Verbindungen im Durchschnitt die Hälfte des Lastfaktors betragen.

9
Tom Anderson

Es wurde bereits erwähnt, dass Hashmaps im Durchschnitt O(n/m) sind, wenn n die Anzahl der Elemente und m die Größe ist. Es wurde auch erwähnt, dass das Ganze im Prinzip zu einer einfach verknüpften Liste mit der Abfragezeit O(n) zusammenfallen kann. (Dies alles setzt voraus, dass die Berechnung des Hash konstant ist).

Was jedoch nicht oft erwähnt wird, ist, dass mit einer Wahrscheinlichkeit von mindestens 1-1/n (Also bei 1000 Artikeln mit einer Wahrscheinlichkeit von 99,9%) der größte Eimer nicht mehr als O(logn) gefüllt wird! Entspricht daher der durchschnittlichen Komplexität von binären Suchbäumen. (Und die Konstante ist gut, eine engere Grenze ist (log n)*(m/n) + O(1)).

Für diese theoretische Schranke ist nur die Verwendung einer einigermaßen guten Hash-Funktion erforderlich (siehe Wikipedia: niversal Hashing . Sie 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: Bei sehr hoher Wahrscheinlichkeit ist O(logn) der schlimmste Fall, in dem die Komplexität einer Hashmap abgerufen/abgelegt wird.

8
Thomas Ahle

Die HashMap-Operation ist abhängig vom Faktor der HashCode-Implementierung. Nehmen wir für das ideale Szenario die gute Hash-Implementierung an, die eindeutigen Hash-Code für jedes Objekt 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 zurückgibt, oder einen solchen Hash, der eine Hash-Kollision aufweist. In diesem Fall wäre die Zeitkomplexität O (n).

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

7
Pranav

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 den gleichen Bucket gelangt, also O [~ # ~] n [ ~ # ~] ), wenn jeder Bucket mit einem List hinterlegt ist.
  • since Java 8 HashMap ersetzt dynamisch die in jedem Bucket verwendeten Nodes (verknüpfte Liste) durch TreeNodes (rot-schwarzer Baum, wenn eine Liste größer als 8 Elemente wird), was zu einem Worst führt Leistung von O ( logN ).

Aber dies ist NICHT die volle Wahrheit, wenn wir 100% genau sein wollen. Die Implementierung von hashCode(), die Art des Schlüssels Object (unveränderlich/zwischengespeichert oder eine Auflistung) kann sich auch streng genommen 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() des Lookup-Elements berechnen, was bedeutet, dass wir möglicherweise Arrays und Listen in unserem Algorithmus durchlaufen müssen.

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

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

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

Das obige hat aber auch seinen eigenen schlimmsten Fall, da die Implementierung von Java String.hashCode() prüft, ob hash == 0, Bevor hashCode berechnet wird. Aber hey, es gibt nicht leere Strings, die ein hashcode von Null ausgeben, wie z. B. "f5a5a608", siehe hier . In diesem Fall ist das Merken möglicherweise nicht hilfreich.

3
Kostas Chalkias

In der Praxis ist es O (1), aber dies ist tatsächlich eine schreckliche und mathematisch unsinnige Vereinfachung. Die O() Notation sagt aus, wie sich der Algorithmus verhält, wenn die Größe des Problems gegen unendlich geht. Hashmap get/put funktioniert wie ein O(1) Algorithmus Für eine begrenzte Größe: Die Begrenzung ist aus Sicht des Computerspeichers und der Adressierung ziemlich groß, aber bei weitem nicht unendlich.

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 abhängt die Hashmap, sofern die Hashmap auf dem tatsächlichen Computersystem dargestellt werden kann.Wenn das Problem diese Größe überschreitet und wir größere Hashmaps benötigen, wird die Anzahl der Bits, die ein Element beschreiben, mit der Zeit mit Sicherheit ebenfalls zunehmen 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 beschrieben mehr als 32 Bit.

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(long(max(n)) und wir glauben einfach, dass dies O (1) ist, da bei einer bestimmten Implementierung max (n) fest ist, ändert sich nichts (die Größe der von uns gespeicherten Objekte wird in Bits gemessen) und der Algorithmus zur Berechnung des Hash-Codes ist schnell.

Wenn ein Element in einer Datenstruktur gefunden würde, würden wir O(1) Informationen aus Luft erzeugen. Mit einer Datenstruktur von n Element kann ich ein Element auf n verschiedene Arten auswählen. Damit kann ich Log (n) -Bit-Informationen kodieren. Wenn ich das mit Null-Bit kodieren kann (das bedeutet O(1))), dann habe ich einen unendlich komprimierenden Zip-Algorithmus erstellt.

2
Peter Verhas