Ist ein Java hashmap wirklich O (1)?

https://stackoverflow.com/questions/1055243

20-08-2019
|

Frage

Ich habe auf SO wieder Java Hashmaps und ihre O(1) Lookup-Zeit einige interessante Ansprüche gesehen. Kann mir jemand erklären, warum das so ist? Es sei denn, diese Hashmaps ganz anders als eine der Hash-Algorithmen sind war ich aufgekauft, muss es existieren immer eine Datenmenge, die Kollisionen enthält.

In diesem Fall würde die Suche eher O(n) wird als O(1).

Kann mir jemand erklären, ob sie sind O (1), und wenn ja, wie sie dies erreichen?

Lösung

Ein besonderes Merkmal eines HashMap ist, dass im Gegensatz zu, sagen wir, ausgeglichene Bäume, sein Verhalten probabilistischen ist. In diesen Fällen seine in der Regel sehr hilfreich um die Komplexität in Bezug auf die Wahrscheinlichkeit eines Worst-Case-Fall zu sprechen wäre auftritt. Für eine Hash-Karte, das ist natürlich der Fall einer Kollision mit Bezug auf, wie voll die Karte sein geschieht. Eine Kollision ist recht einfach zu schätzen.

p _Kollisions = n / Kapazität

So eine Hash-Karte sogar mit einer bescheidenen Anzahl von Elementen ist ziemlich wahrscheinlich, zumindest eine Kollision zu erleben. O-Notation erlaubt es uns, etwas mehr zwingend zu tun. Beachten Sie, dass für jeden beliebigen, festen Konstante k.

O (n) = O (k * n)

Wir können diese Funktion verwenden, um die Leistung der Hash-Karte zu verbessern. Wir könnten stattdessen denken über die Wahrscheinlichkeit von höchstens 2 Kollisionen.

p _{Kollision x 2} = (n / Kapazität) ²

Das ist viel niedriger. Da die Kosten eine zusätzliche Kollision des Umgangs mit Big O-Leistung irrelevant sind, haben wir einen Weg, um die Leistung zu verbessern, ohne tatsächlich die Änderung den Algorithmus gefunden! Wir können diese generalzie zu

p _{Kollisions x k} = (n / Kapazität) ^K

Und jetzt können wir einige beliebige Anzahl von Kollisionen außer Acht lassen und mit verschwindend kleiner Wahrscheinlichkeit von mehr Kollisionen am Ende, als wir sind die Buchführung. Sie könnten die Wahrscheinlichkeit auf ein beliebig kleines Niveau erhalten, indem die richtigen k Wahl, die alle ohne die tatsächliche Implementierung des Algorithmus zu verändern.

Wir sprechen diese über, indem er sagte, dass die Hash-Karte O (1) Zugang mit hohen Wahrscheinlichkeit

hat

Andere Tipps

Sie scheinen auf Worst-Case-Verhalten mit durchschnittlichem Fall (erwarteter) Laufzeit zu mischen. Ersteres ist in der Tat O (n) für Hash-Tabellen im Allgemeinen (das heißt kein perfektes Hashing verwendet wird), aber das ist selten in der Praxis relevant.

Jede zuverlässige Hashtabelle Umsetzung, verbunden mit einer halbwegs Hash, hat eine Wiedergewinnungsleistung von O (1) mit einem sehr kleinen Faktor (2, in der Tat) im erwarteten Fall innerhalb eines sehr schmalen Randes der Varianz.

In Java arbeitet HashMap von hashCode mit einem Eimer zu lokalisieren. Jeder Eimer ist eine Liste der Elemente in diesem Eimer befinden. Die Elemente werden gescannt, equals zum Vergleich verwendet wird. Wenn Elemente hinzufügt, wird die HashMap der Größe verändert, wenn eine bestimmte Last Prozentsatz erreicht ist.

Also, manchmal wird es hat gegen ein paar Dinge zu vergleichen, aber es ist in der Regel sehr viel näher an O (1) als O (n). Aus praktischen Gründen ist das alles, was Sie benötigen, sollten wissen.

