Kurs:Algorithmen und Datenstrukturen/Vorlesung/Hashtabellen Aufwand



AufwandBearbeiten

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äuferBearbeiten

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.

SondierenBearbeiten

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.