Hashtable als assoziative Arrays

In vielen Fällen wird ein möglichst schnelles Nachschlagen von Daten benötigt:

• Textprogramme überprüfen "nebenbei" die Rechtschreibung eingegebener Wörter
• Bei der Erfassung von Maut-Daten muss aus der ausgelesenen ID ein passender Datensatz rasch gefunden werden
• In Gendatenbanken muss sehr oft nach bestimmten Genschnipseln gesucht werden.
• Eine Telefonauskunft benötigt aus vielen Millionen Datensätzendie Angaben eines Kunden
• Bei der Speicherverwaltung benötigt das Betriebssystem in Laufzeit notwendige Daten über belegte Blöcke, vorhandene Inhaltsverzeichnisse, etc.
• Compiler benötigen zur Übersetzung die im Programm definierten Namen möglichst rasch

Die Lösung für diese Fragen bieten sogenannte Hashtabellen. Sie vereinen die Vorteile von Arrays (Direktzugriff auf ein Element) mit den Vorteilen verlinkter Listen (dynamisches Wachsen).

Zu diesem Thema gibt es vom Massachusetts Institute of Technology (MIT) einen interessanten Videomitschnitt:

http://videolectures.net/mit6046jf05_leiserson_lec07/