Hash-Tabelle-Visualizer

Hash-Tabellen verwenden deterministische mathematische Algorithmen, um beliebige Schlüssel endlichen Indexräumen zuzuordnen und so den zeitlichen Abruf von O(1) zu optimieren. Kollisionen, eine unvermeidliche Folge des Schubladenprinzips, erfordern strenge Lösungsprotokolle. Die Verkettung basiert auf Zuordnungen verknüpfter Listen, während die lineare und quadratische Prüfung mathematische Schrittfunktionen zum Navigieren durch Array-Indizes verwendet. Der Lastfaktor bestimmt kontinuierlich die statistische Wahrscheinlichkeit dieser rechenintensiven Kollisionen.

Eine Hashtabelle ist nichts weiter als ein Array plus eine Regel — die Hashfunktion —, die jeden Schlüssel in eine Slotnummer umwandelt. Statt jeden Eintrag einzeln zu durchsuchen, berechnest du, wohin ein Element gehört, und springst direkt dorthin; deshalb bleiben Suchvorgänge selbst bei Millionen von Schlüsseln schnell. Der Haken: Das Tempo hängt von einer gleichmäßigen Verteilung der Schlüssel ab. Füge hier ein paar ein und beobachte, wie schnell zwei Schlüssel denselben Slot beanspruchen.

Weil eine Hashtabelle zu einer langsamen linearen Suche verkommt, sobald zu viele Schlüssel in einem Slot landen — genau der Worst Case, den du oben auslösen kannst —, kann ein Angreifer, der deine Hashfunktion kennt, Tausende von Schlüsseln erzeugen, die absichtlich kollidieren. 2011 legte dieser 'Hash-Flooding'-Trick Webserver in PHP, Java, Python und Ruby mit einer einzigen präparierten Anfrage lahm. Die Lösung waren zufällig initialisierte Hashfunktionen wie SipHash, heute in vielen Sprachen Standard.