15 Hashverfahren
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, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
