wake-up-neo.com

Können Hashtabellen wirklich O (1) sein?

Es scheint allgemein bekannt zu sein, dass Hashtabellen O (1) erreichen können, aber das hat für mich nie Sinn gemacht. Kann das bitte jemand erklären? Hier sind zwei Situationen, die mir einfallen:

A. Der Wert ist ein int kleiner als die Größe der Hashtabelle. Daher ist der Wert ein eigener Hash, daher gibt es keine Hash-Tabelle. Wenn es aber einen gäbe, wäre es O(1) und wäre immer noch ineffizient.

B. Sie müssen einen Hashwert des Werts berechnen. In dieser Situation ist die Reihenfolge O(n) für die Größe der nachgeschlagenen Daten. Die Suche könnte O(1) sein, nachdem Sie O(n) arbeiten, aber das ergibt immer noch O(n) in meinen Augen.

Und wenn Sie keinen perfekten Hash oder eine große Hash-Tabelle haben, gibt es wahrscheinlich mehrere Elemente pro Bucket. Es wird also sowieso irgendwann eine kleine lineare Suche.

Ich finde Hashtabellen fantastisch, aber ich bekomme nicht die Bezeichnung O(1) =, es sei denn, es soll nur theoretisch sein.

Der Artikel für Hashtabellen der Wikipedia verweist konsistent auf die konstante Nachschlagzeit und ignoriert die Kosten der Hashfunktion vollständig. Ist das wirklich eine faire Maßnahme?


Edit: Um zusammenzufassen, was ich gelernt habe:

  • Dies ist technisch richtig, weil die Hash-Funktion nicht alle Informationen im Schlüssel verwenden muss und daher eine konstante Zeit sein kann und weil eine ausreichend große Tabelle Kollisionen auf eine nahezu konstante Zeit bringen kann.

  • In der Praxis trifft dies zu, da es im Laufe der Zeit nur klappt, wenn die Hash-Funktion und die Tabellengröße so gewählt werden, dass Kollisionen minimiert werden. Dies bedeutet jedoch häufig, dass keine konstante Hash-Funktion verwendet wird.

94
drawnonward

Sie haben hier zwei Variablen, m und n, wobei m die Länge der Eingabe und n die Anzahl der Elemente im Hash ist.

Der O(1) Lookup-Leistungsanspruch macht mindestens zwei Annahmen:

  • Ihre Objekte können in O(1) - Zeit gleichgestellt werden.
  • Es wird wenige Hash-Kollisionen geben.

Wenn Ihre Objekte eine variable Größe haben und bei einer Gleichheitsprüfung alle Bits geprüft werden müssen, wird die Leistung zu O (m). Die Hash-Funktion muss jedoch nicht O(m) sein - es kann O (1) sein. Im Gegensatz zu einem kryptografischen Hash muss eine Hash-Funktion zur Verwendung in einem Wörterbuch nicht jedes Bit in der Eingabe betrachten, um den Hash zu berechnen. Implementierungen können nur eine feste Anzahl von Bits betrachten.

Bei ausreichend vielen Elementen wird die Anzahl der Elemente größer als die Anzahl möglicher Hashes, und es kommt zu Kollisionen, die zu einem Leistungsanstieg über O (1) führen, zum Beispiel O(n) für einen einfachen Durchlauf einer verknüpften Liste ( oder O (n * m), wenn beide Annahmen falsch sind).

In der Praxis ist zwar die Behauptung von O(1) zwar technisch falsch, für viele Situationen der realen Welt näherungsweise wahr, und insbesondere für jene Situationen, in denen die obigen Annahmen zutreffen.

50
Mark Byers

Sie müssen den Hash berechnen, also ist die Reihenfolge O(n) für die Größe der gesuchten Daten. Das Nachschlagen könnte O(1) sein, nachdem Sie O(n) arbeiten, aber das kommt immer noch in O(n) in meinen Augen heraus.

