Zufallszahlen in Java generieren – und vorhersagen

Die Generierung von Zufallszahlen (oder -Strings oder anderen zufälligen Objekten) ist eine der häufigsten Programmieraufgaben.

Dieser Artikel beschreibt:

• welche Möglichkeiten es in Java gibt, um Zufallszahlen zu generieren,
• warum es sich dabei um sogenannte „Pseudozufallszahlen“ handelt,
• welche Technik hinter deren Generierung steckt,
• wie man Zufallszahlen in Java vorhersagen kann,
• wie sich die Implementierung der verschiedenen Methoden im Laufe der Java-Versionen verändert hat
• und was das RandomGenerator-Interface aus Java 17 ändert.

Erfahrene Java-Entwickler:innen, die mit den verschiedenen Möglichkeiten zur Erstellung von Zufallswerten vertraut sind, können direkt zum Abschnitt „Pseudozufallszahlen in Java“ oder „Änderungen der Implementierungen im Laufe der Zeit“ springen.

Die Code-Beispiele zu diesem Artikel findest du in diesem GitHub-Repository.

Wie man Zufallszahlen generiert

Dieses Kapitel zeigt die grundlegenden Klassen und Methoden zur Generierung einer Zufallszahl in Java und was bei deren Verwendung im Hinblick auf Threadsicherheit zu beachten ist.

Java Math.random() Methode

Eine der ältesten Methoden (sie existiert seit Java 1.0), um eine zufällige Fließkommazahl zu generieren, ist der Aufruf von Math.random():

double d = Math.random();

Der Aufruf liefert eine Zufallszahl zwischen 0 und 1. Genauer gesagt: eine double-Fließkommazahl größer oder gleich 0,0 und kleiner als 1,0.

Math.random() ist laut Dokumentation threadsicher. Die Synchronisation ist allerdings von Java 1.3 bis einschließlich Java 7 fehlerhaft. Solltest du mit einer dieser Versionen arbeiten, darfst du Math.random() auf keinen Fall von verschiedenen Threads aus aufrufen.

Intern ruft Math.random() die nextDouble()-Methode einer in der Math-Klasse gehaltenen statischen Instanz der im nächsten Abschnitt besprochenen Random-Klasse auf.

Weitere Details zur internen Funktionalität und Threadsicherheit von Math.random() findest du im Kapitel über die Implementierung dieser Methode.

Java Random Klasse

Ebenfalls seit Java 1.0 dabei ist die java.util.Random-Klasse. Mit dieser kannst du wie folgt eine zufällige int-Zahl generieren:

Random random = new Random();
int i = random.nextInt();

Der Aufruf liefert eine zufällige Integer-Zahl im Bereich von Integer.MIN_VALUE (= -2³¹ = -2.147.483.648) bis Integer.MAX_VALUE (= 2³¹-1 = 2.147.483.647).

Weitere Methoden zur Generierung von Zufallswerten sind:

• nextInt(int bound) – generiert eine Zufallszahl größer oder gleich 0 und kleiner als der angegebene Grenzwert bound.
• nextInt(int origin, int bound) – generiert eine Zufallszahl größer oder gleich origin und kleiner als bound (seit Java 17, s. Abschnitt „Erzeugen einer Zufallszahl aus einem Wertebereich“).
• nextLong() – generiert einen zufälligen long-Wert.
• nextBoolean() – liefert einen zufälligen Boolean-Wert, also true oder false.
• nextFloat() – liefert eine zufällige float-Zahl größer oder gleich 0,0 und kleiner als 1,0.
• nextDouble() – liefert eine zufällige double-Zahl größer oder gleich 0,0 und kleiner als 1,0 (diese Methode wird von Math.random() aufgerufen, wie im vorherigen Abschnitt beschrieben).
• nextBytes(byte[] bytes) – füllt das angegebene byte-Array mit zufälligen Bytes.
• nextGaussian() – liefert eine normal- bzw. Gauß-verteilte Zufallszahl mit einer Standardabweichung von 1,0, d. h., dass entsprechend der Normalverteilung die Wahrscheinlichkeit einer nahe der 0 liegenden Zahl höher ist als die Wahrscheinlichkeit einer weit von der 0 entfernten Zahl.

Mit der Methode setSeed(long seed) oder dem zweiten Konstruktor Random(long seed) kannst du den sogenannten Startwert (englisch „seed“) des Zufallszahlengenerators setzen. Das ist nur für besondere Anforderungen nötig. Mehr darüber erfährst du im Kapitel Pseudozufallszahlen.

Erweiterungen von java.util.Random in Java 8

Mit der Einführung von Streams in Java 8 wurde java.util.Random um Methoden zur Erzeugung von Zufallszahlen-Streams erweitert. Die Methode Random.ints() generiert einen IntStream: einen Stream von zufälligen int-Werten.

Das folgende Beispiel gibt sieben Zufallszahlen auf der Konsole aus:

Random random = new Random();
random.ints().limit(7).forEach(System.out::println);

Die durch limit(7) gesetzte Limitierung auf sieben Elemente können wir auch in einer überladenen Variante der ints()-Methode anfordern:

Random random = new Random();
random.ints(7).forEach(System.out::println);

Zwei weitere Varianten erlauben die Angabe von Unter- und Obergrenze der generierten Werte. Das folgende Beispiel generiert sieben Zufallszahlen größer oder gleich 0 und kleiner als 1.000 – einmal durch limit() begrenzt und einmal durch den ersten Parameter der ints()-Methode.

