Warum hashtable, haben ständigen Zugang Zeit im Durchschnitt?
Verstehe ich nicht, diese Erklärung, die besagt, wenn n die Anzahl der Elemente in der Hashtabelle und m die Gesamtzahl der Eimer dann hashtables, haben ständigen Zugang Zeit im Durchschnitt nur dann, wenn n ist proportional zu theta(n). Warum muss es proportional ?
Du musst angemeldet sein, um einen Kommentar abzugeben.
naja, eigentlich m sollte proportional zu n ist. Ansonsten könnte man, zum Beispiel, haben nur 1 Eimer, und wäre es nur wie eine unsortierte set.
Genauer, wenn m proportional zu n, d.h. m = c * n, dann die Anzahl der Elemente in jeder Gruppe n/m = 1/c ist eine Konstante. Gehen zu jedem Eimer ist eine O(1) operation (nur die Berechnung der hash-code) und dann wird die Suche durch den Eimer ist konstant um (man könnte es auch einfach eine lineare Suche durch die Elemente in den Eimer, das wäre also eine Konstante).
Damit die Ordnung des Algorithmus ist O(1), wenn m = c * n.
Nehmen eine gegenteilige Beispiel, angenommen wir hätten eine Feste Größe der Tabelle mit der Größe tableSize. Dann ist die erwartete Anzahl der Elemente in jeder Gruppe n/tableSize ist eine lineare Funktion von n ist. Jede Art der Suche durch den Eimer ist bestenfalls O(log(n)) für den Baum (ich ' m vorausgesetzt, dass Sie nicht bleiben, eine weitere hash-Tabelle im Eimer oder wir haben dann das gleiche argument immer, dass die hash-Tabelle), so würde es sich nicht O(1) in diesem Fall.
n
) ist weniger als oder gleich der Anzahl der buckets (m
). Sonst haben wir eine situation, in derO(1 + |k|)
wobei k die Anzahl der Elemente in der kth Eimer.n <= m
, dannn
ist immer noch proportional zum
alsn = cm
woc <= 1
.Streng genommen, die average-case Zeitkomplexität der hash-Tabelle zugreifen ist eigentlich in Ω(n1/3). Informationen können nicht schneller Reisen als die Lichtgeschwindigkeit, die eine Konstante ist. Da der Raum drei Dimensionen hat, zu speichern
n
bits von Daten erfordert, dass einige Daten werden in einem Abstand in der Größenordnung von n1/3 von der CPU.Mehr Details in meinem blog.
Die chance von Kollisionen höher ist und somit die Inzidenz von mit Scannen durch die Liste der Objekte mit demselben hash-Schlüssel ist auch höher.
Zugriffszeit ist konstant, da der Zugang basiert auf einer Berechnung eines hash-Wertes und dann eine Konstante lookup zu finden, die entsprechenden Eimer. Vorausgesetzt, die hash-Funktion verteilt die posten unter den Eimer, dann die Zeit, die es braucht, um Zugriff auf jedem einzelnen Punkt ist gleich der Zeit, Zugriff auf andere Elemente, unabhängig von n.
Konstante bedeutet nicht unbedingt, ständig niedrig, aber. Die Durchschnittliche Zugriffszeit ist in Bezug auf die gleichmäßige Verteilung der Hash-Funktion und die Anzahl der buckets. Wenn Sie haben Tausende von Elementen gleichmäßig verteilt eine kleine Anzahl von Eimern, Sie finden die Eimer schnell, aber dann die Schleife durch eine Menge von Elementen in den Eimer. Wenn Sie einen guten Anteil der Eimer, um Elemente, aber eine schlechte hash-Funktion, die bringt viele weitere Artikel in einige Eimer eher als andere, die Zugriffszeit für die Elemente, die in größeren Eimer wird langsamer sein als die Zugriffszeit für andere.
Eine relativ große hash-Tabelle, wo es genug slots für jedes element, das Sie speichern und viel mehr Platz, wird die Hash-Funktion zu tun die meisten der Arbeit, die Auswahl an slots und nur sehr wenige Kollisionen, wo verschiedene Elemente haben den gleichen hash. Eine sehr überfüllten hash-Tabelle hätte viele Kollisionen, und würde sich sehr verschlechtern, dass im Grunde eine lineare Suche, wo fast jeder lookup wird ein Falsches Element, das hatte den gleichen hash, und Sie haben zu halten Sie auf der Suche für die richtige (ein-hash-Tabelle-lookup hat noch zu prüfen, den Schlüssel, sobald es wählt den ersten Steckplatz, weil der Schlüssel es sucht vielleicht hatte eine Kollision stattfindet, wenn es gespeichert wurde).
Was bestimmt der hit-Kollisions-Verhältnis ist genau das Verhältnis der Anzahl der Elemente, um die Größe der hash (d.h., die prozentuale Wahrscheinlichkeit, dass eine zufällig gewählte slot wird gefüllt).