Was? Ein einzelnes Element zu hashieren benötigt konstante Zeit. Warum sollte es etwas anderes sein? Wenn Sie n-Elemente einfügen, müssen Sie ja n-Hashes berechnen, und das dauert lineare Zeit ... um ein Element nachzuschlagen, berechnen Sie einen einzelnen Hashwert, nach dem Sie suchen, und suchen Sie dann den entsprechenden Bucket damit. Sie berechnen die Hashes von allem, was sich bereits in der Hash-Tabelle befindet, nicht neu.

Und wenn Sie nicht einen perfekten Hash oder eine große Hash-Tabelle haben, gibt es wahrscheinlich mehrere Elemente pro Bucket, so dass er ohnehin in eine kleine lineare Suche übergeht.

Nicht unbedingt. Die Buckets müssen nicht unbedingt Listen oder Arrays sein. Sie können einen beliebigen Containertyp haben, z. B. eine ausgeglichene BST. Das bedeutet O(log n) den schlimmsten Fall. Aus diesem Grund ist es wichtig, eine gute Hashfunktion zu wählen, um zu vermeiden, dass zu viele Elemente in einen Eimer gelegt werden. Wie KennyTM darauf hingewiesen hat, erhalten Sie im Durchschnitt immer noch O(1) Zeit, auch wenn Sie gelegentlich durch einen Eimer graben müssen.

Der Austausch von Hashtabellen ist natürlich die Komplexität des Platzes. Sie tauschen Raum für Zeit, was in der Informatik der übliche Fall zu sein scheint.


Sie erwähnen die Verwendung von Strings als Schlüssel in einem Ihrer anderen Kommentare. Sie machen sich Sorgen, wie viel Zeit es dauert, um den Hash einer Zeichenkette zu berechnen, weil er aus mehreren Zeichen besteht. Wie jemand anderes noch einmal betont hat, müssen Sie nicht unbedingt alle Zeichen betrachten, um den Hash zu berechnen, obwohl dies einen besseren Hash erzeugen könnte, wenn Sie dies tun. In diesem Fall, wenn im Durchschnitt m Zeichen in Ihrem Schlüssel vorhanden sind und Sie alle zur Berechnung Ihres Hashes verwendet haben, haben Sie vermutlich Recht, dass für die Suche O(m) erforderlich wäre. Wenn m >> n dann ein Problem vorliegt. In diesem Fall wären Sie mit einer BST wahrscheinlich besser dran. Oder wählen Sie eine günstigere Hash-Funktion.

19
mpen

Der Hash hat eine feste Größe - nach dem entsprechenden Hash-Bucket zu suchen, ist ein Vorgang mit festen Kosten. Dies bedeutet, dass es O (1) ist.

Die Berechnung des Hashes muss keine besonders teure Operation sein - wir sprechen hier nicht über kryptografische Hashfunktionen. Aber das ist vorbei. Die Hash-Funktionsberechnung selbst hängt nicht von der Anzahl n der Elemente ab. Während dies von der Größe der Daten in einem Element abhängen kann, ist dies nicht das, worauf sich n bezieht. Die Berechnung des Hashes hängt also nicht von n ab und ist auch O (1).

4
David M

Hashing ist O(1) nur, wenn die Tabelle nur eine konstante Anzahl von Schlüsseln enthält und andere Annahmen gemacht werden. Aber in solchen Fällen hat es einen Vorteil.

Wenn Ihr Schlüssel eine n-Bit-Darstellung hat, kann Ihre Hash-Funktion 1, 2, ... n dieser Bits verwenden. Denken Sie an eine Hash-Funktion, die 1 Bit verwendet. Die Bewertung ist sicher O(1). Sie teilen jedoch nur den Schlüsselbereich in 2 auf. Sie ordnen also bis zu 2 ^ (n-1) -Tasten in derselben Ablage ein. Bei Verwendung der BST-Suche sind bis zu n-1 Schritte erforderlich, um einen bestimmten Schlüssel zu finden, wenn er fast voll ist.

Sie können dies erweitern, um zu sehen, dass Ihre Bin-Größe 2 ^ (n-k) ist, wenn Ihre Hash-Funktion K Bits verwendet.

