Ist eine Java-Hashmap wirklich O (1)?

159

Ich habe einige interessante Behauptungen zu SO re Java-Hashmaps und deren Suchzeit gesehen O(1). Kann jemand erklären, warum das so ist? Sofern sich diese Hashmaps nicht wesentlich von den Hashing-Algorithmen unterscheiden, für die ich mich entschieden habe, muss immer ein Datensatz vorhanden sein, der Kollisionen enthält.

In diesem Fall wäre die Suche O(n)eher als O(1).

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

paxdiablo
quelle
1
Ich weiß, dass dies möglicherweise keine Antwort ist, aber ich erinnere mich, dass Wikipedia einen sehr guten Artikel darüber hat. Verpassen Sie nicht den Abschnitt zur Leistungsanalyse
Victor
28
Die Big O-Notation gibt eine Obergrenze für die bestimmte Art der Analyse an, die Sie durchführen. Sie sollten immer noch angeben, ob Sie an Worst-Case, Durchschnittsfall usw. interessiert sind
Dan Homerick

Antworten:

127

Ein besonderes Merkmal einer HashMap ist, dass ihr Verhalten im Gegensatz zu beispielsweise ausgeglichenen Bäumen wahrscheinlich ist. In diesen Fällen ist es normalerweise am hilfreichsten, über die Komplexität im Hinblick auf die Wahrscheinlichkeit des Eintretens eines Worst-Case-Ereignisses zu sprechen. Bei einer Hash-Karte ist dies natürlich der Fall bei einer Kollision in Bezug darauf, wie voll die Karte gerade ist. Eine Kollision ist ziemlich einfach abzuschätzen.

p Kollision = n / Kapazität

Bei einer Hash-Karte mit nur einer bescheidenen Anzahl von Elementen ist es daher ziemlich wahrscheinlich, dass mindestens eine Kollision auftritt. Mit der Big O-Notation können wir etwas überzeugenderes tun. Beachten Sie, dass für jede beliebige feste Konstante k gilt.

O (n) = O (k · n)

Mit dieser Funktion können wir die Leistung der Hash-Map verbessern. Wir könnten stattdessen über die Wahrscheinlichkeit von höchstens 2 Kollisionen nachdenken.

p Kollision x 2 = (n / Kapazität) 2

Das ist viel niedriger. Da die Kosten für die Behandlung einer zusätzlichen Kollision für die Leistung von Big O nicht relevant sind, haben wir einen Weg gefunden, die Leistung zu verbessern, ohne den Algorithmus tatsächlich zu ändern! Wir können dies verallgemeinern

p Kollision xk = (n / Kapazität) k

Und jetzt können wir eine beliebige Anzahl von Kollisionen ignorieren und am Ende eine verschwindend geringe Wahrscheinlichkeit für mehr Kollisionen haben, als wir berücksichtigen. Sie könnten die Wahrscheinlichkeit auf ein beliebig kleines Niveau bringen, indem Sie das richtige k auswählen, ohne die tatsächliche Implementierung des Algorithmus zu ändern.

Wir sprechen darüber, indem wir sagen, dass die Hash-Map mit hoher Wahrscheinlichkeit O (1) -Zugriff hat

SingleNegationElimination
quelle
Selbst mit HTML bin ich mit den Brüchen immer noch nicht wirklich zufrieden. Räumen Sie sie auf, wenn Sie sich eine gute Möglichkeit dafür vorstellen können.
SingleNegationElimination
4
Tatsächlich besagt das Obige, dass die O (log N) -Effekte für nicht extreme Werte von N durch den festen Overhead begraben werden.
Hot Licks
Technisch gesehen ist diese Zahl, die Sie angegeben haben, der erwartete Wert der Anzahl der Kollisionen, der der Wahrscheinlichkeit einer einzelnen Kollision entsprechen kann.
Simon Kuang
1
Ist dies ähnlich wie bei der amortisierten Analyse?
lostsoul29
1
@ OleV.V. Eine gute Leistung einer HashMap hängt immer von einer guten Verteilung Ihrer Hash-Funktion ab. Sie können eine bessere Hash-Qualität gegen Hashing-Geschwindigkeit eintauschen, indem Sie eine kryptografische Hashing-Funktion für Ihre Eingabe verwenden.
SingleNegationElimination
38

