Hash-Tabelle Kollisionswahrscheinlichkeit
Wahrscheinlichkeit mindestens einer Kollision nach n Einfügungen in m Slots (Geburtstagsparadoxon-Näherung): P = 1 − e^(−n²/(2·m)).
Hash-Tabelle Kollisionswahrscheinlichkeit berechnen
Wahrscheinlichkeit mindestens einer Kollision nach n Einfügungen in m Slots (Geburtstagsparadoxon-Näherung): P = 1 − e^(−n²/(2·m)).
Worum geht es?
Diese Formel ist die direkte Anwendung des Geburtstagsparadoxons auf Hash-Tabellen. Werden n Elemente in m Slots mit gleichverteilter Hash-Funktion eingefügt, ergibt sich die Wahrscheinlichkeit für mindestens eine Kollision näherungsweise zu P = 1 − e^(−n²/(2·m)).
Die kontraintuitive Konsequenz: schon bei n ≈ √m ist eine Kollision wahrscheinlicher als 50 %. Das hat direkte Implikationen für die Sicherheit von Hash-Werten — ein 64-Bit-Hash kollidiert mit hoher Wahrscheinlichkeit bereits nach 2³² ≈ 4 Mrd. Eingaben, nicht erst nach 2⁶⁴.
Die Formel
P = 1 − e^(−n² / (2 · m))
Herleitung (Birthday-Approximation):
P ≈ 1 − exp(− C(n,2) / m)
= 1 − exp(− n(n−1) / (2m))
≈ 1 − exp(− n² / (2m)) für n ≫ 1Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| n | Elemente | — | Anzahl eingefügter Schlüssel. |
| m | Tabellengröße | — | Anzahl möglicher Hash-Werte / Slots. |
| P | Kollisions-W. | — | Wahrscheinlichkeit ≥ 1 Kollision. |
Minimal-Beispiel
23 Personen, 365 mögliche Geburtstage:
P = 1 − e^(−23² / (2 · 365))
= 1 − e^(−0,7247)
≈ 0,5155
≈ 51,5 %Praxis-Beispiele
Beispiel 1 — Hash-Tabelle mit 1024 Slots
100 Elemente in m = 1024:
P = 1 − e^(−100² / 2048)
= 1 − e^(−4,883)
≈ 0,9924
≈ 99,2 %Trotz Lastfaktor α ≈ 0,1 ist eine Kollision praktisch sicher — das ist normal und der Grund, warum Hash-Tabellen Chaining oder Open Addressing brauchen.
Beispiel 2 — UUID v4 (128 Bit)
Ab wie vielen UUIDs liegt die Kollisions-W. bei 50 %?
Setze P = 0,5:
0,5 = 1 − e^(−n²/(2 · 2¹²⁸))
⇒ n ≈ √(2 · 2¹²⁸ · ln 2)
≈ 2,17 · 10¹⁹Eine UUID-Kollision ist praktisch ausgeschlossen.
Beispiel 3 — 32-Bit-Hash für 100 000 Einträge
m = 2³² ≈ 4,29 · 10⁹
n = 100 000
P = 1 − e^(−10¹⁰ / (8,59 · 10⁹))
≈ 1 − e^(−1,164)
≈ 0,688
≈ 68,8 %Ein 32-Bit-Hash ist für 100 000 Einträge ungeeignet — mindestens 64 Bit verwenden.