so K-Bit-Hash-Funktion ==> nicht mehr als 2 ^ K effektive Bins ==> bis zu 2 ^ (n-K) n-Bit-Schlüssel pro Bin ==> (n-K) Schritte (BST) zum Auflösen von Kollisionen. Tatsächlich sind die meisten Hash-Funktionen viel weniger "effektiv" und benötigen/verwenden mehr als K Bits, um 2 ^ k-Bins zu erzeugen. Also auch das ist optimistisch.

Sie können es so anzeigen - Sie müssen ~ n Schritte machen, um im schlimmsten Fall ein Schlüsselpaar von n Bits eindeutig unterscheiden zu können. Es gibt keine Möglichkeit, diese informationstheoretische Grenze, Hashtabelle oder nicht zu umgehen.

Dies ist jedoch NICHT wie/wenn Sie Hash-Tabelle verwenden!

Bei der Komplexitätsanalyse wird davon ausgegangen, dass für n-Bit-Schlüssel O (2 ^ n) Schlüssel in der Tabelle vorhanden sein könnten (z. B. 1/4 aller möglichen Schlüssel). Die meiste Zeit, wenn nicht immer, verwenden wir jedoch eine Hash-Tabelle. Wir haben nur eine konstante Anzahl der n-Bit-Schlüssel in der Tabelle. Wenn Sie nur eine konstante Anzahl von Schlüsseln in der Tabelle wünschen, beispielsweise C Ihre maximale Anzahl ist, könnten Sie eine Hashtabelle mit O(C) - Bins bilden, die eine erwartete konstante Kollision (mit einer guten Hashfunktion) garantiert. ; und eine Hash-Funktion, die ~ logC der n Bits im Schlüssel verwendet. Dann ist jede Abfrage O(logC) = O (1). So behaupten Leute, "Hash-Tabellenzugriff ist O (1)" /

Hier gibt es ein paar Fänge - erstens, dass Sie nicht alle Bits benötigen, kann nur ein Abrechnungstrick sein. Erstens können Sie den Schlüsselwert nicht wirklich an die Hash-Funktion übergeben, da dies n Bits im Speicher verschieben würde, die 0 (n) sind. Sie müssen also z. eine Referenzübergabe. Sie müssen es aber trotzdem irgendwo aufbewahren, was eine O(n) -Operation war. Sie berechnen es einfach nicht dem Hashing; Ihre Gesamtrechenaufgabe kann sich dem nicht entziehen. Zweitens machen Sie das Hashing, finden den Behälter und finden mehr als 1 Schlüssel. Ihre Kosten hängen von Ihrer Auflösungsmethode ab. Wenn Sie einen Vergleich durchführen (BST oder Liste), haben Sie die Funktion O(n) (Abrufen-Taste ist n-Bit). Wenn Sie einen zweiten Hash ausführen, haben Sie dasselbe Problem, wenn der zweite Hash eine Kollision hat. O(1) ist also nicht zu 100% garantiert, es sei denn, Sie haben keine Kollision (Sie können die Chance verbessern, indem Sie einen Tisch mit mehr Fächern als Schlüsseln haben, aber immer noch). 

Betrachten Sie die Alternative, z. BST in diesem Fall. Es gibt C-Tasten, also wird eine ausgeglichene BST O(logC) in die Tiefe gehen, so dass eine Suche O(logC) Schritte erfordert. In diesem Fall wäre der Vergleich jedoch eine O(n) -Operation ... daher scheint es, dass Hashing in diesem Fall die bessere Wahl ist. 

2
Eugene D

TL; DR: Hash-Tabellen garantieren O(1) den erwarteten Worst-Case-Zeitpunkt, wenn Sie Ihre Hash-Funktion gleichmäßig zufällig aus einer universellen Familie von Hash-Funktionen auswählen. Der erwartete schlechteste Fall ist nicht derselbe wie der durchschnittliche Fall.

