Ich bin verwirrt über die Zeit Komplexität der Hash-Tabelle viele Artikel behaupten, dass sie "amortisiert O (1)" nicht wahr Reihenfolge O (1) was bedeutet das in realen Anwendungen. Was ist die durchschnittliche Zeitkomplexität der Operationen in einer Hash-Tabelle, in der tatsächlichen Implementierung nicht in der Theorie, und warum sind die Operationen nicht wahr O (1)?Zeit Komplexität der Hash-Tabelle
Für einige Verwendungen von Hashtabellen ist es unmöglich, sie im Voraus mit der "richtigen" Größe zu erstellen, da nicht bekannt ist, wie viele Elemente während der Lebensdauer der Tabelle gleichzeitig gehalten werden müssen. Wenn Sie schnellen Zugriff behalten möchten, müssen Sie die Tabelle von Zeit zu Zeit anpassen, wenn die Anzahl der Elemente zunimmt. Diese Größenänderung dauert linear in Bezug auf die Anzahl der Elemente, die bereits in der Tabelle vorhanden sind, und erfolgt normalerweise bei einer Einfügung, wenn die Anzahl der Elemente einen Schwellenwert überschreitet.
Diese Größenänderungsoperationen können selten genug durchgeführt werden, damit die amortisierten Einfügekosten immer noch konstant sind (indem Sie eine geometrische Progression für die Größe der Tabelle verfolgen, zum Beispiel die Größe bei jeder Größenänderung verdoppeln). Aber ein Einfügen von Zeit zu Zeit dauert O (n) Zeit, weil es eine Größenänderung auslöst.
In der Praxis ist dies kein Problem, es sei denn, Sie erstellen harte Echtzeitanwendungen.
Es ist nicht nur die Größe, die berücksichtigt wird - es sind auch die Hash-Kollisionen. Es gibt verschiedene Arten, mit ihnen umzugehen, aber was immer du tust, wird nicht in O (1) geschehen. Der durchschnittliche Fall ist in der Praxis immer noch nahe bei O (1), wenn die Hashtabelle nicht ganz voll ist – Jords
@Jords Ich weiß nicht, was "nahe bei O (1)" bedeutet.Außerdem bin ich ziemlich zuversichtlich, dass das "amortisierte O (1)", das in der Literatur gefunden wird, Hypothesen über die Hash-Funktion entspricht, bei denen die Bucket-Tiefe unter einer festen Grenze bleibt, daher konstante Zeit. Wenn das Nachschlagen ohne Größenänderung keine konstante Zeit wäre, wäre die amortisierte Nachschau sicherlich auch keine konstante Zeit. –
Es ist unmöglich, im Voraus zu wissen, wie viele Kollisionen Sie mit Ihrer Hash-Funktion bekommen, sowie Dinge wie die Größe ändern müssen. Dies kann der Leistung einer Hash-Tabelle ein Element der Unvorhersagbarkeit hinzufügen, was nicht wahr ist O (1). Praktisch alle Hashtabellen-Implementierungen bieten O (1) auf der riesigen, großen, überwiegenden Mehrheit von Einfügungen. Dies ist das gleiche wie das Einfügen von Arrays - es ist O (1), es sei denn, Sie müssen die Größe ändern, in diesem Fall ist es O (n) plus die Kollisionsunsicherheit.
In Wirklichkeit sind Hash-Kollisionen sehr selten und die einzige Bedingung, in der Sie sich um diese Details kümmern müssen, ist, wenn Ihr spezifischer Code ein sehr enges Zeitfenster hat, in dem er ausgeführt werden muss. Für praktisch jeden Anwendungsfall sind Hash-Tabellen O (1). Eindrucksvoller als O (1) Insertion ist O (1) Lookup.
Nun, O (1) Lookup gilt auch für Arrays –
Einfügen ein Wert in eine Hash-Tabelle, auf dem durchschnittlichen Fall nimmt, O (1) Zeit. Die Hash-Funktion ist berechnet, die Bock wird aus der Hash-Tabelle ausgewählt, und dann wird Element eingefügt. Im schlimmsten Fall, , haben alle Elemente Hashed auf den gleichen Wert, was bedeutet, dass entweder die gesamte Bucket-Liste durchlaufen werden muss, oder im Fall der offenen Adressierung muss die gesamte Tabelle bis zu einer leeren Stelle sondiert werden gefunden. daher im schlimmsten Fall, Insertion nimmt O (n) Zeit
beziehen: http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf (Hash Table Section)
Dieser Zusammenhang wird, wenn auch nicht genau die gleiche Frage: http://stackoverflow.com/ Fragen/2369467/Warum-sind-Hash-Tabelle-Erweiterungen-in der Regel-durch-Doubling-the-Size-gemacht –
Dies hilft, die Einfügung zu beantworten, aber erklärt nichts über die anderen Operationen, ich interessiere mich am meisten für eine Erklärung zu Die Zeit Komplexität der Suche in einer Hash-Tabelle – marme
Unter einigen Hypothesen auf die Hash-Funktion, Nachschlagen ist real O (1) Zeit für die meisten Hash-Tabellen-Implementierungen. Tatsächlich ist es in einigen Implementierungen mit beschränkter Bucket-Tiefe vom Design her konstant. –