Für welche Art von Daten sind Hashtabellenoperationen O (1)?

Aus den Antworten auf (Wann) ergibt sich die Hash-Tabellensuche O (1)? Ich stelle fest, dass Hash-Tabellen das schlechteste Verhalten von aufweisen, zumindest amortisiert, wenn die Daten bestimmte statistische Bedingungen erfüllen, und dass es Techniken gibt, mit denen sich diese Bedingungen erweitern lassen.$O(1)$

Aus Sicht eines Programmierers weiß ich jedoch nicht im Voraus, wie meine Daten aussehen werden: Sie stammen häufig aus einer externen Quelle. Und ich habe selten alle Daten auf einmal: Oft geschieht das Einfügen und Löschen mit einer Geschwindigkeit, die nicht weit unter der Rate der Suchvorgänge liegt. Daher ist die Vorverarbeitung der Daten zur Feinabstimmung der Hash-Funktion nicht möglich.

Gehen Sie also einen Schritt zurück: Wie kann ich bei Kenntnis der Datenquelle feststellen, ob eine Hash-Tabelle die Chance hat, -Operationen auszuführen , und welche Techniken für meine Hash-Funktion möglicherweise verwendet werden?$O(1)$

Es gibt verschiedene Techniken, die sicherstellen, dass Suchvorgänge auch im schlimmsten Fall immer O (1) -Operationen erfordern.

Wie kann ich feststellen, ob eine Hash-Tabelle eine Chance auf O (1) -Operationen hat und welche Techniken möglicherweise für meine Hash-Funktion verwendet werden?

Der schlimmste Fall tritt ein, wenn ein böswilliger Angreifer (Mallory) Ihnen absichtlich Daten zur Verfügung stellt, die Mallory speziell ausgewählt hat, um das System langsam laufen zu lassen.

Sobald Sie eine bestimmte Hash-Funktion ausgewählt haben, ist es wahrscheinlich zu optimistisch anzunehmen, dass Mallory nie herausfinden wird, welche Hash-Funktion Sie ausgewählt haben. Sobald Mallory feststellt, welche Hash-Funktion Sie ausgewählt haben, können Sie mit Mallory viele Daten in Ihre Hash-Tabelle einfügen. Dann sind Sie zum Scheitern verurteilt: Mallory kann intern schnell Milliarden von Datenelementen generieren und diese mit Ihren Hash-Daten versehen Die Hash-Funktion ermittelt, welche Datenelemente wahrscheinlich kollidieren, und füttert Sie dann mit Millionen von Eins-zu-Tausend-Datenelementen, die wahrscheinlich kollidieren. Dies führt zu Suchvorgängen, die viel langsamer als O (1) ausgeführt werden.

Alle Techniken, die "O (1) Lookups auch im schlimmsten Fall" garantieren, vermeiden dieses Problem, indem Sie ein wenig zusätzliche Arbeit an jeder Einfügung leisten, um zu gewährleisten, dass in Zukunft jede mögliche Suche in O (1) -Zeit erfolgreich sein kann . Insbesondere nehmen wir an (schlimmster Fall), dass Mallory früher oder später herausfinden wird, welche Hash-Funktion wir verwenden; Er hat jedoch nur die Möglichkeit, einige Datenelemente einzufügen, bevor wir eine andere Hash-Funktion auswählen - Tabellierungs-Hashing oder eine andere universelle Hashing-Funktion -, die wir speziell auswählen, damit alle Daten, die wir bisher haben, in 2 nachgeschlagen werden können oder 3 Sonden - dh O (1). Da wir diese Funktion zufällig auswählen, können wir ziemlich sicher sein, dass Mallory für eine Weile nicht weiß, welche Funktion wir ausgewählt haben. Auch wenn MalloryGibt uns sofort Daten, die selbst mit dieser neuen Hash-Funktion mit früheren Daten kollidieren, können wir dann noch eine neue Hash-Funktion auswählen, so dass nach dem erneuten Aufbereiten alle früheren Daten, die er und alle anderen uns zugeführt haben, jetzt angezeigt werden können in 2 oder 3 Sonden im schlimmsten Fall - dh O (1) Lookups im schlimmsten Fall.