Haftungsausschluss: Ich beweise nicht, dass Hash-Tabellen O(1) sind. Schauen Sie sich dazu dieses Video von coursera an [ 1 ]. Ich diskutiere auch nicht die abgeschrieben Aspekte von Hash-Tabellen. Das ist orthogonal zur Diskussion über Hashing und Kollisionen.

Ich sehe in anderen Antworten und Kommentaren eine überraschend große Verwirrung um dieses Thema und werde versuchen, einige von ihnen in dieser langen Antwort zu korrigieren.

Über den schlimmsten Fall nachdenken

Es gibt verschiedene Arten der Worst-Case-Analyse. Die Analyse, die die meisten Antworten hier bisher gemacht haben ist nicht schlimmster Fall, sondern durchschnittlicher Fall [ 2 ]. Die durchschnittliche Fallanalyse ist in der Regel praktischer. Möglicherweise verfügt Ihr Algorithmus über einen Eingang für den schlechtesten Fall, funktioniert jedoch auch für alle anderen möglichen Eingänge. Unterm Strich ist Ihre Laufzeit hängt von der Datenmenge ab auf der Sie laufen.

Betrachten Sie den folgenden Pseudocode der Methode get einer Hash-Tabelle. Hier gehe ich davon aus, dass wir Kollisionen durch Verketten behandeln, sodass jeder Tabelleneintrag eine verknüpfte Liste von (key,value) - Paaren ist. Wir nehmen auch an, dass die Anzahl der Buckets m fest ist, aber O(n), wobei n die Anzahl der Elemente in der Eingabe ist.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Wie andere Antworten gezeigt haben, liegt dieser Wert im Durchschnitt bei O(1) und im ungünstigsten Fall bei O(n). Wir können hier eine kleine Skizze eines Beweises durch Herausforderung machen. Die Herausforderung lautet wie folgt:

(1) Sie geben einem Gegner Ihren Hash-Tabellen-Algorithmus.

(2) Der Gegner kann es studieren und sich so lange vorbereiten, wie er will.

(3) Schließlich gibt Ihnen der Gegner eine Eingabe der Größe n, die Sie in Ihre Tabelle einfügen können.

Die Frage ist: Wie schnell ist Ihre Hash-Tabelle bei der Eingabe des Gegners?

Ab Schritt (1) kennt der Gegner Ihre Hash-Funktion; während Schritt (2) kann der Gegner eine Liste von n Elementen mit demselben hash modulo m erstellen, z. zufälliges Berechnen des Hash einer Reihe von Elementen; und dann in (3) können sie Ihnen diese Liste geben. Aber siehe da alle n Elemente im selben Bucket gehasht haben, benötigt Ihr Algorithmus O(n) Zeit, um die verknüpfte Liste in diesem Bucket zu durchlaufen. Egal wie oft wir die Herausforderung wiederholen, der Gegner gewinnt immer und so schlecht ist Ihr Algorithmus, der schlimmste Fall O(n).

Wie kommt es, dass Hashing O (1) ist?

Was uns bei der vorherigen Herausforderung störte, war, dass der Gegner unsere Hash-Funktion sehr gut kannte und dieses Wissen nutzen konnte, um die schlechtestmöglichen Eingaben zu machen. Was wäre, wenn wir anstatt immer eine feste Hash-Funktion zu verwenden, tatsächlich eine Reihe von Hash-Funktionen hätten, H, aus denen der Algorithmus zur Laufzeit zufällig auswählen kann? Falls Sie neugierig sind, wird H eine universelle Familie von Hash-Funktionen genannt []. Okay, lass uns versuchen, etwas Zufälligkeit hinzuzufügen.

