Direkt zum Inhalt

Lexikon der Mathematik: offenes Hashverfahren

Methode zur Beseitigung von Kollisionen bei einem Hashverfahren.

Tritt bei der Suche nach einem Datensatz mit Hilfe eines Hashverfahrens eine Kollision auf, so gibt es verschiedene Methoden, diese Kollision zu beseitigen.

Eine einfache Methode ist das offene Hashverfahren. Dabei sieht man davon ab, die Eintragungen mit identischem Index H(k) zu einer Liste zu verknüpfen, sondern sucht einfach unter anderen Einträgen in der gleichen Tabelle, bis das gesuchte Element oder ein freier Platz gefunden ist, wobei man im letzten Fall davon ausgeht, daß das gesuchte Element nicht in der Tabelle vorhanden ist.

Dieses Verfahren läßt insofern noch einige Entscheidungsfreiheit zu, als die Methode, um aus einer potentiellen Adresse die nächste zu ermitteln, nicht von vornherein festgelegt ist. Es ist daher möglich, verschiedene Funktionen zur Berechnung der Adressen zu verwenden.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos