Hash-Tabelle (Hash Map)
Datenstruktur, die Schlüssel in amortisiert O(1)-Zeit auf Werte abbildet — der Baustein hinter dict/HashMap/Object in fast jeder Sprache.
Eine Hash-Funktion bildet Schlüssel auf einen Bucket-Index ab. Kollisionen werden per Chaining (verkettete Liste je Bucket — Standard bei Javas HashMap) oder Open Addressing gelöst (Linear/Quadratic Probing — Pythons dict, Gos map, Rusts HashBrown). Resize, sobald der Load Factor ~0,75 übersteigt.
Worst Case O(n) bei schlechter Hash-Funktion. Die HashDoS-Angriffe (2011) zwangen alle Sprachen zu geseedeten Hashfunktionen (SipHash). Robin-Hood-Hashing und Hopscotch-Hashing sind moderne Varianten mit besserer Cache Locality.