Nehmen wir zunächst an, unsere Hash-Tabelle enthält auch einen Startwert r, und r wird zur Konstruktionszeit einer Zufallszahl zugewiesen. Wir weisen es einmal zu und dann ist es für diese Hash-Tabellen-Instanz behoben. Kommen wir nun zu unserem Pseudocode.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Wenn wir die Herausforderung noch einmal versuchen: Ab Schritt (1) kann der Gegner alle Hash-Funktionen kennen, die wir in H haben, aber jetzt hängt die spezifische Hash-Funktion, die wir verwenden, von r ab. Der Wert von r ist für unsere Struktur privat, der Angreifer kann ihn weder zur Laufzeit prüfen noch im Voraus vorhersagen, sodass er keine Liste erstellen kann, die für uns immer schlecht ist. Nehmen wir an, dass der Gegner in Schritt (2) eine Funktion hash in H zufällig auswählt und dann eine Liste von n Kollisionen unter hash modulo m Erstellt. und sendet dies für Schritt (3), wobei die Finger gekreuzt werden, die zur Laufzeit H[r] die gleichen hash sind, die sie gewählt haben.

Dies ist eine ernsthafte Wette für den Gegner. Die Liste, die er erstellt hat, kollidiert unter hash, ist jedoch nur eine zufällige Eingabe unter jeder anderen Hash-Funktion in H. Wenn er diese Wette gewinnt, ist unsere Laufzeit der schlechteste Fall O(n) wie zuvor, aber wenn er verliert, erhalten wir nur eine zufällige Eingabe, die die durchschnittliche O(1) Zeit in Anspruch nimmt. Und tatsächlich verliert der Gegner meistens, er gewinnt nur einmal alle |H| Herausforderungen und wir können |H| Sehr groß machen.

Vergleichen Sie dieses Ergebnis mit dem vorherigen Algorithmus, bei dem der Gegner immer die Herausforderung gewonnen hat. Hier ein bisschen mit der Hand winken, aber da die meisten Male der Gegner scheitert und dies für alle möglichen Strategien gilt, die der Gegner versuchen kann, folgt, dass der schlimmste Fall O(n) ist. ist der erwartete schlechteste Fall tatsächlich O(1).


Auch dies ist kein formeller Beweis. Die Garantie, die wir aus dieser erwarteten Worst-Case-Analyse erhalten, ist, dass unsere Laufzeit jetzt unabhängig von einer bestimmten Eingabe ist. Dies ist eine wirklich zufällige Garantie, im Gegensatz zur durchschnittlichen Fallanalyse, bei der wir gezeigt haben, dass ein motivierter Gegner leicht schlechte Eingaben machen kann.

1
Edman

A. Der Wert ist ein int kleiner als die Größe der Hash-Tabelle. Daher ist der Wert ein eigener Hash, sodass es keine Hash-Tabelle gibt. Aber wenn ja, wäre es O(1) und immer noch ineffizient.

Dies ist ein Fall, in dem Sie die Schlüssel trivial verschiedenen Buckets zuordnen können, sodass ein Array eine bessere Auswahl an Datenstrukturen bietet als eine Hash-Tabelle. Dennoch wachsen die Ineffizienzen nicht mit der Tabellengröße.

(Möglicherweise verwenden Sie immer noch eine Hash-Tabelle, da Sie nicht sicher sind, dass die ints kleiner als die Tabellengröße bleiben, wenn sich das Programm weiterentwickelt. Sie möchten den Code potenziell wiederverwendbar machen, wenn diese Beziehung nicht besteht, oder Sie tun es einfach nicht wollen, dass Menschen, die den Code lesen/pflegen, geistige Anstrengungen aufwenden müssen, um die Beziehung zu verstehen und aufrechtzuerhalten).

B. Sie müssen einen Hash des Werts berechnen. In dieser Situation ist die Reihenfolge O(n) für die Größe der Daten, nach denen gesucht wird. Die Suche könnte O(1) sein, nachdem Sie O(n) gearbeitet haben, aber das kommt in meinen Augen immer noch zu O(n).