Beachten Sie, dass o (1) bedeutet nicht, dass jeder Lookup nur ein einzelnes Element untersucht - es bedeutet, dass die durchschnittliche Anzahl der Elemente bleibt geprüft konstant w.r.t. die Anzahl der Elemente in dem Behälter. Also, wenn es im Durchschnitt vier Vergleiche nimmt ein Element in einem Behälter mit 100 Gegenständen zu finden, sollte es auch einen Durchschnitt von 4 Vergleichen nimmt ein Element in einem Behälter mit 10.000 Artikeln und für jede andere Anzahl von Elementen (es gibt immer eine finden wenig Varianz, besonders um die Punkte, an denen die Hash-Tabelle Aufgüsse, und wenn es eine sehr kleine Anzahl von Elementen).

So Kollisionen nicht verhindern, dass der Behälter aus mit o (1) Operationen, solange die durchschnittliche Anzahl von Schlüsseln pro Eimer bleibt innerhalb eines gebundenen fixiert.

Ich weiß, das ist eine alte Frage, aber es ist eigentlich eine neue Antwort darauf.

Sie haben Recht, dass eine Hash-Karte nicht wirklich O(1) ist, streng genommen, weil die Anzahl der Elemente beliebig groß wird, irgendwann werden Sie nicht in der Lage sein, in konstanter Zeit zu suchen (und O-Notation wird in Begriffen definiert von Zahlen, die beliebig groß werden) können.

Aber es folgt nicht, dass die Echtzeit-Komplexität O(n) ist - weil es keine Regel gibt, die besagt, dass die Eimer als eine lineare Liste implementiert werden müssen.

In der Tat, Java 8 implementiert die Eimer als TreeMaps, sobald sie einen Schwellenwert überschreiten, die die aktuelle Zeit O(log n) macht.

Wenn die Anzahl der Schaufeln (nennen wir es b) konstant gehalten wird (der übliche Fall ist), dann Nachschlag ist eigentlich O (n).
als n groß wird, die Anzahl der Elemente in jedem Eimer Mittelwert n / b. Wenn Kollisionsauflösung in einem der üblichen Wege (verkettete Liste zum Beispiel) durchgeführt wird, dann Lookup ist O (n / b) = O (n).

Die O-Notation ist über das, was passiert, wenn n größer und größer wird. Es kann irreführend sein, wenn sie bestimmte Algorithmen angewandt, und Hash-Tabellen sind ein typischer Fall. Wir wählen die Anzahl der Schaufeln auf, wie viele Elemente wir erwarten, zu beschäftigen. Wenn n etwa die gleiche Größe wie b ist, dann ist Lookup etwa konstant Zeit, aber wir können es nicht nennen O (1), weil O in Form einer Grenze als n → ∞ definiert ist.

O(1+n/k) wo k die Anzahl der Eimer ist.

Wenn Implementierung setzt k = n/alpha dann ist es O(1+alpha) = O(1) seit alpha eine Konstante ist.

Wir haben festgestellt, dass die Standardbeschreibung von Hash-Tabelle Lookups für O (1) bezieht sich auf die durchschnittlichen Fall erwarteten Zeit, nicht die strengen Worst-Case-Leistung. Für eine Hash-Tabelle Kollisionen mit Chaining Lösung (wie Java hashmap) ist dies technisch O (1 + α) mit eine gute Hash-Funktion , wobei α die Ladefaktor der Tabelle ist. solange die Anzahl von Objekten Sie speichern nicht mehr ist als ein konstanter Faktor größer als die Tabellengröße nach wie vor konstant.

Es wird auch erläutert, dass es möglich ist streng gesprochen Eingang zu konstruieren, die O erfordert ( n ) Lookups für jede deterministische Hash-Funktion. Aber es ist auch interessant, den schlimmsten Fall zu betrachten erwartet Zeit, die als durchschnittliche Suchzeit unterschiedlich ist. Verwendung von Verkettungs dies O (1 + die Länge der längsten Kette), beispielsweise Θ (log n / log log n ), wenn α = 1 ist.

Wenn Sie in theoretischen Möglichkeiten interessiert sind konstante Zeit erwartet Worst-Case-Lookups zu erreichen, Sie lesen dynamischer perfekter Hashing die Kollisionen rekursiv mit einer anderen Hash-Tabelle löst!