Sie scheinen das Worst-Case-Verhalten mit der durchschnittlichen (erwarteten) Laufzeit zu verwechseln. Ersteres ist zwar O (n) für Hash-Tabellen im Allgemeinen (dh es wird kein perfektes Hashing verwendet), dies ist jedoch in der Praxis selten relevant.

Jede zuverlässige Implementierung einer Hash-Tabelle in Verbindung mit einem halbwegs anständigen Hash hat eine Abrufleistung von O (1) mit einem sehr kleinen Faktor (tatsächlich 2) im erwarteten Fall innerhalb eines sehr engen Varianzspielraums.

Konrad Rudolph
quelle
6
Ich habe immer gedacht, dass die Obergrenze der schlimmste Fall ist, aber es scheint, dass ich mich geirrt habe - Sie können die Obergrenze für den Durchschnittsfall haben. Es scheint also, dass Leute, die O (1) beanspruchen, klargestellt haben sollten, dass dies ein durchschnittlicher Fall war. Der schlimmste Fall ist ein Datensatz, bei dem es viele Kollisionen gibt, die ihn zu O (n) machen. Das macht jetzt Sinn.
Paxdiablo
2
Sie sollten wahrscheinlich klarstellen, dass Sie bei Verwendung der Big-O-Notation für den Durchschnittsfall von einer Obergrenze für die erwartete Laufzeitfunktion sprechen, die eine klar definierte mathematische Funktion ist. Ansonsten macht Ihre Antwort nicht viel Sinn.
ldog
1
gmatt: Ich bin mir nicht sicher, ob ich Ihren Einwand verstehe: Die Big-O-Notation ist per Definition eine Obergrenze für die Funktion . Was könnte ich sonst noch bedeuten?
Konrad Rudolph
3
In der Computerliteratur wird normalerweise eine große O-Notation angezeigt, die eine Obergrenze für die Laufzeit- oder Raumkomplexitätsfunktionen eines Algorithmus darstellt. In diesem Fall entspricht die Obergrenze tatsächlich der Erwartung, die selbst keine Funktion, sondern ein Operator für Funktionen (Zufallsvariablen) und tatsächlich ein Integral (Lebesgue) ist. Die Tatsache, dass Sie so etwas binden können, sollte nicht berücksichtigt werden selbstverständlich und nicht trivial.
ldog
31

In Java verwendet HashMap Hashcode, um einen Bucket zu finden. Jeder Bucket ist eine Liste von Elementen, die sich in diesem Bucket befinden. Die Elemente werden gescannt und zum Vergleich gleich verwendet. Beim Hinzufügen von Elementen wird die Größe der HashMap geändert, sobald ein bestimmter Lastprozentsatz erreicht ist.

Manchmal muss es also mit einigen Elementen verglichen werden, aber im Allgemeinen ist es viel näher an O (1) als an O (n). Aus praktischen Gründen ist das alles, was Sie wissen müssen.