Random random = new Random();
random.ints(0, 1000).limit(7).forEach(System.out::println);
random.ints(7, 0, 1000).forEach(System.out::println);

Jeweils entsprechende vier Varianten existieren für:

• longs() – generiert einen LongStream von Zufallszahlen
• doubles() – generiert einen DoubleStream von Zufallszahlen

Threadsicherheit von java.util.Random

java.util.Random ist threadsicher; du kannst also die Methoden eines einzigen Random-Objekts sicher aus mehreren Threads aufrufen.

Da die erzeugten Werte keine echten Zufallszahlen sind, sondern eine Zufallszahl aus der vorherigen berechnet wird (das ist stark vereinfacht ausgedrückt; genaueres findest du im Kapitel „Pseudozufallszahlen“) – und da diese Berechnung atomar erfolgen muss, ist der Aufruf der Methode mit einem gewissen Synchronisations-Overhead verbunden.

Viele gleichzeitige Aufrufe aus mehreren Threads können somit die Performance negativ beeinflussen. Im GitHub-Repo findest du das Programm RandomMultipleThreadsDemo, das den Unterschied demonstriert.

Die folgende Grafik zeigt, wie lange es auf meinem 6-Core-i7 dauert, 100 Millionen Zufallszahlen über ein geteiltes Random-Objekt zu erzeugen: bei einem Thread etwa eine Sekunde, bei sechs parallelen Threads über 50 Sekunden:

Gemessen habe ich hier den Extremfall, in dem die Threads ununterbrochen Zufallszahlen generieren, also ständig Contention verursachen (Konflikte beim Zugriff auf den gemeinsamen Status). Sollte ein Thread nur gelegentlich eine Zufallszahl generieren, tritt Contention seltener auf und ist möglicherweise gar nicht messbar.

Sofern du Thread-Contention erwartest und deine Anwendung nicht die Verwendung eines einzigen Zufallszahlengenerators erfordert (was nur in Ausnahmefällen der Fall sein dürfte), kannst du pro Thread ein separates Random-Objekt erzeugen – dann bleibt die Zeit für 100 Millionen Zufallszahlen bei etwa einer Sekunde, egal wie viele Threads parallel laufen (MultipleRandomMultipleThreadsDemo in GitHub):

Besser noch ist es, das im folgenden Abschnitt beschriebene ThreadLocalRandom einzusetzen.

Java ThreadLocalRandom Klasse

In Java 7 wurde die Klasse java.util.concurrent.ThreadLocalRandom eingeführt. Die statische Methode ThreadLocalRandom.current() liefert pro Thread einen von allen anderen Threads unabhängigen Zufallszahlengenerator. So kann es zu keiner Thread-Contention kommen, und der im vorherigen Abschnitt beschriebene Synchronisations-Overhead fällt weg.

ThreadLocalRandom.current() liefert ein ThreadLocalRandom-Objekt, welches wiederum von Random erbt und damit die gleichen Methoden bereitstellt, also z. B. nextInt():

Random random = ThreadLocalRandom.current();
int randomNumber = random.nextInt();

Das Programm ThreadLocalRandomMultipleThreadsDemo misst die Performance von ThreadLocalRandom. Das Ergebnis: Die Erzeugung von 100 Millionen Zufallszahlen dauert etwa 150 ms, egal wie viele Threads gleichzeitig laufen – ein enormer Performancegewinn im Vergleich zu Random – nicht nur bei mehreren Threads, sondern auch bei nur einem:

ThreadLocalRandom sollte also immer deine erste Wahl sein.

Es ist interessant, wie die Implementierung von Java 7 zu Java 8 grundlegend verändert wurde. Mehr dazu im Abschnitt „Implementierung von ThreadLocalRandom“.

Erzeugen einer Zufallszahl aus einem Wertebereich

Eine häufige Anforderung ist es, eine Zufallszahl aus einem bestimmten Zahlenbereich zu generieren. Ein paar Möglichkeiten hast du bereits kennengelernt:

• Random.nextInt(int bound) – generiert eine zufällige Integer-Zahl zwischen 0 und dem angegebenen Grenzwert.
• Random.ints(int randomNumberOrigin, int randomNumberBound) – generiert einen unendlichen Stream von Zufallszahlen im angegebenen Zahlenbereich.
• Random.ints(long streamSize, int randomNumberOrigin, int randomNumberBound) – generiert einen Stream der angegebenen Anzahl von Zufallszahlen im angegebenen Zahlenbereich.
• die analogen Stream-erzeugenden Methoden Random.longs() und Random.doubles().

Die obere Begrenzung bound bzw. randomNumberBound ist dabei immer exklusiv, d. h., die generierten Zufallszahlen sind immer kleiner als der angegebene Maximalwert.

Für eine einzelne Zufallszahl mit Unter- und Obergrenze gibt es seit Java 17 die Methode nextInt(int origin, int bound) – auf Random und allen anderen Generatoren, denn sie ist im Interface RandomGenerator definiert (mehr dazu im Kapitel „Zufallszahlengeneratoren seit Java 17“). ThreadLocalRandom hat diese Methode schon seit Java 7.

Auch hier ist die Untergrenze inklusiv und die Obergrenze exklusiv.

Zufallszahl zwischen 1 und 10

Eine Zufallszahl zwischen 1 und 10 (jeweils einschließlich) erhältst du also mit der Obergrenze 11:

int number = ThreadLocalRandom.current().nextInt(1, 11);

Zufallszahl zwischen 1 und 100

Analog dazu eine Zufallszahl zwischen 1 und 100:

int number = ThreadLocalRandom.current().nextInt(1, 101);

