Kurs:Algorithmen und Datenstrukturen/Vorlesung/Hashtabellen Aufwand

Aufwand

Auf dieser Seite wird der Aufwand von Hashtabellen behandelt.

Bei geringer Kollisionswahrscheinlichkeit beträgt der Aufwand beim Suchen O(1) und beim Einfügen ebenfalls O(1). Das Löschen bei den Sondierverfahren hat zwei mögliche Aufwandsklassen. Wenn nur die Einträge als gelöscht markiert werden, beträgt der Aufwand O(1), aber wenn ein Rehashen der gesamten Tabelle notwendig ist, dann beträgt der Aufwand O(n).

Verkettete Überläufer

Der Füllgrad (load factor) beträgt $\alpha =m/N$ wobei m die Anzahl der gespeicherten Elemente ist und N die Anzahl der Buckets. Bei erfolgloser Suche, das heißt bei Hashing mit Überlauflisten, beträgt der Aufwand $\mathrm{\Theta }(1+\alpha )$ Bei der erfolgreichen Suche ist der Aufwand ebenfalls in dieser Größenordnung.

Sondieren

Der Aufwand beim Suchen beträgt $\frac{1}{1-\alpha }$

Typische Werte sind $\frac{1}{1-0.5}=2$

und $\frac{1}{1-0.9}=10$

Die exakte Analyse basiert auf der Aufsummierung der Wahrscheinlichkeiten, dass i Elemente das Bucket i belegen bei einer Gleichverteilung.

Die Wahrscheinlichkeiten basieren auf dem Füllgrad $\alpha$. Wenn das Bucket belegt ist, ist die Wahrscheinlichkeit $\alpha$. Wenn das Bucket und das sondierte Bucket belegt sind, dann beträgt die Wahrscheinlichkeit ${\alpha }^2$.

$1+\alpha +{\alpha }^2+{\alpha }^3+...=\frac{1}{1-\alpha }$

Bei der erfolgreichen Suche ist der Aufwand besser, hat aber die gleiche Größenordnung. Bei einer mittleren Anzahl von Sondierungen über alle Schlüssel beträgt der Aufwand

$\frac{1}{\alpha }ln(\frac{1}{1-\alpha })$

Für ein $\alpha$ nahe 1 gilt $\frac{1}{\alpha }\to 1$

Bei $\alpha =0.99$ gilt, dass 100 Sondierungen für eine erfolglose Suche gebraucht werden und in 100= 5 erfolgreiche Suchen.