Zum Inhalt springen

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Hashtabellen Aufwand

Aus Wikiversity



Aufwand

[Bearbeiten]

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

[Bearbeiten]

Der Füllgrad (load factor) beträgt 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 Bei der erfolgreichen Suche ist der Aufwand ebenfalls in dieser Größenordnung.

Sondieren

[Bearbeiten]

Der Aufwand beim Suchen beträgt

Typische Werte sind

und

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 . Wenn das Bucket belegt ist, ist die Wahrscheinlichkeit . Wenn das Bucket und das sondierte Bucket belegt sind, dann beträgt die Wahrscheinlichkeit .

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

Für ein nahe 1 gilt

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


Discussion