Zufallszahl zwischen 1 und 6 (Würfel)

Und so simulierst du den Wurf eines Würfels:

int roll = ThreadLocalRandom.current().nextInt(1, 7);

Zufallszahl zwischen zwei Werten

Für beliebige Grenzen gibst du die Untergrenze direkt an und die Obergrenze um eins erhöht – für den Bereich von min bis max einschließlich also:

int number = ThreadLocalRandom.current().nextInt(min, max + 1);

Wie man in Java zufällige Strings generiert

Wir haben bisher Methoden der Random-Klasse kennengelernt, mit denen wir zufällige Integer-Zahlen (nextInt), zufällige Double-Zahlen (nextDouble), zufällige Arrays (nextBytes) und zufällige Boolean-Werte (nextBoolean) erstellen können.

Manchmal benötigen wir jedoch einen zufälligen String – also einen String, der mit einer zufälligen oder vorgegebenen Anzahl zufälliger Zeichen gefüllt ist.

Wir können dazu einen StringBuilder nach und nach mit zufälligen Kleinbuchstaben füllen (diese und die folgenden Methoden findest du in der RandomUtils-Klasse in GitHub):

public static String randomLowerCaseString(int length) {
  StringBuilder sb = new StringBuilder();
  Random r = ThreadLocalRandom.current();
  for (int i = 0; i < length; i++) {
    char c = (char) ('a' + r.nextInt(26));
    sb.append(c);
  }
  return sb.toString();
}

Etwas komplizierter wird es, wenn wir den Zeichenbereich erweitern wollen, z. B. auf Großbuchstaben, Ziffern und das Leerzeichen. Dann müssen wir ein Alphabet festlegen und daraus ein zufälliges Zeichen entnehmen:

private static final String ALPHANUMERIC_WITH_SPACE_ALPHABET =
    " 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

public static String randomAlphanumericalWithSpaceString(int length) {
  return randomString(length, ALPHANUMERIC_WITH_SPACE_ALPHABET);
}

public static String randomString(int length, String alphabet) {
  StringBuilder sb = new StringBuilder();
  Random r = ThreadLocalRandom.current();
  for (int i = 0; i < length; i++) {
    int pos = r.nextInt(alphabet.length());
    char c = alphabet.charAt(pos);
    sb.append(c);
  }
  return sb.toString();
}

Seit Java 8 können wir die randomString()-Methode auch mit einem Stream implementieren:

public static String randomStringWithStream(int length, String alphabet) {
  return ThreadLocalRandom.current()
      .ints(length, 0, alphabet.length())
      .map(alphabet::charAt)
      .collect(
          StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
      .toString();
}

Alternativ kannst du auch die Klasse RandomStringUtils aus dem Open-Source-Projekt Apache Commons Lang einsetzen, z. B. RandomStringUtils.insecure().nextAlphanumeric(10). Die statischen Methoden dieser Klasse sind deprecated; seit Version 3.16 gibt es stattdessen insecure() (basiert auf ThreadLocalRandom) und secure() (basiert auf SecureRandom).

Pseudozufallszahlen in Java

Dieser Artikel hat bereits einige Male das Thema „Pseudozufallszahlen“ erwähnt. Jetzt ist es an der Zeit, das Thema genauer unter die Lupe zu nehmen.

Wie bereits kurz angesprochen, erzeugt Random keine echten Zufallszahlen. Das kann es gar nicht, denn Computer basieren auf Algorithmen, und Algorithmen sind konkrete Vorschriften, die von einer bestimmten Eingabe zu einer bestimmten Ausgabe führen.

Was stattdessen generiert wird, sind sogenannte „Pseudozufallszahlen“. Diese basieren auf einer Folge von Zahlen, die bei einem Startwert beginnt (dem sogenannten „seed“) und bei der die nächste Zahl jeweils aus der vorherigen berechnet wird.

Die Berechnungsvorschrift ist so konstruiert, dass die generierten Zahlen a) den Eindruck erwecken, zufällig zu sein und b) gleichmäßig im Zahlenraum verteilt sind (die mathematische Theorie dahinter kannst du im Wikipedia-Artikel „Kongruenzgenerator“ nachlesen).

Startwert „seed“

Der Startwert „seed“ wird beim Aufruf des Random()-Konstruktors aus System.nanoTime() generiert, XOR-verknüpft mit einem Wert, der bei jedem Konstruktoraufruf verändert wird – damit zwei kurz nacheinander erzeugte Random-Objekte nicht denselben Seed bekommen. Dadurch ist die Wahrscheinlichkeit hoch, dass bei jeder Erzeugung eines Random-Objekts die Zufallszahlen-Sequenz an einer anderen Position beginnt.

Wir können den seed-Wert aber auch selbst festlegen:

• im Konstruktor Random(long seed)
• oder mit der Methode setSeed(long seed)

Wenn wir das tun, erhalten wir immer die gleiche Folge von Zufallszahlen. Das können wir ganz einfach überprüfen: Der folgende Code (Klasse SetSeedExample in GitHub) gibt bei jedem Start – auf jedem Betriebssystem und mit jeder Java-Version – zweimal die Zahlenfolge 30, 63, 48, 84, 70 aus.

Random random = new Random(42);
for (int i = 0; i < 5; i++) {
  System.out.println(random.nextInt(100));
}

random.setSeed(42);
for (int i = 0; i < 5; i++) {
  System.out.println(random.nextInt(100));
}

Warum beginnt die Zahlenfolge nicht bei 42?

Die Antwort findest du im nächsten Abschnitt.

