Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


16. Hashing



Ein Ansatz für das Suchen, der sich von den auf Vergleichen beruhenden Baumstrukturen des vorangegangenen Kapitels vollkommen unterscheidet, beruht auf dem Hashing (»Zerhacken«). Dabei handelt es sich um eine Methode für die direkte Bezugnahme auf Datensätze in einer Tabelle durch Ausführung arithmetischer Transformationen, die Schlüssel in Tabellenadressen umwandeln. Wenn wir wissen, daß die Schlüssel unterschiedliche ganze Zahlen von 1 bis N sind, können wir den Datensatz mit dem Schlüssel i in der Tabellenposition i speichern, bereit für den unmittelbaren Zugriff mit Hilfe des Schlüsselwertes. Hashing ist eine Verallgemeinerung dieser einfachen Methode für typische Suchanwendungen, wenn wir solche speziellen Kenntnisse über die Schlüsselwerte nicht haben.

Der erste Schritt bei einer Suche unter Benutzung von Hashing ist die Berechnung einer Hash-Funktion, die den Suchschlüssel in eine Tabellenadresse transformiert. Im Idealfall sollten verschiedene Schlüssel auf verschiedene Adressen abgebildet werden, doch da keine Hash-Funktion perfekt ist, ist es möglich, daß zwei oder mehr unterschiedliche Schlüssel durch die Funktion auf die gleiche Tabellenadresse abgebildet werden. Daher besteht der zweite Teil einer Suche mit Hashing in einem Prozeß zur Kollisionsbeseitigung (collision-resolution), bei dem solche Schlüssel behandelt werden. Eine der Methoden zur Kollisionsbeseitigung, die wir untersuchen wollen, verwendet verkettete Listen. Sie ist in ausgeprägt dynamischen Situationen geeignet, wo die Anzahl der Suchschlüssel nicht im voraus angegeben werden kann. Die anderen beiden Verfahren zur Kollisionsbeseitigung, die wir betrachten werden, erzielen kurze Suchzeiten für Datensätze, die in einem Feld konstanter Größe gespeichert sind.

Hashing ist ein gutes Beispiel für einen Kompromiß zwischen Zeit- und Platzbedarf. Wenn es keine Beschränkung des Speichers gäbe, könnten wir jede beliebige Suche mit nur einem Zugriff auf den Speicher ausführen, indem wir einfach den Schlüssel als Speicheradresse verwenden. Wenn es keine zeitliche Begrenzung gäbe, könnten wir mit einem Minimum an Speicherplatz auskommen, indem wir ein sequentielles Suchverfahren benutzen. Hashing ermöglicht einen Weg, wie man mit einem vertretbaren Maß sowohl an Speicherplatz als auch an Zeit auskommen kann, so daß ein Gleichgewicht zwischen diesen beiden Extremen gefunden wird. Eine effiziente Nutzung der verfügbaren Speicherkapazität und ein schneller Zugriff auf den Speicher sind die vorrangigen Ziele jeder Hashing-Methode.

Hashing ist ein »klassisches« Problem der Informatik in dem Sinne, daß die verschiedenen Algorithmen recht gründlich untersucht worden sind und sehr große Verbreitung fanden. Für ein breites Spektrum von Anwendungen gibt es viele empirische und analytische Begründungen für die Zweckmäßigkeit von Hashing-Methoden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]