Es ist O (1) nur dann, wenn Ihre Hash-Funktion ist sehr gut. Die Java-Hash-Tabelle Implementierung schützt nicht vor schlechten Hash-Funktionen.

Ob Sie die Tabelle wachsen, wenn Sie Elemente hinzufügen oder nicht, ist die Frage nicht relevant, da es über Lookup-Zeit ist.

Elemente innerhalb des HashMap sind als eine Anordnung von verketteten Liste gespeichert (Knoten), wobei jede verkettete Liste in der Anordnung stellt einen Eimer für eindeutigen Hash-Wert von einer oder mehreren Tasten.
Während ein Eintrag in der HashMap Zugabe wird der Hash-Code des Schlüssels verwendet, um die Position der Schaufel in der Anordnung, so etwas wie zu bestimmen:

location = (arraylength - 1) & keyhashcode

Hier ist die & repräsentiert bitweise AND-Operator.

Zum Beispiel: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Während der get-Operation verwendet er dieselbe Art und Weise die Lage der Eimer für den Schlüssel zu bestimmen. Unter dem besten Fall hat jeder Schlüssel eindeutig hashcode und die Ergebnisse in einer einzigartigen Eimer für jeden Schlüssel in diesem Fall die get-Methode nur verbringt viel Zeit den Eimer Lage und das Abrufen der Wert, der konstant O ist, um zu bestimmen (1).

Unter dem schlimmsten Fall alle Schlüssel haben denselben Hash-Code und in gleichen Eimer gespeichert, führt dies durch die gesamte Liste in durchqueren, die zu O führt (n).

Im Falle von Java-8, die verlinkte Liste Eimer mit einem TreeMap ersetzt wird, wenn die Größe auf mehr als 8 wächst, verringert dies die Worst-Case-Sucheffizienz zu O (log n).

Dies gilt grundsätzlich für die meisten Hash-Tabelle Implementierungen in den meisten Programmiersprachen, wie der Algorithmus selbst nicht wirklich ändern.

Wenn es keine Kollisionen in der Tabelle vorhanden, Sie nur eine einzige Nachschau zu tun haben, also die Laufzeit O (1). Wenn es Kollisionen vorhanden ist, haben Sie mehr als eine Nachschau zu tun, der die Performance gegenüber O fährt nach unten (n).

Es hängt von dem Algorithmus Sie wählen, um Kollisionen zu vermeiden. Wenn Ihre Implementierung getrennte Verkettung verwendet dann geschieht das Worst-Case-Szenario, in dem jedes Datenelement auf den gleichen Wert (schlechte Wahl der Hash-Funktion zum Beispiel) gehasht wird. In diesem Fall ist die Daten lookup nicht von einer linearen Suche auf einer verknüpften Liste d O (n). Allerdings ist die Wahrscheinlichkeit, dass das passiert vernachlässigbar und Lookups beste und mittlere Fälle konstant bleiben heißt O (1).

Lehre zur Seite, aus praktischer Sicht, HashMaps als mit einer belanglosen Auswirkungen auf die Leistung angenommen werden sollte (es sei denn, Ihr Profiler sagt Ihnen etwas anderes.)

Nur in theoretischen Fall, wenn Hashcodes sind immer anders und Eimer für jeden Hash-Code auch unterschiedlich ist, wird die O (1) vorhanden sind. Ansonsten ist es konstanter Ordnung heißt auf Zuwachs von hashmap, dessen Reihenfolge der Such konstant bleibt.

Natürlich ist die Leistung des hashmap wird auf die Qualität der hashCode () Funktion für das jeweilige Objekt depend basiert. Wenn jedoch die Funktion so ausgeführt wird, dass die Möglichkeit von Kollisionen sehr gering ist, wird es eine sehr gute Leistung hat (dies ist nicht streng O (1) in alle möglicher Fall, aber es ist in most Fälle).

die Standardimplementierung in der Oracle JRE Zum Beispiel ist eine Zufallszahl zu verwenden (die in der Objektinstanz gespeichert wird, so dass sie sich nicht ändert - aber es sperrt auch voreingenommen sichernd, aber das ist eine andere Diskussion) so die Chance, von Kollisionen sehr gering ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow