Laufzeit einfügen von n Elementen in eine leere hash-Tabelle

Question

Die Leute sagen, es dauert amortisiert O(1), um in eine hash-Tabelle.Daher setzen n Elemente müssen O(n).Das ist nicht wahr für große n, da, wie ein Nutzer sagte, "Alles, was Sie brauchen, zu erfüllen voraussichtlich amortisiert O(1) ist um die Tabelle zu erweitern und sofort wieder alles mit einem neuen random-hash-Funktion zu jeder Zeit gibt es eine Kollision."

Also:was ist die Durchschnittliche Lauf-Zeit, das einfügen von n Elementen in eine hash-Tabelle?Ich weiß, das ist wahrscheinlich von der Implementierung abhängig, so erwähnen, welche Art von Implementierung, die Sie sprechen.

Zum Beispiel, wenn es (log n) mit gleichem Abstand Kollisionen, und jede Kollision in O(k) zu beheben, wobei k die aktuelle Größe der hashtable, dann hätten Sie diese recurrence relation:

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

(das heißt, Sie nehmen die Zeit, die zum einfügen von n/2 Elemente hat, so Sie haben eine Kollision, wobei n/2 zu beheben, dann müssen Sie die restlichen n/2 Einsätze ohne Kollision).Das noch endet als O(n), so yay.Aber ist das vernünftig?

Answer 1

Es hängt völlig ab, wie ineffizient Ihr Wiederkäuen ist. Insbesondere können, wenn Sie richtig die erwarteten Größe der Hash-Tabelle zum zweiten Mal schätzen, Ihre Laufzeit nähert sich immer noch O (n). Effektiv, müssen Sie angeben, wie ineffizient Ihre Aufguss Größenberechnung ist, bevor Sie die erwartete Reihenfolge bestimmen kann.

Answer 2

  

Die Leute sagen, es abgeschrieben O (1) nimmt in einer Hash-Tabelle zu setzen.

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

Hash-Tabellen sind im Grunde eine randomisierte Datenstruktur, im gleichen Sinne, dass quicksort ein randomisierte Algorithmus ist. Sie benötigen eine Hash-Funktionen mit einer gewissen Zufälligkeit zu erzeugen, oder aber es existieren pathologische Eingänge, die nicht O sind (1).

Sie können voraussichtlich abgeschrieben O erreichen (1) unter Verwendung von dynamisch perfekt Hashing :

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

Die Lösung ist zu haben zwei Hash-Tabellen, mit der zweiten Tabelle für Kollisionen; lösen Kollisionen auf dieser zweiten Tabelle durch den Wiederaufbau es. Diese Tabelle wird O (\ sqrt {n}) Elemente, so würde O (n) die Größe wachsen.

In der Praxis Sie oft nur eine feste Hash-Funktion verwenden, da man davon ausgehen kann (oder es egal, ob) Ihre Eingabe pathologisch ist, ähnlich wie man oft quicksort ohne die Eingabe prerandomizing.

Answer 3

All O (1) sagt, ist, dass der Betrieb in konstanter Zeit durchgeführt wird, und es ist nicht abhängig von der Anzahl der Elemente in der Datenstruktur.

In einfachen Worten bedeutet dies, dass Sie die gleichen Kosten zu zahlen haben, egal wie groß Ihre Datenstruktur ist.

In der Praxis bedeutet dies, dass einfache Datenstrukturen wie Bäume sind im Allgemeinen effektiver, wenn Sie müssen eine Menge Daten nicht speichern. Nach meiner Erfahrung finde ich Bäume schneller bis zu ~ 1k Elemente (32bit), dann Hash-Tabellen übernehmen. Aber wie üblich YMMW.

Answer 4

Warum nicht einfach zu laufen ein paar tests auf Ihrem system?Vielleicht, wenn Sie werde nach der Quelle, wir können gehen Sie zurück und testen Sie Sie auf unserer Systeme und eigentlich könnten wir in Form dieser in eine sehr nützliche Diskussion.

Es ist nicht nur die Umsetzung, sondern auch noch die Umwelt, der entscheidet, wie viel Zeit der Algorithmus tatsächlich braucht.Sie können jedoch schauen, ob irgendwelche benchmarking Proben sind vorhanden oder nicht.Das problem bei mir ist die Veröffentlichung meiner Ergebnisse wird nicht von nutzen sein, da die Menschen keine Ahnung haben, was auf meinem system ausgeführt wird, wie viel RAM frei ist jetzt und so weiter.Sie können immer nur eine Ungefähre Vorstellung.Und das ist ungefähr so gut wie das, was die big-O bietet.