|
Bei Hashing (zerhacken) handelt es sich um eine Methode für die direkte Bezugnahme auf Datensätze in einer Tabelle. Dies erfolgt mit Hilfe einer Funktion, die direkt aus dem jeweiligen Schlüssel die Adresse des zugehörigen Datensatzes errechnet.
Wenn man weiß, daß die Schlüssel nur ganze Zahlen von 1 bis N sind, kann beispielsweise der Datensatz mit dem Schlüssel 5 an der Tabellenposition 5 gespeichert werden.
Hashing ist eine Verallgemeinerung dieser Methode, wenn die speziellen Kenntnisse über die Schlüsselwerte nicht vorhanden sind.
Bei der Benutzung von Hashing sind zwei Punkte zu beachten:
1. Wahl einer geeigneten Hash-Funktion zur Berechnung der Tabellenadresse.
2. Da die Anzahl der verfügbaren Speicherplätze in der Regel geringer ist als die der möglichen Schlüssel, muß eine Funktion gewählt werden, die eine Doppelbelegung einer Adresse zuläßt. Die Art der Behandlung derartiger Kollisionen beeinflußt die Zugriffsdauer wesentlich.
Hashing ist ein guter Kompromiß zwischen Zeit- und Platzbedarf. Gäbe es keine Beschränkung des Speichers, könnte man jede beliebige Suche mit nur einem Zugriff auf den Speicher ausführen, wenn man den Schlüssel als Speicheradresse verwendet. Wenn es keine zeitliche Begrenzung gäbe, könnte man mit einem Minimum an Speicherplatz auskommen, indem man ein sequentielles Suchverfahren verwendet.
Hashing ermöglicht es, mit einem vertretbaren Maß an Speicherplatz als auch an Zeit auszukommen. Eine effiziente Nutzung der verfügbaren Speicherkapazität und ein schneller Zugriff auf den Speicher sind die vorrangigen Ziele jeder Hashing-Methode.
|
