Hash-Kollisionen: Wenn zwei Schlüssel denselben Platz wollen

Kurz: Eine Kollision entsteht, wenn zwei verschiedene Schlüssel in einer Hashtabelle auf denselben Platz abgebildet werden; Verfahren wie Verkettung lösen das.

Genauer: Eine Hashtabelle berechnet aus einem Schlüssel mit einer Hashfunktion eine Position im Array. Weil es mehr mögliche Schlüssel als Plätze gibt, treffen zwangsläufig manchmal zwei Schlüssel auf denselben Platz. Das ist unvermeidbar (Taubenschlagprinzip) und muss behandelt werden, damit beide Werte gefunden werden.

Im Detail

Verkettung (Separate Chaining)

Jeder Platz („Bucket“) enthält eine kleine Liste. Landen zwei Schlüssel im selben Bucket, stehen beide in der Liste, und die Suche vergleicht dort die Schlüssel. Das ist einfach und robust, Java HashMap arbeitet so (bei langen Listen wandeln sie sich in Bäume um).

Offene Adressierung

Alle Einträge liegen direkt im Array. Ist ein Platz belegt, sucht man einen anderen: lineares Sondieren probiert den nächsten Platz, quadratisches Sondieren größere Sprünge, doppeltes Hashing nutzt eine zweite Hashfunktion für die Schrittweite. Gelöschte Einträge müssen mit einer Markierung („Grabstein“) gekennzeichnet werden, damit Suchketten nicht abreißen. Spart Zeiger, ist aber bei fast vollem Array langsam.

Der Füllgrad

Der Load Factor ist Einträge geteilt durch Plätze. Je voller, desto mehr Kollisionen. Üblich ist, bei etwa 0,75 die Tabelle zu vergrößern (meist Verdopplung) und alle Einträge neu zu verteilen (Rehashing). Dadurch bleibt der mittlere Aufwand für Einfügen und Suchen konstant (O(1) im Durchschnitt).

Gute Hashfunktionen und Angriffe

Eine gute Funktion verteilt Schlüssel gleichmäßig und ist schnell. Ein Angreifer, der Hashfunktion und Tabelle kennt, kann viele Schlüssel erzeugen, die alle kollidieren, und die Anwendung durch O(n)-Zugriffe lahmlegen („Hash-Flooding“). Gegenmaßnahmen sind zufällig initialisierte Hashfunktionen (SipHash) oder Bäume in langen Buckets.

Siehe auch: HashMap, Hashing, Big-O-Notation, Bloom-Filter und Trie