Ableitung von Zufallszahlen aus dem Zustand des Zufallszahlengenerators

Mit dem „seed“-Wert bestimmen wir nicht die erste Zufallszahl, sondern den Startzustand des Zufallszahlengenerators. In der Random-Klasse wird der Status in einer 48-Bit-Zahl gespeichert, die aus dem „seed“ berechnet wird.

Unpassenderweise wird der Zustand in einer Variablen gespeichert, die ebenfalls den Namen seed trägt; passender wäre der Name state gewesen. Der jeweilige Folgestatus wird über folgende Formel berechnet:

seed = (seed * 25.214.903.917 + 11) & 2⁴⁸-1

Aus diesem 48-Bit-Wert werden dann linksbündig so viele Bits entnommen, wie für den angeforderten Zufallswert benötigt werden, z. B. 32 Bit für ein int:

... oder 1 Bit für ein boolean:

Und für Zahlen, die mehr als 48 Bit benötigen, wie long oder double?

• Für ein long werden 32 Bit entnommen, dann wird der Folgezustand berechnet, dann weitere 32 Bit entnommen.
• Für ein double werden einmal 26 Bit und noch einmal 27 Bit entnommen, ergibt 53 Bit (was der Genauigkeit eines double-Werts entspricht).

Aus den 48 Bit werden nie mehr als 32 Bit entnommen. Warum ist der Status dann 48 Bit lang und nicht 32?

Der Grund ist der folgende:

Wenn der Status nur 32 Bit lang wäre, würde einer bestimmten Integer-Zufallszahl immer die gleiche Zufallszahl folgen. Das bedeutet wiederum, dass eine einzelne Zufallszahl genügen würde, um alle zukünftigen Zufallszahlen vorherzusagen.

Dadurch, dass uns bei einem 48-Bit-Status die restlichen 16 Bit verborgen bleiben, gibt es für einen 32-Bit-Wert 2¹⁶, also 65.536 verschiedene Status, in denen sich der Zufallszahlengenerator aktuell befinden könnte. Ein- und dieselbe Integer-Zufallszahl kann also 65.536 verschiedene Nachfolger haben. Das macht eine Vorhersage aus einer einzelnen Zahl unmöglich.

Wenn wir allerdings zwei aufeinanderfolgende Zufallszahlen kennen, sieht das ganz anders aus. Mehr dazu im Abschnitt „Vorhersagbarkeit von Zufallszahlen“.

Generierung von Pseudozufallszahlen in java.util.Random

Wie sieht das Ganze im Quellcode von java.util.Random aus?

Beginnen wir mit der nextInt()-Methode:

public int nextInt() {
  return next(32);
}

Die aufgerufene next()-Methode sieht wie folgt aus:

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

// ...

synchronized protected int next(int bits) {
  long nextseed = (seed * multiplier + addend) & mask;
  seed = nextseed;
  return (int)(nextseed >>> (48 - bits));
}

Zeile 8 implementiert die im vorangegangenen Abschnitt vorgestellte Formel zur Berechnung des Folgezustands.

In Zeile 10 werden die angeforderten Bits durch „right shift“ und Casting auf int extrahiert. Die folgende Grafik zeigt das für 32 Bit:

... und einmal für 1 Bit:

Die nextBoolean()-Methode muss dann nur noch prüfen, ob die so erhaltene 1-Bit-Zahl 1 oder 0 ist:

public boolean nextBoolean() {
  return next(1) != 0;
}

Die nextLong()-Methode holt sich, wie oben erwähnt, zunächst 32 Bit, schiebt diese um 32 Bit nach links und addiert eine zweite 32-Bit-Zahl:

public long nextLong() {
  return ((long)(next(32)) << 32) + next(32);
}

Die nextDouble()-Methode ist etwas komplizierter (auch hier zunächst die – etwas leichter zu lesende, da noch nicht hochoptimierte – ursprüngliche Implementierung bis Java 7):

public double nextDouble() {
  long l = ((long)(next(26)) << 27) + next(27);
  return l / (double)(1L << 53);
}

Die Methode führt folgende zwei Schritte aus:

1. Verkettung einer 26-Bit-Zufallszahl mit einer 27-Bit-Zufallszahl zu einer 53-Bit-Zahl (also eine Zahl zwischen 0 und 2⁵³-1)
2. Teilung durch 2⁵³ (eins mehr als die höchste Zahl, die in Schritt 1 generiert werden könnte)

Das ergibt dann eine Zahl >= 0,0 und < 1,0.

Warum werden für ein double nur 53 Bit verwendet und nicht 64? Der Grund: Ein double speichert seine Mantisse mit 52 Bit, hat aber 53 signifikante Bits. Eine normalisierte Fließkommazahl hat nämlich die Form 1,xxx… · 2^e – vor dem Komma steht immer eine 1. Weil das bei jeder Zahl so ist, speichert das Format diese 1 gar nicht erst, sondern nur die 52 Bit nach dem Komma. Zusammen mit der immer vorhandenen führenden 1 sind das 53 Bit Genauigkeit. Die übrigen zwölf Bit sind das Vorzeichen und der elf Bit lange Exponent. Eine detailliertere Erklärung findest du im Wikipedia-Artikel „Doppelte Genauigkeit“.

Analog verwendet die nextFloat()-Methode 24 Bit (23 gespeicherte Mantissenbits plus die führende 1) und nicht 32 (s. Wikipedia-Artikel „Einfache Genauigkeit“):

public float nextFloat() {
  return next(24) / ((float)(1 << 24));
}

Vorhersagbarkeit von Zufallszahlen

