|
Folien
Übungen
Programme
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 4: Hashverfahren
|
|
|
In den
Kapiteln 1 und 3 haben wir
einige Methoden kennengelernt, die es erlauben, eine Menge von Datensätzen
so zu speichern, dass die Operationen
Suchen, Einfügen und Entfernen unterstützt werden. Jeder Datensatz ist
dabei gekennzeichnet durch einen eindeutigen Schlüssel.
Zu jedem Zeitpunkt ist lediglich eine (kleine) Teilmenge S aller möglichen
Schlüssel K (englisch: keys) gespeichert. Statt nun bei der Suche nach einem
Datensatz mit Schlüssel k mehrere Schlüsselvergleiche mit Schlüsseln
aus S auszuführen, wird bei Hash-Verfahren versucht, durch eine Berechnung
festzustellen, wo der Datensatz mit Schlüssel k gespeichert ist.
Die Datensätze werden in einem linearen Feld mit Indizes
von 0 bis m - 1
gespeichert; dieses Feld nennt man die
Hashtabelle, m
ist die Größe der Hashtabelle.
Eine Abbildung, die Hashfunktion h ordnet jedem Schlüssel k
einen Index h(k) zwischen 0 und m - 1 zu, die Hashadresse. Im allgemeinen
ist S eine sehr kleine Teilmenge von K. Die Hashfunktion
kann also im allgemeinen nicht injektiv sein, sondern muß verschiedene Schlüssel
auf dieselbe Hashadresse abbilden.
Zwei Schlüssel k,k' mit h(k)=h(k') heißen Synonyme; befinden
sich beide Schlüssel in der aktuellen Schlüsselmenge K, so ergibt
sich eine Adresskollision. Treten
in K keine Synonyme auf, so kann jeder Datensatz in der Hashtabelle
an der seiner Hashadresse entsprechenden Stelle gespeichert werden. Bei
Adresskollisionen hingegen muß eine Sonderbehandlung vorgenommen werden.
Ein Hashverfahren muß also zwei Forderungen genügen. Erstens sollen möglichst
wenige Kollisionen auftreten. Dies kann angestrebt werden durch die Wahl
einer „guten“ Hashfunktion. Zweitens sollen Adresskollisionen möglichst
effizient aufgelöst werden.
|
|
Bei Fragen zu
dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|