FogleBird
quelle
11
Nun, da big-O die Grenzen festlegen soll, spielt es keine Rolle, ob es näher an O (1) liegt oder nicht. Sogar O (n / 10 ^ 100) ist immer noch O (n). Ich verstehe, wie effizient es ist, das Verhältnis zu senken, aber das bringt den Algorithmus immer noch auf O (n).
Paxdiablo
4
Die Hash-Maps-Analyse erfolgt normalerweise im Durchschnitt, dh O (1) (mit Absprachen). Im schlimmsten Fall können Sie O (n) haben, dies ist jedoch normalerweise nicht der Fall. in Bezug auf den Unterschied - O (1) bedeutet, dass Sie unabhängig von der Anzahl der Elemente in der Tabelle dieselbe Zugriffszeit erhalten. Dies ist normalerweise der Fall (sofern ein gutes Verhältnis zwischen der Größe der Tabelle und 'n besteht) ')
Liran Orevi
4
Es ist auch erwähnenswert, dass es immer noch genau O (1) ist, auch wenn das Scannen des Eimers eine Weile dauert, da bereits einige Elemente darin enthalten sind. Solange die Eimer eine feste maximale Größe haben, ist dies nur ein konstanter Faktor, der für die O () - Klassifizierung irrelevant ist. Aber natürlich können noch mehr Elemente mit "ähnlichen" Schlüsseln hinzugefügt werden, so dass diese Eimer überlaufen und Sie keine Konstante mehr garantieren können.
etw
@sth Warum sollten die Eimer jemals eine feste maximale Größe haben?
Navin
31

Denken Sie daran, dass o (1) nicht bedeutet, dass bei jeder Suche nur ein einzelnes Element untersucht wird. Dies bedeutet, dass die durchschnittliche Anzahl der überprüften Elemente für die Anzahl der Elemente im Container konstant bleibt. Wenn also durchschnittlich 4 Vergleiche erforderlich sind, um einen Artikel in einem Container mit 100 Artikeln zu finden, sollten durchschnittlich 4 Vergleiche erforderlich sein, um einen Artikel in einem Container mit 10000 Artikeln zu finden, und für eine beliebige andere Anzahl von Artikeln (es gibt immer einen ein bisschen Varianz, insbesondere um die Punkte, an denen die Hash-Tabelle erneut aufbereitet wird, und wenn es eine sehr kleine Anzahl von Elementen gibt).

Kollisionen verhindern also nicht, dass der Container o (1) -Operationen ausführt, solange die durchschnittliche Anzahl von Schlüsseln pro Bucket innerhalb einer festen Grenze bleibt.

Daniel James
quelle
16

Ich weiß, dass dies eine alte Frage ist, aber es gibt tatsächlich eine neue Antwort darauf.

Sie haben Recht, dass eine Hash-Karte nicht wirklich ist O(1) streng genommen ist, denn da die Anzahl der Elemente beliebig groß wird, können Sie möglicherweise nicht in konstanter Zeit suchen (und die O-Notation wird in Zahlen definiert, die dies können willkürlich groß werden).

Daraus folgt jedoch nicht, dass die Echtzeitkomplexität ist O(n) da es keine Regel gibt, die besagt, dass die Buckets als lineare Liste implementiert werden müssen.

Tatsächlich implementiert Java 8 die Buckets, TreeMapssobald sie einen Schwellenwert überschreiten, der die tatsächliche Zeit angibt O(log n).

ajb
quelle
4

Wenn die Anzahl der Buckets (nennen Sie es b) konstant gehalten wird (der übliche Fall), ist die Suche tatsächlich O (n).
Wenn n groß wird, beträgt die Anzahl der Elemente in jedem Bucket durchschnittlich n / b. Wenn die Kollisionsauflösung auf eine der üblichen Arten erfolgt (z. B. verknüpfte Liste), lautet die Suche O (n / b) = O (n).

In der O-Notation geht es darum, was passiert, wenn n immer größer wird. Es kann irreführend sein, wenn es auf bestimmte Algorithmen angewendet wird, und Hash-Tabellen sind ein typisches Beispiel. Wir wählen die Anzahl der Eimer basierend auf der Anzahl der Elemente, mit denen wir uns befassen möchten. Wenn n ungefähr die gleiche Größe wie b hat, ist die Suche ungefähr zeitlich konstant, aber wir können es nicht O (1) nennen, da O als Grenze als n → ∞ definiert ist.

IJ Kennedy
quelle
4

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

Wenn Implementierung setzt k = n/alphadann ist es O(1+alpha) = O(1)da alphaeine Konstante ist.