Im vorletzten Abschnitt habe ich die Behauptung aufgestellt, dass wir aus zwei aufeinanderfolgenden Pseudozufallszahlen vorhersagen können, welche weiteren Zahlen folgen. Diese Behauptung lässt sich mit einem einfachen Test überprüfen.

Das Programm RandomIntegerPairRepetitionFinder generiert für alle 2³² Integer-Zahlen jeweils alle 2¹⁶ möglichen Seed-Werte – und daraus die 2¹⁶ möglichen Nachfolger. Findet das Programm ein- und dasselbe Paar von aufeinanderfolgenden Pseudozufallszahlen mehr als einmal, gibt es dieses auf der Konsole aus.

Nach 24 Stunden wurde auf meinem Laptop keine Wiederholung gefunden. Das Programm müsste allerdings insgesamt knapp 1.200 Stunden, also 50 Tage, laufen, um alle Kombinationen zu überprüfen. So viel Zeit habe ich nicht, daher kann ich meine Behauptung nicht beweisen.

Trotzdem können wir ein Programm schreiben, das aus zwei gegebenen Zufallszahlen alle weiteren vorhersagt. Solch ein Programm kann erkennen, ob für die Eingabe nur eine mögliche Sequenz existiert – und um eine dritte Zahl bitten, sollten zwei nicht ausreichen.

Wie man die nächste Zufallszahl in Java vorhersagt

Wenn zwei durch Random.nextInt() erzeugte Zufallszahlen gegeben sind, lassen sich die weiteren Zufallszahlen leicht vorhersagen.

Dazu bestimmen wir für die erste gegebene Zahl die 2¹⁶ möglichen Seed-Werte, generieren daraus die jeweilige Folgezahl und prüfen, ob diese mit der zweiten gegebenen Zahl übereinstimmt. Ist das der Fall, können wir ausgehend vom so ermittelten Seed-Wert alle weiteren Zufallszahlen berechnen.

Den vollständigen Code dazu findest du in der Klasse RandomIntegerPredictor.

Der folgende Code zeigt die Methode, die den Seed-Wert bestimmt. Ich habe sie für den Abdruck in diesem Artikel dahingehend vereinfacht, dass sie nur zwei Eingabezahlen verwendet. Der Code in der verlinkten Klasse kann auch eine längere Eingabefolge verarbeiten.

private static final int NUMBER_OF_POSSIBLE_SEEDS = 1 << 16;

private static final long MULTIPLIER = 0x5DEECE66DL;
private static final long ADDEND = 0xBL;
private static final long MASK = (1L << 48) - 1;

// ...

private long getSeedMatchingForSequence() {
  long firstNumberSeedBase = Integer.toUnsignedLong(givenNumbers[0]) << 16;

  for (int noise = 0; noise < NUMBER_OF_POSSIBLE_SEEDS; noise++) {
    long seed = firstNumberSeedBase | noise;
    long nextSeed = getNextSeed(seed);
    int nextInt = (int) (nextSeed >>> 16);
    if (nextInt == givenNumbers[1]) {
      return seed;
    }
  }

  throw new IllegalArgumentException(
      "Found no matching seed; please verify your input sequence.");
}

private long getNextSeed(long seed) {
  return (seed * MULTIPLIER + ADDEND) & MASK;
}

Aus dem so erhaltenen Seed-Wert können wir die weitere Zahlenfolge ableiten:

public int[] predict(int numberOfPredictions) {
  long seed = getSeedMatchingForSequence();

  // Skip the given numbers
  for (int i = 0; i < givenNumbers.length; i++) {
    seed = getNextSeed(seed);
  }

  // Get the predictions
  int[] predictions = new int[numberOfPredictions];
  for (int i = 0; i < numberOfPredictions; i++) {
    predictions[i] = (int) (seed >>> 16);
    seed = getNextSeed(seed);
  }

  return predictions;
}

Im GitHub-Repo befindet sich eine Demo, RandomIntegerPredictorDemo, die zwei Zufallszahlen ausgibt, dann die nächsten 10 Zufallszahlen vorhersagen lässt und schließlich 10 weitere Zufallszahlen ausgibt. Die Vorhersage stimmt:

Two random numbers:
-1,179,305,299
435,136,901

Predicting 10 random numbers:
-2,139,482,012
1,388,148,251
1,134,856,645
-1,205,820,716
182,240,689
...

Next *actual* random numbers:
-2,139,482,012
1,388,148,251
1,134,856,645
-1,205,820,716
182,240,689
...

Im Repo befindet sich außerdem der Kommandozeilen-Runner RandomIntegerPredictorRunner, den du (nachdem du den Code compiliert hast) wie folgt aufrufen kannst:

$ java eu.happycoders.random.predictor.RandomIntegerPredictorRunner 5 999571443 25208007
Given numbers: [999571443, 25208007]
Predicting 5 random numbers...
-1,315,941,039
136,476,741
1,077,533,899
-211,240,302
143,354,061

Der erste Parameter, 5, gibt an, wie viele Folgezahlen angezeigt werden sollen; die folgenden Parameter sind die bekannte Zufallszahlenfolge. Ausgegeben wird die Vorhersage der folgenden Zufallszahlen.

Java SecureRandom Klasse

Im letzten Abschnitt des vorherigen Kapitels hast du gesehen, wie man aus nur zwei aufeinanderfolgenden Zufallszahlen alle weiteren vorhersagen kann.

Für gewisse Anforderungen (z. B. Kryptografie) ist diese Vorhersagbarkeit nicht akzeptabel. In solchen Fällen benötigen wir einen „sicheren“ Zufallszahlengenerator.

