Kollisionen: Chaining

Chaining speichert kollidierende Einträge in einer Liste (oder einem Baum) pro Bucket. Einfügen hängt an die Struktur des Buckets.

Vorteil: einfache Löschlogik. Nachteil: Zusatzzeiger und schlechte Cache-Lokalität bei langen Ketten.

Klassische HashMap-Buckets (historisch Listen, heute oft Bäume ab einer Schwelle). Verstehen von Chaining erklärt Worst-Case-Verhalten und Attacken mit kollidierenden Keys.

Vertiefung

Beim Chaining verweist jeder Tabellenplatz auf eine Sammlung aller Einträge, die dort landen. Suche, Einfügen und Löschen bearbeiten zuerst den Index und danach nur diese lokale Sammlung. Listen sind einfach, bei langen Ketten können auch andere Strukturen sinnvoll sein.

Ist die Verteilung brauchbar, bleibt die mittlere Kettenlänge durch den Lastfaktor kontrolliert. Im ungünstigen Fall sammeln sich jedoch sehr viele Schlüssel an einer Stelle, und die Suche nähert sich einer linearen Prüfung. Chaining toleriert eine Belegung oberhalb der Tabellenlänge, weil Buckets mehrere Einträge aufnehmen.

Schwierigkeitsstufen

1. Eine Kollision durch Einfügen in eine Bucketliste behandeln.
2. Erwartete Kettenlänge mit dem Lastfaktor in Beziehung setzen.
3. Den degenerierten Fall einer schlechten Hashfunktion analysieren.

Fallstricke

Beim Aktualisieren darf ein bereits gleichwertiger Schlüssel nicht blind als zweiter Eintrag angehängt werden. Ein weiterer Fehler ist, nur den Hashwert und nicht die Schlüsselgleichheit zu prüfen.