Direkt zum Inhalt

Lexikon der Mathematik: Hashverfahren

ein Verfahren, bei dem aus dem Ordnungsbegriff eines Datensatzes mit Hilfe eines festgelegten Algorithmus die Adresse des Datensatzes berechnet wird.

Man kann Verfahren dieser Art so interpretieren, daß der Ordnungsbegriff zerlegt wird, um daraus die physische Adresse zu bestimmen (hash= zerkleinern, zerlegen). Ist K die Menge der Ordnungsbegriffe oder auch Schlüssel und A der Adreß- raum, so besteht das Problem in der Konstruktion einer geeigneten Abbildung H : KA, die man auch Schlüsseltransformation nennt. Die Hauptschwierigkeit bei der Verwendung einer Schlüsseltransformation liegt darin, daß die Menge der möglichen Schlüsselwerte meist deutlich größer ist als die Menge der verfügbaren Speicheradressen, weshalb die Funktion nicht injektiv sein kann. Daher muß das Suchen mit einem Hash- verfahren immer zwei Schritte haben. Der erste Schritt beim Suchen eines Elements mit dem Ordnungbegriff k besteht in der Berechnung des zugewiesenen Index H(k) = h. Der zweite Schritt ist dann die Prüfung, ob das erhaltene Bild-Element tatsächlich den Schlüssel k besitzt, das heißt, ob der Wert des Schlüsselattributs von T[h] auch wirklich gleich k ist. Man nennt dabei T die Hashtabelle oder auch Hashtafel.

Falls sich die zu einem gegebenen Schlüssel ermittelte Eintragung in der Hashtafel nicht als das gesuchte Element erweist, spricht man von einer Kollision, da in diesem Fall zwei Elemente Schlüssel besitzen, die auf das gleiche Element abgebildet werden. Für diesen Fall existieren verschiedene Methoden zur Auflösung von Kollisionen (Hashfunktion).

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.