Bereits seit Java 1.1 gibt es die Klasse java.security.SecureRandom. Diese generiert „kryptografisch starke“ Zufallszahlen, wie sie in RFC 4086 „Randomness Requirements for Security“ definiert sind.

„Kryptografisch stark“ kann auf eine der folgenden zwei Arten (oder eine Kombination aus beiden) implementiert werden:

• Eine deterministische Folge wie bei Random, allerdings mit wesentlich größerem „Noise“ (die Bits des Seeds, die nicht in die generierte Zufallszahl eingehen), so dass ein Reverse Engineering des Seeds aus einer gegebenen Sequenz mit heutiger Hardware praktisch unmöglich wird.
• Echte Zufallszahlen, generiert durch spezielle Hardware, die z. B. radioaktive Zerfallsvorgänge misst.

Verschiedene Arten von sicheren Zufallszahlengeneratoren können über das Java Service Provider Interface (SPI) zur Verfügung gestellt und zur Laufzeit über SecureRandom.getInstance(String algorithm) und einige überladene Varianten dieser Methode ausgewählt werden.

Der Konstruktor von SecureRandom liefert eine Standard-Implementierung. SecureRandom erbt von Random und stellt somit die gleichen Methoden zur Verfügung. Das folgende Beispiel zeigt, wie du eine stark zufällige Fließkommazahl generieren kannst:

SecureRandom secureRandom = new SecureRandom();
double strongRandomNumber = secureRandom.nextDouble();

Weitere Details findest du im SecureRandom-JavaDoc.

Änderungen der Implementierungen im Laufe der Zeit

In diesem Abschnitt erfährst du, wie die in diesem Artikel vorgestellten Methoden zur Generierung von Zufallszahlen implementiert sind und wie (und warum) die Implementierungen im Laufe der Java-Versionen überarbeitet wurden.

Die folgende Tabelle fasst zusammen, welche Java-Version was geändert hat; die Details folgen in den Abschnitten darunter.

Java-Version	Änderung
1.0 / 1.1	Math.random() und Random.next() sind synchronized.
1.3	Math.random() wechselt auf Double-Checked Locking – und ist damit nicht mehr threadsicher.
1.4	Random.next() verwaltet den Status in einem sun.misc.AtomicLong per Compare-and-set.
5	Random.next() wechselt auf java.util.concurrent.atomic.AtomicLong; SecureRandom.getAlgorithm() kommt hinzu.
6	Das AtomicLong-Feld in Random wird final.
7	ThreadLocalRandom kommt hinzu – eine Instanz pro Thread.
8	Math.random() wechselt auf das Initialization-on-Demand-Holder-Pattern; Random.nextDouble() multipliziert statt zu dividieren; ThreadLocalRandom wird neu geschrieben und speichert den Status im Thread-Objekt; SecureRandom.getInstanceStrong() kommt hinzu.
9	SecureRandom bekommt mit JEP 273 parametrisierbare DRBG-Generatoren.
17	Alle Generatoren implementieren das neue Interface RandomGenerator; ThreadLocalRandom mischt die Thread-ID in den Seed.
19	Random.from(RandomGenerator) kommt hinzu; ThreadLocalRandom wird final und verwendet threadId().
20 bis 27	Keine Änderungen an den hier gezeigten Implementierungen.

An Math.random() und Random hat sich seit Java 8 nichts mehr geändert; alles danach betrifft ThreadLocalRandom-Interna, SecureRandom-Parameter und das gemeinsame Interface.

Implementierung von Math.random()

Die statische Methode Math.random() ruft intern auf einer statischen Instanz der Random-Klasse die nextDouble()-Methode auf. Der Code für die Erzeugung des statischen Random-Objekts wurde mehrmals geändert.

In Java 1.0 wurde die Math.random()-Methode einfach mit dem synchronized-Keyword versehen. Dies war korrekt, führte aber zu einem hohen Synchronisations-Overhead:

public static synchronized double random() {
  if (randomNumberGenerator == null)
    randomNumberGenerator = new Random();
  return randomNumberGenerator.nextDouble();
}

In Java 1.3 wurde auf das „Double-Checked Locking“-Pattern umgestellt:

// !!! DON'T DO THIS - NOT THREAD-SAFE !!!

public static double random() {
  if (randomNumberGenerator == null) initRNG();
  return randomNumberGenerator.nextDouble();
}

private static synchronized void initRNG() {
  if (randomNumberGenerator == null)
    randomNumberGenerator = new Random();
}

Diese vermeintlich performantere Implementierung ist nicht threadsicher! Aufgrund des unsynchronisierten lesenden Zugriffs auf randomNumberGenerator in der random()-Methode könnte ein Thread an dieser Stelle ein unvollständig initialisiertes Objekt sehen. Eine ausführliche Erklärung findest du im zuvor verlinkten Artikel.

Behoben wurde das erst in Java 8 – durch die Umstellung auf das „Initialization on Demand Holder“-Pattern:

private static final class RandomNumberGeneratorHolder {
  static final Random randomNumberGenerator = new Random();
}

public static double random() {
  return RandomNumberGeneratorHolder.randomNumberGenerator.nextDouble();
}

Bei diesem Pattern wird randomNumberGenerator erst dann erzeugt, wenn es benötigt wird; gleichzeitig garantiert die JVM die korrekte Synchronisierung beim Initialisieren der RandomNumberGeneratorHolder-Klasse.