Satyanarayana Kakollu
quelle
1
Was bedeutet das konstante Alpha ?
Prahalad Deshpande
2

Wir haben festgestellt, dass sich die Standardbeschreibung der Hash-Tabellensuche mit O (1) auf die erwartete Durchschnittszeit bezieht, nicht auf die strikte Leistung im ungünstigsten Fall. Für eine Hash-Tabelle, die Kollisionen mit Verkettung auflöst (wie Javas Hashmap), ist dies technisch gesehen O (1 + α) mit einer guten Hash-Funktion , wobei α der Lastfaktor der Tabelle ist. Immer noch konstant, solange die Anzahl der Objekte, die Sie speichern, nicht mehr als ein konstanter Faktor ist, der größer als die Tabellengröße ist.

Es wurde auch erklärt, dass es streng genommen möglich ist, Eingaben zu erstellen, die O ( n ) -Suchen für jede deterministische Hash-Funktion erfordern . Es ist aber auch interessant, die im schlimmsten Fall erwartete Zeit zu berücksichtigen , die sich von der durchschnittlichen Suchzeit unterscheidet. Bei Verwendung der Verkettung ist dies O (1 + die Länge der längsten Kette), zum Beispiel Θ (log n / log log n ), wenn α = 1 ist.

Wenn Sie an theoretischen Methoden interessiert sind, um Worst-Case-Lookups mit konstanter Zeit zu erzielen, können Sie sich über dynamisches perfektes Hashing informieren , das Kollisionen rekursiv mit einer anderen Hash-Tabelle auflöst!

jtb
quelle
2

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

Ob Sie die Tabelle beim Hinzufügen von Elementen vergrößern müssen oder nicht, ist für die Frage nicht relevant, da es um die Suchzeit geht.

Antti Huima
quelle
2

Elemente in der HashMap werden als Array verknüpfter Listen (Knoten) gespeichert. Jede verknüpfte Liste im Array repräsentiert einen Bucket für den eindeutigen Hashwert eines oder mehrerer Schlüssel.
Beim Hinzufügen eines Eintrags in der HashMap wird der Hashcode des Schlüssels verwendet, um die Position des Buckets im Array zu bestimmen.

location = (arraylength - 1) & keyhashcode

Hier steht das & für den bitweisen UND-Operator.

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

Während des Abrufvorgangs wird auf dieselbe Weise die Position des Buckets für den Schlüssel bestimmt. Im besten Fall hat jeder Schlüssel einen eindeutigen Hashcode und führt zu einem eindeutigen Bucket für jeden Schlüssel. In diesem Fall verbringt die Methode get nur Zeit, um die Position des Buckets zu bestimmen und den Wert abzurufen, der konstant O (1) ist.

Im schlimmsten Fall haben alle Schlüssel denselben Hashcode und werden in demselben Bucket gespeichert. Dies führt dazu, dass die gesamte Liste durchlaufen wird, was zu O (n) führt.

Im Fall von Java 8 wird der Bucket der verknüpften Liste durch eine TreeMap ersetzt, wenn die Größe auf mehr als 8 ansteigt. Dies reduziert die Sucheffizienz im ungünstigsten Fall auf O (log n).

Ramprabhu
quelle
1

Dies gilt grundsätzlich für die meisten Hash-Tabellen-Implementierungen in den meisten Programmiersprachen, da sich der Algorithmus selbst nicht wirklich ändert.

Wenn in der Tabelle keine Kollisionen vorhanden sind, müssen Sie nur eine einzige Suche durchführen, daher beträgt die Laufzeit O (1). Wenn Kollisionen vorliegen, müssen Sie mehr als eine Suche durchführen, wodurch die Leistung in Richtung O (n) verringert wird.

Tobias Svensson
quelle
1
Dies setzt voraus, dass die Laufzeit durch die Suchzeit begrenzt ist. In der Praxis gibt es viele Situationen, in denen die Hash-Funktion die Grenze (String) bereitstellt
Stephan Eggermont
1