Wir müssen zwischen der Größe des Schlüssels (z. B. in Bytes) und der Größe der Anzahl von Schlüsseln, die in der Hash-Tabelle gespeichert sind, unterscheiden. Behauptungen, die Hash-Tabellen O(1) -Operationen liefern, bedeuten, dass Operationen (Einfügen/Löschen/Suchen) nicht dazu neigen, sich weiter zu verlangsamen mit zunehmender Anzahl der Schlüssel von Hunderten auf Tausende auf Millionen auf Milliarden (zumindest nicht, wenn alle Daten in gleich schnellem Speicher abgerufen/aktualisiert werden, sei dies RAM oder Disk - Cache-Effekte können ins Spiel kommen, aber selbst die Kosten eines Cache-Fehlschlags im schlimmsten Fall sind in der Regel ein konstantes Vielfaches des Best-Case-Treffers.

Stellen Sie sich ein Telefonbuch vor: Sie haben vielleicht Namen, die ziemlich lang sind, aber ob das Buch 100 Namen oder 10 Millionen Namen hat, die durchschnittliche Namenslänge wird ziemlich konsistent sein und der schlimmste Fall in der Geschichte ...

Der Guinness-Weltrekord für den längsten Namen, den jemals jemand verwendet hat, wurde von Adolph Blaine Charles David Earl Gerald Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Senior, aufgestellt

...wc sagt mir, dass das 215 Zeichen sind - das ist keine feste Obergrenze für die Schlüssellänge, aber wir brauchen uns keine Sorgen zu machen, dass massiv mehr.

Dies gilt für die meisten Hash-Tabellen der realen Welt: Die durchschnittliche Schlüssellänge wächst nicht mit der Anzahl der verwendeten Schlüssel. Es gibt Ausnahmen, zum Beispiel kann eine Schlüsselerstellungsroutine Zeichenfolgen zurückgeben, die inkrementelle Ganzzahlen einbetten, aber selbst dann, wenn Sie die Anzahl der Schlüssel um eine Größenordnung erhöhen, erhöhen Sie die Schlüssellänge nur um 1 Zeichen: dies ist nicht signifikant.

Es ist auch möglich, einen Hash aus einer festgelegten Menge von Schlüsseldaten zu erstellen. Zum Beispiel wird Microsoft Visual C++ mit einer Standardbibliothek-Implementierung von std::hash<std::string> ausgeliefert, die einen Hash mit nur zehn Bytes erstellt, die gleichmäßig entlang der Zeichenfolge verteilt sind O(1) Verhaltensweisen auf der Nach-Kollisions-Suchseite), aber die Zeit zum Erstellen des Hashs hat eine harte Obergrenze.

Und es sei denn, Sie haben einen perfekten Hash oder eine große Hash-Tabelle, gibt es wahrscheinlich mehrere Artikel pro Eimer. Es geht also sowieso irgendwann in eine kleine lineare Suche über.

Allgemein wahr, aber das Tolle an Hashtabellen ist, dass die Anzahl der Schlüssel, die während dieser "kleinen linearen Suche" besucht wurden, - für die getrennte Verkettung von Kollisionen - eine Funktion von ist Hash-Tabelle Ladefaktor (Verhältnis von Schlüsseln zu Eimern).

Beispielsweise ergibt sich bei einem Lastfaktor von 1,0 ein Durchschnitt von ~ 1,58 für die Länge dieser linearen Suchvorgänge, unabhängig von der Anzahl der Schlüssel (siehe meine Antwort hier ). Für geschlossenes Hashing ist es etwas komplizierter, aber nicht viel schlimmer, wenn der Ladefaktor nicht zu hoch ist.

Dies ist technisch richtig, da die Hash-Funktion nicht alle Informationen im Schlüssel verwenden muss und daher eine konstante Zeit sein kann und eine ausreichend große Tabelle Kollisionen auf nahezu konstante Zeit reduzieren kann.