Für diese Änderung gibt es keinen JEP; sie wird im Bug-Tracker unter JDK-6470700 aufgeführt – gemeldet wurde der Fehler bereits 2006.

An dieser Implementierung hat sich bis Java 27 nichts weiter geändert.

Implementierung von java.util.Random

Im Kapitel „Pseudozufallszahlen in Java“ habe ich die grundsätzliche Implementierung der Random-Klasse anhand deren ursprünglichem Quellcode erklärt. Die öffentlichen Methoden rufen intern die Methode next(int bits) auf.

Deren Synchronisation erfolgte ursprünglich über das synchronized-Keyword, das zwar einfach einzusetzen ist, aber – insbesondere bis einschließlich Java 5 – einen hohen Performance-Overhead verursachte.

Hier noch einmal der ursprüngliche Code (die next()-Methode gibt es seit Java 1.1):

private long seed;

synchronized protected int next(int bits) {
  long nextseed = (seed * multiplier + addend) & mask;
  seed = nextseed;
  return (int)(nextseed >>> (48 - bits));
}

In Java 1.4 wurde der Seed-Wert in einem (damals noch internen) sun.misc.AtomicLong gespeichert und mit attemptUpdate() geändert. Diese Methode arbeitet mit Compare-and-set, also optimistischem Locking:

import sun.misc.AtomicLong;

private AtomicLong seed;

protected int next(int bits) {
  long oldseed, nextseed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
  } while (!seed.attemptUpdate(oldseed, nextseed));
  return (int)(nextseed >>> (48 - bits));
}

In Java 5 wurde auf das neue, offizielle java.util.concurrent.atomic.AtomicLong und dessen compareAndSet()-Methode umgestellt:

import java.util.concurrent.atomic.AtomicLong;

private AtomicLong seed;

protected int next(int bits) {
  long oldseed, nextseed;
  AtomicLong seed = this.seed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
  } while (!seed.compareAndSet(oldseed, nextseed));
  return (int)(nextseed >>> (48 - bits));
}

In Java 6 wurde die AtomicLong-Variable final gemacht. Bis Java 27 wurde die Implementierung der next()-Methode nicht noch einmal verändert.

Eine weitere Änderung gab es an der nextDouble()-Methode. Zur Erinnerung – so sah sie ursprünglich aus:

public double nextDouble() {
  long l = ((long)(next(26)) << 27) + next(27);
  return l / (double)(1L << 53);
}

Da Division deutlich teurer ist als Multiplikation, wurde in Java 8 der Wert 1/2⁵³ in eine Konstante extrahiert, und seither wird mit dieser multipliziert:

private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)

public double nextDouble() {
  return (((long)(next(26)) << 27) + next(27)) * DOUBLE_UNIT;
}

Die Funktionalität der Random-Klasse ist also seit Java 1.0 unverändert geblieben; bis Java 8 hat sich allerdings deren Performance kontinuierlich verbessert.

Implementierung von java.util.concurrent.ThreadLocalRandom

In Java 7 liefert die Methode ThreadLocalRandom.current() pro Thread eine separate Instanz von ThreadLocalRandom:

private static final ThreadLocal<ThreadLocalRandom> localRandom =
  new ThreadLocal<ThreadLocalRandom>() {
    protected ThreadLocalRandom initialValue() {
      return new ThreadLocalRandom();
    }
};

public static ThreadLocalRandom current() {
  return localRandom.get();
}

ThreadLocalRandom erbt von Random, das den Status in einem AtomicLong speichert. Da dessen Threadsicherheit (und der damit einhergehende Overhead) in ThreadLocalRandom nicht benötigt werden, speichert ThreadLocalRandom den Status stattdessen in einem eigenen Feld rnd, auf das es ohne Synchronisation zugreift:

In Java 8 wurde ThreadLocalRandom komplett neu geschrieben. Statt separate Instanzen pro Thread bereitzustellen, liefert ThreadLocalRandom.current() für alle Threads die gleiche, statische Instanz von ThreadLocalRandom zurück.

Damit nun nicht alle Threads wieder auf ein- und denselben Status zugreifen (was dann wieder synchronisiert werden müsste), wird dieser ab Java 8 in der Variablen threadLocalRandomSeed des Thread-Objekts des aktuellen Threads gespeichert:

Für diese Änderung gibt es keinen JEP; sie wird im Bug-Tracker unter JDK-8005926 aufgeführt.

Auf dieses Feld greift ThreadLocalRandom per Unsafe zu – in Java 8 noch sun.misc.Unsafe, seit Java 9 jdk.internal.misc.Unsafe. So sieht der Code in Java 27 aus:

private static final Unsafe U = Unsafe.getUnsafe();
private static final long SEED
  = U.objectFieldOffset(Thread.class, "threadLocalRandomSeed");

// ...

final long nextSeed() {
  Thread t; long r; // read and update per-thread seed
  U.putLong(t = Thread.currentThread(), SEED,
            r = U.getLong(t, SEED) + (t.threadId() << 1) + GOLDEN_GAMMA);
  return r;
}

Die Formel hat sich dabei zweimal geändert: In Java 8 bis 16 wurde nur die Konstante GAMMA addiert. Seit Java 17 fließt zusätzlich die Thread-ID ein – zunächst über getId(), seit Java 19 über threadId(), da getId() seitdem deprecated ist.

Dass verschiedene Threads in Java 7 unterschiedliche und in Java 8 die gleiche ThreadLocalRandom-Instanz verwenden, kannst du mit folgendem Beispiel-Code leicht zeigen:

