Laufzeit zum Einfügen von n Elementen in eine leere Hash-Tabelle

Question

Die Leute sagen, es dauert amortisiert O (1) in eine Hash-Tabelle zu setzen. Daher müssen n Elemente O (n) sein. Das stimmt jedoch nicht für große n, da ein Beantworter sagte: "Alles, was Sie benötigen, um das erwartete amortisierte O (1) zu erfüllen, ist, die Tabelle zu erweitern und alles mit einer neuen zufälligen Hash-Funktion zu wiederholen, wenn eine Kollision auftritt."

Also: Was ist die durchschnittliche Laufzeit von Einfügen von n Elementen in eine Hash-Tabelle? Mir ist klar, dass dies wahrscheinlich von der Implementierung abhängig ist. Erwähnen Sie daher, von welcher Art von Implementierung Sie sprechen.

Zum Beispiel, wenn es (log n) mit gleichem Abstand Kollisionen und jede Kollision nimmt O (k) zu lösen, wobei k die aktuelle Größe der Hash-Tabelle ist, dann würden Sie diese Rekursion haben:

(das heißt, Sie nehmen sich die Zeit, n/2 Elemente einzufügen, dann haben Sie eine Kollision, n/2 zu lösen, dann machen Sie die restlichen n/2 Einsätze ohne eine Kollision). Dies endet immer noch in O (n), also yay. Aber ist das vernünftig?

Answer 1

Es hängt vollständig davon ab, wie ineffizient Ihre Umwertung ist. Insbesondere wenn Sie die erwartete Größe Ihrer Hashtable das zweite Mal richtig schätzen können, nähert sich Ihre Laufzeit weiterhin O (n) an. Effektiv müssen Sie angeben, wie ineffizient die Berechnung der Wiederverwendungsgröße ist, bevor Sie die erwartete Reihenfolge bestimmen können.

Answer 2

Warum nicht einfach ein paar Tests auf Ihrem System durchführen? Vielleicht, wenn Sie die Quelle veröffentlichen, können wir zurückgehen und sie auf unseren Systemen testen und wir könnten das wirklich zu einer sehr nützlichen Diskussion formen.

Es ist einfach nicht die Implementierung, sondern die Umgebung entscheidet darüber, wie viel Zeit der Algorithmus tatsächlich benötigt. Sie können jedoch prüfen, ob Benchmarking-Stichproben verfügbar sind oder nicht. Das Problem, dass ich meine Ergebnisse gepostet habe, wird nutzlos sein, da die Leute keine Ahnung haben, was sonst auf meinem System läuft, wie viel RAM im Moment frei ist und so weiter. Du kannst immer nur eine Idee haben. Und das ist ungefähr so ​​gut wie das, was dir das große O gibt.

Answer 3

Die Leute sagen, es dauert amortisiert O (1) in eine Hash-Tabelle zu setzen.

Aus theoretischer Sicht ist es erwartet abgeschrieben O (1).

Hashtabellen sind grundsätzlich eine randomisierte Datenstruktur, in dem Sinne, dass Quicksort ein randomisierter Algorithmus ist. Sie müssen Ihre Hash-Funktionen mit einer gewissen Zufälligkeit generieren, sonst existieren pathologische Eingaben, die nicht O (1) sind.

Sie erwarten erreichen können abgeschrieben O (1) mit dynamic perfect hashing:

Die naiven Idee, die ich ursprünglich geschrieben auf jeder Kollision mit einer neuen zufälligen Hash-Funktion wieder aufwärmen. (Siehe auch perfect hash functions) Das Problem dabei ist, dass dies O (n^2) Raum vom Geburtstagsparadox erfordert.

Die Lösung ist zwei Hash-Tabellen zu haben, mit der zweiten Tabelle für Kollisionen; Lösen Sie Kollisionen an dieser zweiten Tabelle auf, indem Sie sie neu erstellen. Diese Tabelle wird O (\ sqrt {n}) -Elemente haben und somit auf O (n) wachsen. In der Praxis verwenden Sie oft nur eine feste Hash-Funktion, weil Sie davon ausgehen können, dass Ihre Eingabe pathologisch ist (ähnlich wie Sie oft Quicksort, ohne die Eingabe vorzuspannen).

Answer 4

Alle O (1) sagt, dass die Operation in konstanter Zeit ausgeführt wird, und es ist nicht abhängig von der Anzahl der Elemente in Ihrer Datenstruktur.

In einfachen Worten bedeutet dies, dass Sie die gleichen Kosten bezahlen müssen, egal wie groß Ihre Datenstruktur ist.

In der Praxis bedeutet dies, dass einfache Datenstrukturen wie Bäume im Allgemeinen effektiver sind, wenn Sie nicht viele Daten speichern müssen. Nach meiner Erfahrung finde ich Bäume schneller bis zu ~ 1k Elementen (32bit Ganzzahlen), dann übernehmen Hashtabellen. Aber wie immer YMMW.