Tokenlabor

Kollisionswahrscheinlichkeit berechnen

Kollisionswahrscheinlichkeit berechnen für Zufalls-IDs, UUIDs und Hashes: Wie groß ist das Risiko doppelter Werte bei n Einträgen und b Bit?

Ändern Sie Alphabet oder Länge, wird die Bit-Zahl daraus berechnet: b = Länge × log₂(Alphabet).

–

 

SchwelleAb so vielen WertenAnmerkung

Alles läuft in Ihrem Browser. Eingaben verlassen Ihr Gerät nicht.

Geburtstagsparadoxon für IDs und Hashes

Mit diesem Rechner können Sie die Kollisionswahrscheinlichkeit berechnen, also die Wahrscheinlichkeit, dass unter n zufällig erzeugten Werten mindestens zwei gleich sind. Dahinter steckt das Geburtstagsparadoxon: Schon bei 23 Personen haben mit über 50 Prozent zwei am selben Tag Geburtstag, obwohl das Jahr 365 Tage hat. Beim Birthday-Problem wächst die Gefahr nicht mit n, sondern mit n², weil jedes Paar zählt. Für Zufalls-IDs, Tokens und Hashes gilt genau dasselbe.

Gerechnet wird mit p ≈ 1 − e^(−n(n−1)/(2N)), wobei N = 2^b die Zahl möglicher Werte ist. Für kleine Wertebereiche bis eine Million rechnet das Werkzeug exakt als Produkt. Die Tabelle zeigt, ab wie vielen Werten bestimmte Schwellen erreicht sind; die 50-Prozent-Grenze liegt bei etwa 1,18 × √N. Für eine UUID-Kollision bei UUID v4 mit 122 Zufallsbits müssten Sie rund 2,7 × 10^18 IDs erzeugen, um auf 50 Prozent zu kommen. Eine Hash-Kollision bei einem auf 32 Bit gekürzten Hash wird dagegen schon ab etwa 77.000 Einträgen wahrscheinlich.

Praktisch nutzen Sie die Rechnung, um die ID-Länge berechnen zu können: Geben Sie Alphabet und Länge an und prüfen Sie, ob die Wahrscheinlichkeit für Ihre erwartete Menge klein genug ist. Grenzen: Die Formel setzt einen guten Zufallsgenerator voraus, etwa crypto.getRandomValues. Bei UUID v7 und ULID hängen die Zufallsbits an der Millisekunde; hier ist n die Zahl der IDs innerhalb derselben Millisekunde. Gezielte Angriffe auf Hash-Verfahren werden nicht betrachtet.

Anleitung: Kollisionswahrscheinlichkeit berechnen in 4 Schritten

  1. Wählen Sie unter „Vorlage“ ein bekanntes ID-Format wie UUID v4 oder einen kurzen Git-Hash, oder tragen Sie die Bit-Zahl selbst ein.
  2. Alternativ geben Sie „Zeichen im Alphabet“ und „Länge der ID“ an, etwa 62 und 8 für Base62-Kürzel; die Bit-Zahl wird daraus berechnet.
  3. Tragen Sie unter „Anzahl erzeugter Werte“ ein, wie viele IDs insgesamt entstehen, zum Beispiel 1e9 für eine Milliarde.
  4. Lesen Sie die Kollisionswahrscheinlichkeit ab und prüfen Sie in der Tabelle, ab wie vielen Werten 1 %, 50 % oder 1 zu 1 Million erreicht sind.

Typische Anwendungsfälle

  • Vor dem Einführen kurzer Links oder Bestellnummern prüfen, ob 6 oder 8 Zeichen für die erwartete Menge reichen.
  • Abschätzen, ob ein auf 8 Hex-Zeichen gekürzter Hash als Cache-Schlüssel oder Dateiname noch eindeutig genug ist.
  • In Code-Reviews begründen, warum UUID v4 oder ein 128-Bit-Zufallstoken praktisch kollisionsfrei ist.
  • Im Unterricht das Geburtstagsparadoxon mit 23 Personen und 365 Tagen nachrechnen.
Fragen

Häufige Fragen

Was besagt das Geburtstagsparadoxon?

Unter 23 Personen haben mit gut 50 Prozent Wahrscheinlichkeit zwei am selben Tag Geburtstag. Der Grund: Es gibt 253 mögliche Paare, und jedes Paar kann übereinstimmen. Bei IDs ist es genauso.

Kann es bei UUID v4 Kollisionen geben?

Theoretisch ja, praktisch kaum. Bei 122 Zufallsbits liegt die Wahrscheinlichkeit selbst nach einer Milliarde UUIDs bei etwa 10^-19. Voraussetzung ist ein guter Zufallsgenerator.

Ab wann ist eine Kollision wahrscheinlich?

Bei etwa 1,18 × √N Werten, wobei N die Zahl möglicher Werte ist. Bei 32 Bit sind das rund 77.000, bei 64 Bit rund 5 Milliarden.

Wie wähle ich die richtige ID-Länge?

Legen Sie fest, welche Kollisionswahrscheinlichkeit Sie tolerieren, etwa 1 zu 1 Million, und wie viele IDs insgesamt entstehen. Der Rechner zeigt, ob die Bit-Zahl reicht. Als Faustregel braucht man etwa 2·log₂(n) + 20 Bit.

Wie viele Zeichen braucht eine Kurz-ID für eine Million Einträge?

Für eine Kollisionswahrscheinlichkeit unter 1 zu 1 Million bei einer Million Werten braucht man rund 59 Bit, also etwa 10 Zeichen Base62 oder 15 Hex-Zeichen. Der Rechner zeigt das für Ihr Alphabet.

Gilt die Rechnung auch für Hashes wie SHA-256?

Ja, wenn die Eingaben verschieden sind und der Hash sich wie eine Zufallsfunktion verhält. Bei 256 Bit ist eine zufällige Kollision praktisch ausgeschlossen; gezielte Angriffe auf schwache Verfahren wie MD5 sind eine andere Frage.

Weitere Werkzeuge

Das könnte auch helfen

Alle 558 Werkzeuge

IBAN prüfen

IBAN-Prüfziffer (Mod 97) und Kreditkartennummer (Luhn) formal prüfen, ohne Speicherung.

Öffnen

Zahlensysteme umrechnen

Dezimal, Binär, Oktal, Hexadezimal und jede Basis von 2 bis 36, auch sehr große Zahlen.

Öffnen

Bit-Byte-Umrechner

Bit, Byte, Kilobit, Megabit, Gigabit und Mbit/s in MB/s umrechnen, dezimal und binär.

Öffnen

Dateigröße umrechnen

KB, MB, GB, TB und KiB, MiB, GiB umrechnen, mit Erklärung zu SI- und IEC-Einheiten.

Öffnen

Bitweise Operationen

AND, OR, XOR, NOT und Shifts mit Bitdarstellung für 8, 16, 32 und 64 Bit rechnen.

Öffnen

Römische Zahlen umrechnen

Zahlen in römische Ziffern und zurück umrechnen, 1 bis 3999, mit Prüfung der Schreibweise.

Öffnen