for (int i = 0; i < 3; i++) {
  new Thread() {
    @Override
    public void run() {
      System.out.println(
          "ThreadLocalRandom instance: " + ThreadLocalRandom.current());
    }
  }.start();
}

Wenn du den Code unter Java 7 laufen lässt, siehst du drei unterschiedliche Instanzen; unter Java 8 wird dir dreimal die gleiche Instanz angezeigt.

Implementierung von java.security.SecureRandom

SecureRandom ist selbst keine Implementierung eines sicheren Zufallszahlengenerators. Konkrete Implementierungen werden über das Service Provider Interface (SPI) zur Verfügung gestellt. Auf diese einzugehen würde den Rahmen dieses Artikels sprengen.

Erwähnenswert sind drei Erweiterungen an SecureRandom selbst:

• In Java 1.5 wurde die Methode getAlgorithm() hinzugefügt, die den Namen des implementierten Algorithmus liefert.
• In Java 8 kam die Methode getInstanceStrong() hinzu, die die Implementierung eines besonders starken Algorithmus liefert, wie er z. B. für RSA-Schlüsselpaare empfohlen wird.
• In Java 9 kamen mit JEP 273 („DRBG-Based SecureRandom Implementations“) das Interface SecureRandomParameters und darauf aufbauende Methoden hinzu: getInstance(String algorithm, SecureRandomParameters params), getParameters(), nextBytes(byte[] bytes, SecureRandomParameters params) und reseed().

Zufallszahlengeneratoren seit Java 17: RandomGenerator

Bis Java 16 hatte SplittableRandom zwar fast dieselben Methoden wie Random, ThreadLocalRandom und SecureRandom, aber keinen gemeinsamen Typ mit ihnen. Wer zwischen den Generatoren wechseln wollte, musste den Code anfassen.

Das hat Java 17 mit JEP 356 („Enhanced Pseudo-Random Number Generators“) geändert: Alle vier Klassen implementieren seitdem das Interface java.util.random.RandomGenerator, in dem die gemeinsamen Methoden wie nextInt(), nextDouble() und ints() definiert sind. Ich empfehle, im eigenen Code diesen Typ zu verwenden – dann tauschst du den Algorithmus an genau einer Stelle.

Das Interface bringt Methoden mit, die es auf Random vorher nicht gab:

• nextInt(int origin, int bound), nextLong(long origin, long bound), nextFloat(float origin, float bound) und nextDouble(double origin, double bound) – Zufallszahl mit Unter- und Obergrenze,
• nextLong(long bound), nextFloat(float bound) und nextDouble(double bound) – Zufallszahl mit Obergrenze,
• nextGaussian(double mean, double stddev) – normalverteilte Zufallszahl mit wählbarem Mittelwert und wählbarer Standardabweichung,
• nextExponential() – exponentialverteilte Zufallszahl.

Dazu kommen neue Algorithmen der sogenannten „LXM“-Familie. Der Name steht für die drei Bausteine: ein linearer Kongruenzgenerator (L) wie in Random, ein Xor-basierter Generator (X) aus der Xorshift-Familie und eine Mischfunktion (M), die die Ergebnisse beider verknüpft. Die Zahlen im Namen sind die Zustandsbits der beiden Teilgeneratoren – L64X128MixRandom hat also einen 64-Bit-Kongruenzgenerator und einen 128-Bit-Xor-Generator (Details in der Paketbeschreibung von java.util.random).

Du wählst einen Algorithmus über seinen Namen aus:

RandomGenerator generator = RandomGenerator.of("L64X128MixRandom");
int roll = generator.nextInt(1, 7);

Wenn dir der Algorithmus egal ist, nimmst du RandomGenerator.getDefault() – in Java 17 bis 27 liefert diese Methode einen L32X64MixRandom. Laut JavaDoc ist aber ausdrücklich nicht garantiert, dass das so bleibt: Mit einer neuen Java-Version kann getDefault() einen anderen Algorithmus liefern. Wer sich auf den Algorithmus verlassen muss, nennt ihn beim Namen.

Zwei kleinere Ergänzungen kamen später:

• Seit Java 19 wandelt Random.from(RandomGenerator) einen beliebigen Generator in ein Random-Objekt um – für APIs, die diesen Typ verlangen (JDK-8279598).
• Seit Java 19 ist ThreadLocalRandom final (JDK-8283688) – Unterklassen gab es ohnehin nie, denn der Konstruktor ist privat.

Die vollständige Interface-Hierarchie (StreamableGenerator, SplittableGenerator, JumpableGenerator und weitere) samt Klassendiagrammen vor und nach Java 17 findest du im Artikel über Java 17.

Fazit

Dieser Artikel hat damit begonnen, die verschiedenen Möglichkeiten aufzuzeigen, über die in Java Zufallszahlen generiert werden können.

Danach hast du erfahren, warum Zufallszahlen eigentlich Pseudozufallszahlen sind, wie man eine Folge von Zufallszahlen berechnet und wie man aus zwei gegebenen Zufallszahlen alle zukünftigen Zufallszahlen vorhersagen kann.

Der Artikel hat mit einer Reise durch die Java-Versionen abgeschlossen und darin gezeigt, wie (und warum) die Implementierungen der zuvor gezeigten Methoden im Laufe der Zeit verändert wurden.

Meine Empfehlung daraus: ThreadLocalRandom für alles, was nur zufällig aussehen muss; SecureRandom für alles, was ein Angreifer nicht erraten darf – Tokens, Passwörter, Schlüssel; und seit Java 17 RandomGenerator als Typ im eigenen Code, damit der Algorithmus austauschbar bleibt.