Hashstrukturen

Hashstrukturen, oft als Hash-Tabellen bezeichnet, sind eine Datenstruktur zur Abbildung von Schlüsseln auf Werte. Zentral ist eine Hash-Funktion, die aus einem Schlüssel eine ganzzahlige Zahl erzeugt, die als Index in einem Speicherbereich, dem Hash-Array, verwendet wird. Typische Operationen sind Einfügen, Suchen und Entfernen von Schlüssel-Wert-Paaren. Die Effizienz hängt von der Güte der Hash-Funktion und dem Füllgrad der Tabelle ab.

Bei jeder Operation wird der Schlüssel durch die Hash-Funktion verarbeitet, um den Ziel-Index zu bestimmen. Wenn mehrere Schlüssel denselben Index belegen (Kollisionen), muss eine Kollisionsauflösungsstrategie gewählt werden. Zwei Hauptansätze existieren: Verkettung und offene Adressierung. Bei der Verkettung verweist jeder Slot im Array auf eine Sammlung von Einträgen (z. B. eine Liste oder einen Baum). Bei offener Adressierung werden bei Kollisionen weitere Slots im selben Array untersucht, zum Beispiel durch lineares Sondieren, quadratisches Sondieren oder doppeltes Hashing.

Leistung und Skalierung hängen stark vom Load Factor ab. Erwartete durchschnittliche Zeitkomplexität für Suchen, Einfügen und Entfernen liegt bei O(1); im Worst-Case kann sie O(n) betragen. Um die Effizienz zu erhalten, wird die Tabelle oft vergrößert und neu aufgebaut (Rehashing), sobald der Load Factor einen Schwellenwert überschreitet.

Anwendungsgebiete umfassen Wörterbücher, Symboltabellen in Compilern, Caches und schnelle Lookups in Datenbanken. Varianten und Optimierungen umfassen dynamische Größenanpassung, universelle Hashfunktionen, Cuckoo-Hashing sowie den Einsatz von speziellen Strukturen zur Reduktion von Kollisionen. Kryptographische Hash-Funktionen werden in Hash-Tabellen aufgrund der geringeren Geschwindigkeit im Allgemeinen nicht bevorzugt.