Dies hängt vom gewählten Algorithmus ab, um Kollisionen zu vermeiden. Wenn Ihre Implementierung eine separate Verkettung verwendet, tritt das Worst-Case-Szenario auf, in dem jedes Datenelement auf denselben Wert gehasht wird (z. B. schlechte Auswahl der Hash-Funktion). In diesem Fall unterscheidet sich die Datensuche nicht von einer linearen Suche in einer verknüpften Liste, dh O (n). Die Wahrscheinlichkeit, dass dies geschieht, ist jedoch vernachlässigbar und die besten und durchschnittlichen Nachschlagefälle bleiben konstant, dh O (1).

Nizar Grira
quelle
1

Abgesehen von Akademikern sollte aus praktischer Sicht akzeptiert werden, dass HashMaps keine Auswirkungen auf die Leistung hat (sofern Ihr Profiler Ihnen nichts anderes sagt).

Ryan Emerle
quelle
4
Nicht in praktischen Anwendungen. Sobald Sie eine Zeichenfolge als Schlüssel verwenden, werden Sie feststellen, dass nicht alle Hash-Funktionen ideal sind und einige sehr langsam.
Stephan Eggermont
1

Nur im theoretischen Fall, wenn Hashcodes immer unterschiedlich sind und der Bucket für jeden Hashcode ebenfalls unterschiedlich ist, existiert O (1). Andernfalls ist die Reihenfolge konstant, dh beim Inkrementieren der Hashmap bleibt die Suchreihenfolge konstant.

sn.anurag
quelle
0

Natürlich hängt die Leistung der Hashmap von der Qualität der Funktion hashCode () für das angegebene Objekt ab. Wenn die Funktion jedoch so implementiert wird, dass die Wahrscheinlichkeit von Kollisionen sehr gering ist, hat sie eine sehr gute Leistung (dies ist nicht in jedem möglichen Fall streng O (1), aber in den meisten Fällen Fällen).

Die Standardimplementierung in der Oracle-JRE besteht beispielsweise darin, eine Zufallszahl zu verwenden (die in der Objektinstanz gespeichert ist, damit sie sich nicht ändert - aber auch die voreingenommene Sperrung deaktiviert, aber das ist eine andere Diskussion), damit die Wahrscheinlichkeit von Kollisionen besteht sehr niedrig.

Grauer Panther
quelle
"es ist in den meisten Fällen". Insbesondere tendiert die Gesamtzeit gegen K mal N (wobei K konstant ist), während N gegen unendlich tendiert.
ChrisW
7
Das ist falsch. Der Index in der Hash-Tabelle wird bestimmt, über hashCode % tableSizedie es durchaus zu Kollisionen kommen kann. Sie können die 32-Bit-Version nicht vollständig nutzen. Das ist der Sinn von Hash-Tabellen ... Sie reduzieren einen großen Indizierungsbereich auf einen kleinen.
FogleBird
1
"Es ist garantiert, dass es keine Kollisionen gibt." Nein, nicht, weil die Größe der Karte kleiner als die Größe des Hash ist. Wenn beispielsweise die Größe der Karte zwei beträgt, ist eine Kollision garantiert (egal was zum Hash) wenn / wenn ich versuche drei Elemente einzufügen.
ChrisW
Aber wie konvertiert man von einem Schlüssel in die Speicheradresse in O (1)? Ich meine wie x = Array ["Schlüssel"]. Der Schlüssel ist nicht die Speicheradresse, daher müsste es sich immer noch um eine O (n) -Suche handeln.
Paxdiablo
1
"Ich glaube, wenn Sie hashCode nicht implementieren, wird die Speicheradresse des Objekts verwendet." Es könnte dies verwenden, aber der Standard-Hashcode für das Standard-Oracle Java ist tatsächlich eine 25-Bit-Zufallszahl, die im Objektheader gespeichert ist, sodass 64/32-Bit keine Konsequenz hat.
Boann