Laufzeit zum Einfügen von n Elementen in eine leere Hashtabelle

Question

Man sagt, dass es amortisiert O(1) dauert, eine Hashtabelle zu erstellen. Daher muss das Einfügen von n Elementen O(n) sein. Das stimmt jedoch nicht für große n, da, wie ein Antwortender sagte, "alles, was man braucht, um das erwartete amortisierte O(1) zu erfüllen, ist, die Tabelle zu erweitern und jedes Mal, wenn es eine Kollision gibt, alles mit einer neuen zufälligen Hash-Funktion neu zu zerlegen."

Also: Was ist die durchschnittliche Laufzeit der Einfügung n Elemente in eine Hashtabelle? Ich weiß, dass dies wahrscheinlich von der Implementierung abhängt, also geben Sie an, von welcher Art von Implementierung Sie sprechen.

Wenn es zum Beispiel (log n) gleichmäßig verteilte Kollisionen gibt und jede Kollision O(k) zur Auflösung benötigt, wobei k die aktuelle Größe der Hashtabelle ist, dann ergibt sich diese Rekursionsbeziehung:

T(n) = T(n/2) + n/2 + n/2

(d.h. man nimmt sich die Zeit, n/2 Elemente einzufügen, dann kommt es zu einer Kollision, die n/2 Zeit in Anspruch nimmt, um sie aufzulösen, dann führt man die restlichen n/2 Einfügungen ohne Kollision durch). Am Ende ist das immer noch O(n), also prima. Aber ist das vernünftig?

Answer 1

Das hängt ganz davon ab, wie ineffizient Ihre Aufbereitung ist. Insbesondere, wenn Sie die erwartete Größe Ihrer Hashtabelle beim zweiten Mal richtig einschätzen können, nähert sich Ihre Laufzeit immer noch O(n). Sie müssen also angeben, wie ineffizient die Berechnung der Rehash-Größe ist, bevor Sie die erwartete Reihenfolge bestimmen können.

Answer 2

Man sagt, es dauert amortisiert O(1), um in eine Hashtabelle zu kommen.

Vom theoretischen Standpunkt aus betrachtet, ist es erwartet amortisiert O(1).

Hash-Tabellen sind im Grunde eine randomisierte Datenstruktur, so wie Quicksort ein randomisierter Algorithmus ist. Sie müssen Ihre Hash-Funktionen mit einer gewissen Zufälligkeit generieren, da es sonst pathologische Eingaben gibt, die nicht O(1) sind.

Sie können das erwartete amortisierte O(1) erreichen, indem Sie dynamisches perfektes Hashing :

Die naive Idee, die ich ursprünglich gepostet hatte, war, bei jeder Kollision mit einer neuen zufälligen Hash-Funktion zu rehashen. (Siehe auch perfekte Hash-Funktionen ) Das Problem dabei ist, dass dafür O(n^2) Platz benötigt wird, vom Geburtstagsparadoxon.

Die Lösung besteht darin, dass zwei Hash-Tabellen, wobei die zweite Tabelle für Kollisionen verwendet wird; Kollisionen in dieser zweiten Tabelle werden durch Neuaufbau aufgelöst. Diese Tabelle hat O( \sqrt {n}) Elemente, würde also auf O(n) Größe anwachsen.

In der Praxis verwendet man oft einfach eine feste Hash-Funktion, weil man davon ausgehen kann (oder es einem egal ist), dass die Eingabe pathologisch ist, so wie man auch oft eine Quicksortierung durchführt, ohne die Eingabe vorher zu randomisieren.

Answer 3

O(1) besagt lediglich, dass die Operation in konstanter Zeit durchgeführt wird, und das ist no abhängig von der Anzahl der Elemente in Ihrer Datenstruktur.

Mit einfachen Worten bedeutet dies, dass Sie unabhängig von der Größe Ihrer Datenstruktur die gleichen Kosten zu tragen haben.

In der Praxis bedeutet dies, dass einfache Datenstrukturen wie z. B. Bäume allgemein effektiver, wenn Sie nicht viele Daten speichern müssen. Meiner Erfahrung nach sind Bäume bis zu ~1k Elementen (32-Bit-Ganzzahlen) schneller, danach übernehmen Hash-Tabellen die Führung. Aber wie üblich YMMW.

Answer 4

Warum führen Sie nicht einfach ein paar Tests auf Ihrem System durch? Wenn Sie den Quellcode veröffentlichen, können wir sie vielleicht auf unseren Systemen testen, und wir könnten daraus eine sehr nützliche Diskussion machen.

Es ist nicht nur die Implementierung, sondern auch die Umgebung, die darüber entscheidet, wie viel Zeit der Algorithmus tatsächlich benötigt. Sie können jedoch nachsehen, ob Benchmarking-Beispiele verfügbar sind oder nicht. Das Problem ist, dass es nichts bringt, wenn ich meine Ergebnisse poste, da die Leute keine Ahnung haben, was sonst noch auf meinem System läuft, wie viel RAM gerade frei ist und so weiter. Man kann immer nur eine grobe Vorstellung haben. Und das ist ungefähr so gut wie das, was das große O einem gibt.