Hashing ist ein sehr häufig angewandtes Verfahren, um Informationen (im Hauptspeicher) abzuspeichern und möglichst schnell wiederzufinden.

Die Beschreibungen von Hashing führen dabei das Problem, beliebige Informationen abzuspeichern und wiederzufinden, auf das Problem zurück, ganze Zahlen abzuspeichern und wiederzufinden. Diese Vereinfachung ist aufgrund der Universalität der Binärkodierung gerechtfertigt: Jedwede Information kann als eine Folge von Nullen und Einsen dargestellt werden, also als eine Zahl im Binärsystem.

Eine nicht ganz ernst gemeinte Schlussfolgerung aus dieser Universalität ist die Anleitung, wie man mit dem gesamten Wissen der Menschheit spazieren gehen kann: Man besuche alle Bibliotheken der Welt, schreibe alle Buchstaben aller Bücher hintereinander, kodiere die so erhaltene Zeichenfolge mit der ASCII-Kodierung und fasse die so entstandene Bitfolge als eine einzige, riesige Zahl W auf. Man berechne daraus die Zahl w=1/W, mache im Abstand von w Zentimetern eine Kerbe zum unteren Ende eines Spazierstocks, und wandere dann gestützt auf das gesammelte Wissen der Menscheit auf und davon.

Diese Anleitung krankt natürlich daran, dass die Zahl W so riesig ist, und daher der Reziprokwert w so klein, dass „im Abstand von w Zentimetern zum unteren Ende des Spazierstocks“ mit Sicherheit kein Molekül mehr sitzt, das man zur Kerbung benutzen könnte. Genauso kranken auch die Beschreibungen von Hashing meistens daran, dass die Größe der abzuspeichernden Zahlen, d. h. die Menge an Informationen, nicht in Betracht gezogen wird, und stattdessen so getan wird, als ob man an jede Speicherstelle i des Hauptspeichers eine beliebig große Zahl schreiben könnte.

In konkreten Implementierungen beschränkt man sich daher darauf, Zahlen aus einem bestimmten Bereich abspeichern und wiederfinden zu wollen; meistens ist dies das Intervall, das vom Typ int ausgefüllt wird, also der Bereich [-2^31..2^31-1]. Beliebige Informationen können gespeichert werden, indem diese auf einen Wert aus diesem Intervall abgebildet werden, den so genannten Hash-Wert. Fasst man diese Informationen als Schlüssel auf, so kann man zu ihnen weitere Informationen assoziieren, und dadurch zu einem assoziativen Containertyp gelangen. Datenstrukturen, die Hashing-Verfahren verwenden, um Schlüssel (und eventuell dazu assoziierte Informationen) zu speichern, werden als hashende Typen bezeichnet.

Dieser Abschnitt beschreibt die algorithmischen Grundlagen und die Schnittstelle der hashenden LEDA-Typen h_array (Hashing Array) und map.