Diese Art von verfehlt den Punkt. Jede Art von assoziativer Datenstruktur muss letztendlich manchmal Operationen über jeden Teil des Schlüssels ausführen (Ungleichheit kann manchmal nur aus einem Teil des Schlüssels bestimmt werden, aber Gleichheit erfordert im Allgemeinen, dass jedes Bit berücksichtigt wird). Zumindest kann er den Schlüssel einmal hashen und den Hash-Wert speichern, und wenn er eine ausreichend starke Hash-Funktion verwendet - z. 64-Bit-MD5 - möglicherweise wird sogar die Möglichkeit, dass zwei Schlüssel denselben Wert haben, praktisch ignoriert (ein Unternehmen, für das ich gearbeitet habe, hat genau das für die verteilte Datenbank getan: Die Zeit der Hash-Generierung war im Vergleich zu WAN-weiten Netzwerkübertragungen immer noch unbedeutend). Es macht also keinen Sinn, sich über die Kosten für die Verarbeitung des Schlüssels Gedanken zu machen: Das Speichern von Schlüsseln ist unabhängig von der Datenstruktur und verschlechtert sich, wie oben erwähnt, im Durchschnitt nicht, wenn mehr Schlüssel vorhanden sind.

Bei Hash-Tabellen, die groß genug sind, um Kollisionen zu vermeiden, fehlt auch der Punkt. Für die getrennte Verkettung haben Sie bei jedem Lastfaktor immer noch eine konstante durchschnittliche Länge der Kollisionskette - sie ist nur höher, wenn der Lastfaktor höher ist, und diese Beziehung ist nicht linear. Der SO Benutzer Hans kommentiert meine Antwort auch oben verlinkt dass:

die durchschnittliche Schaufellänge bei nicht leeren Schaufeln ist ein besseres Maß für die Effizienz. Es ist ein/(1-e ^ {- a}) [wobei a der Lastfaktor ist, e 2,71828 ...]

Der Ladefaktor allein bestimmt die durchschnittliche Anzahl der kollidierenden Schlüssel, die Sie während Einfüge-/Lösch-/Suchvorgängen durchsuchen müssen. Bei einer getrennten Verkettung nähert es sich nicht einfach der Konstanz, wenn der Lastfaktor niedrig ist - es ist immer konstant. Für die offene Adressierung hat Ihre Behauptung jedoch eine gewisse Gültigkeit: Einige kollidierende Elemente werden in alternative Buckets umgeleitet und können dann die Operationen auf anderen Schlüsseln stören, sodass sich die Länge der Kollisionskette bei höheren Belastungsfaktoren (insbesondere> .8 oder .9) dramatisch verschlechtert.

In der Praxis ist dies der Fall, da es im Laufe der Zeit nur funktioniert, solange die Hash-Funktion und die Tabellengröße so gewählt werden, dass Kollisionen minimiert werden, obwohl dies häufig bedeutet, dass keine Hash-Funktion mit konstanter Zeit verwendet wird.

Nun, die Tabellengröße sollte einen vernünftigen Ladefaktor ergeben, wenn Sie zwischen engem Hashing oder getrennter Verkettung wählen. Aber auch, wenn die Hash-Funktion etwas schwach ist und die Tasten nicht sehr zufällig sind, hilft es oft, die Anzahl der Buckets zu reduzieren Auch Kollisionen (hash-value % table-size werden dann so umbrochen, dass Änderungen nur an einem oder zwei höherwertigen Bits im Hash-Wert noch zu pseudozufällig über verschiedene Teile der Hash-Tabelle verteilten Buckets führen).

0
Tony Delroy

Es gibt zwei Einstellungen, unter denen Sie O(1) im schlechtesten Fall erhalten können.

  1. Wenn Ihr Setup statisch ist, erhalten Sie durch FKS-Hashing den schlechtesten Fall O(1). Ihre Einstellung ist jedoch nicht statisch.
  2. Wenn Sie Kuckuck-Hashing verwenden, werden Abfragen und Löschungen O(1) Worst-Case, aber das Einfügen wird nur O(1) erwartet. Kuckuckshashing funktioniert recht gut, wenn Sie eine Obergrenze für die Gesamtzahl der Einfügungen haben und die Tabellengröße auf etwa 25% erhöhen.

Kopiert von hier

0
ChaosPredictor

Auf der Diskussion hier scheint es so zu sein, dass, wenn X die Obergrenze von (Anzahl der Elemente in der Tabelle/Anzahl der Behälter) ist, die bessere Antwort O(log(X)) ist, wenn eine effiziente Implementierung der Bin-Suche vorausgesetzt wird.

0
nak