15Hashverfahren

Mit den Baumverfahren haben wir effiziente Datenstrukturen zum Finden von Einträgen mittels Suchschlüsseln betrachtet, die uns einen logarithmischen Aufwand beim Suchen garantieren. Hashverfahren gehen einen ganz anderen Weg: Die Datensätze werden einfach in einem normalen Feld mit direktem Zugriff gespeichert und eine spezielle Funktion, die Hashfunktion, ermöglicht für jeden gespeicherten Wert den direkten Zugriff auf den Datensatz.

Statt einer ausgereiften Datenstruktur benötigen wir nun also eine ausgefeilte Funktion zur Adressberechnung, die fast »magische« Fähigkeiten besitzen muss – sind doch die konkreten abzuspeichernden Werte vorher nicht bekannt, und das Feld sollte natürlich auch nicht beliebig groß werden. Wir werden ...

Get Algorithmen und Datenstrukturen, 6th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.