Es ist ziemlich einfach, eine neue Hash-Funktion zufällig auszuwählen und die gesamte Tabelle häufig genug zu überarbeiten, um sicherzustellen, dass jede Suche immer O (1) ist. Während dies garantiert, dass jede Suche immer O (1) ist, können diese Techniken beim Einfügen des N-ten Elements in eine Hash-Tabelle, die bereits N-1 Elemente enthält, gelegentlich O (N) Zeit für diese Einfügung erfordern. Es ist jedoch möglich, das System so zu gestalten, dass, selbst wenn Mallory Ihnen absichtlich neue Daten gibt, die mit der neuen Hash-Funktion mit früheren Daten kollidieren, das System viele Elemente von Mallory und anderen akzeptieren kann, bevor es eine Aktion ausführen muss vollständiger O (N) Umbau. Hashtabellentechniken, die eine neue Funktion auswählen und erneut aufbereiten, um O (1) -Suchvorgänge auch im schlimmsten Fall zu gewährleisten, umfassen:

• Kuckuck-Hashing garantiert, dass jede Schlüsselsuche mit höchstens 2 Hash-Berechnungen und 2 Tabellensuchen erfolgreich ist.
• Hopscotch-Hashing garantiert, dass jede Schlüsselsuche erfolgreich ist, nachdem bei einer kleinen Anzahl von H (möglicherweise H = 32) aufeinanderfolgenden Einträgen in der Tabelle geprüft wurde .
• dynamisches, perfektes Hashing - das Papier von Dietzfelbinger aus dem Jahr 1994 ist das erste, das ich gelesen habe und das darauf hinwies, dass es möglich ist, auch wenn es "häufig" wiederholt wird, um zu gewährleisten, dass jede Schlüsselsuche mit zwei Hash-Berechnungen und zwei Nachschlägen immer erfolgreich ist eine vollständige Wiederaufbereitung so selten durchzuführen, dass die erwarteten durchschnittlichen Kosten für das Einfügen und Löschen von Daten, obwohl bei jeder vollständigen Wiederaufbereitung O (n) -Zeit erforderlich ist, O (1) amortisiert werden.

Datenstrukturen / Hash-Tabellen

$O(1)$

$O(1)$$O (n^2 W)$

$O(\sqrt{\log n / \log \log n})$$O(1)$

$h_{a,b}(x) = ax + b \mod p$

In der Vergangenheit haben laut einem Usenix-Artikel von Crosby und Wallach die gängigen Programmiersprachen nichts dergleichen getan, sodass viele Web-Apps (und andere Server) einem DoS-Angriff ausgesetzt waren, der auf Produktionskollisionen beruhte. (Das Papier stammt aus dem Jahr 2003, aber es deutet darauf hin, dass Dan Bernstein die gleiche Idee schon viel früher entdeckt hat.)

Eine schnelle Google-Suche gibt an, dass der Stand der Technik in Bezug auf Implementierungen sowohl verbessert als auch nicht verbessert wurde .

Eine weitere Ausnahme ist, dass es in einer Welt mit hoher Bandbreite aufgrund von Timing-Angriffen nicht so schwer ist, Kollisionen online zu finden (im Gegensatz zu Offline, wie der Crosby-Wallach-Link vorschlägt). Ich erinnere mich anscheinend, dass Daniel Golovin vor einigen Jahren Ergebnisse zu Datenstrukturen erzielt hat, die nicht für Timing-Angriffe anfällig sind, aber ich weiß nicht, ob sie weit verbreitet sind.

Die Durchschnittsanalyse für die Hash-Tabellen erfolgt unter der üblichen Annahme, dass die Eingaben einheitlich sind, was früher aufgrund des Rasiermessers von Occam der Fall war.

Wenn Sie zusätzliche Kenntnisse über die Domäne und die Verteilung der Schlüssel haben, können Sie dieselbe Durchschnittsfallanalyse durchführen und die einheitliche Verteilung durch Ihre Verteilung ersetzen und die Erwartungen zumindest theoretisch neu berechnen.

Die Schwierigkeit ergibt sich natürlich aus der Tatsache, dass eine ungleichmäßige Durchschnittsfallanalyse schwierig ist. Und Ihr „Wissen“ kann möglicherweise nicht bequem als eine Distribution ausgedrückt werden, die in einer solchen Analyse leicht verwendet werden kann.

Am einfachsten sind natürlich Simulationen. Implementieren Sie die Hash-Tabellen und beobachten Sie, wie sie für Ihre typischen Eingaben ausgeführt werden.

$n$$n!$