Hash Table

In Python heißt es dict ({"name": "Max"}). In JavaScript Object oder Map. Es ist die vielleicht wichtigste Datenstruktur überhaupt. Wann immer du "suchen" musst, nutze eine Hash Map. Es sei denn, du brauchst die Daten sortiert (Hashes sind chaotisch unsortiert).

1. Kollisionen

Was, wenn "Harry Potter" und "Herr der Ringe" zufällig die gleiche Regal-Nummer (Hash) bekommen? Das nennt man Kollision. Die Hash Map muss das lösen:

• Chaining: Im Regal steht eine kleine Liste mit beiden Büchern.
• Open Addressing: "Nimm einfach das nächste freie Regal." Zu viele Kollisionen machen die Hash Map langsam (O(n) im Worst Case).

2. Load Factor

Wie voll ist die Map? Wenn 100 Regale da sind und 90 voll sind (Load Factor 0.9), gibt es viele Kollisionen. Deshalb vergrößert sich die Hash Map automatisch (Resizing), wenn sie zu ca. 75% voll ist. Das Kopieren kostet kurz Zeit, aber danach ist sie wieder schnell.

1. Hash Flooding (DoS) und SipHash

Ein katastrophales Design in alten Python- und Node-Versionen: MurmurHash oder CityHash. Beide Hashfunktionen rasend schnell, aber kryptografisch unsicher (Berechenbar). Hacker sandten präzise kalkulierte JSON-Keys ("a1", "b4"), die im Server absichtlich alle auf den exakt gleichen Hash-Bucket crashten. Die $\mathcal{O}(1)$ Map kollabierte in eine verlinkte Liste mit Suchzeit $\mathcal{O}(N)$. Bei 100.000 Insertions verbrannte die Webserver CPU für Minuten in purer LinkedList-Traversierung (Hash Collision DoS). Modernes dict oder HashMap nutzt daher rand-seeded Hashes (wie SipHash24), die sich bei jedem frischen Programmstart kryptographisch randomisieren. Der Angreifer kann die Kollisionsvektoren extern nicht mehr erraten.

2. Hash-Mapping: Open Addressing (Linear Probing vs Cuckoo Hashing)

Bei High-Performance C++ (Robin Hood Hashing / Cuckoo Hashing), meidet man Linked-List-Ketten (Chaining) extrem. Warum? Weil Chaining Pointers verfolgt, was Cache Misses in der CPU (L1/L2) produziert (teuer!). Open Addressing nutzt ein einziges flaches Contiguous Array. Wenn Slot A besetzt ist, schiebt man den Key einfach in Slot A+1 (Linear Probing). Durch Spatial Locality liest der CPU-Cache dies fast umsonst. Beim Cuckoo Hashing existieren $N=2$ Hashfunktionen. Ist Slot A besetzt, kickt das neue Item den Vorbesitzer brutal aus dem Nest. Der gefeuerte Key weicht auf seinen alternativen Hash-Slot $h_2(x)$ aus. Droht dort ein Loopback, fliegen Items zyklisch raus, bis alles sitzt. Liefert garantiert striktes $\mathcal{O}(1)$ Lookup im Worst Case.

3. Tombstones beim Delete

Das perfideste Problem bei Open Addressing. Man sucht Key X. Sein Hash lieferte Index 5. Es gab einst Kollision, er rutschte auf Index 6. Wird der Node in Index 5 später gelöscht (Index ist "frei"), und du suchst nach X, springt der Lookup-Pointer auf 5, sieht "leer!" und beendet die Iteration sofort fälschlicherweise (Element Not Found). Deswegen darf man Slots nicht eiskalt nullen. Man legt eine Beerdigungsflagge (Tombstone) aufs Feld ("Hier war mal wer, check unbedingt weiter auf Index 6"). Ist die Tabelle durch massiven Insert/Delete Code zum Großteil mit Tombstones vollgemüllt, blockiert Lookup massiv. Ein teurer globaler Rehash-Lauf fegt den Friedhof danach gnadenlos leer.