Zufallszahlen in Java

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
• und wie sich die Implementierung der verschiedenen Methoden im Laufe der Java-Versionen verändert hat.

Erfahrene Java-Entwickler, 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();Code-Sprache: Java (java)

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();Code-Sprache: Java (java)

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.
• nextLong() – generiert einen zufälligen long-Wert.
• nextBoolean() – liefert einen zufälligen Boolean-Wert, also true oder false.
• nextFloat() – liefert eine zufällig float-Zahl größer oder gleich 0,0 und kleiner als 1,0.
• nextDouble() – liefert eine zufällig 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);Code-Sprache: Java (java)

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);Code-Sprache: Java (java)

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 limits() 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);Code-Sprache: Java (java)

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 quasi 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 einsetzen.

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();Code-Sprache: Java (java)

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.)

Wir können also

• entweder eine einzelne Zufallszahl zwischen 0 und einer Obergrenze erzeugen
• oder einen Stream von Zufallszahlen, der von Unter- und Obergrenze eingeschränkt ist.

Wollen wir jedoch eine einzelne Zufallszahl aus einem Zahlenbereich generieren, dessen Untergrenze nicht die 0 ist, können wir uns keiner vorhandenen JDK-Funktion bedienen, sondern müssen einen Umweg gehen. Hier ein paar Beispiele:

Zufallszahl zwischen 1 und 10

Da wir nur die Obergrenze von Zufallszahlen definieren können, erstellen wir eine Zahl zwischen 0 und 9 und addieren eine 1:

Random random = ThreadLocalRandom.current();
int number = 1 + random.nextInt(9);Code-Sprache: Java (java)

Achtung: Obergrenzen sind immer exklusiv, d. h. der Code liefert maximal eine 9. Um die 10 einzuschließen, also Zahlen kleiner oder gleich 10 zu erhalten, müssen wir den Code wie folgt abwandeln:

Random random = ThreadLocalRandom.current();
int number = 1 + random.nextInt(10);Code-Sprache: Java (java)

Zufallszahl zwischen 1 und 100

Um eine Zufallszahl zwischen 1 und 100 zu generieren, generieren wir eine Zahl zwischen 0 und 99 und addieren 1:

Random random = ThreadLocalRandom.current();
int number = 1 + random.nextInt(99);Code-Sprache: Java (java)

Analog zum vorherigen Beispiel müssen wir nextInt(100) schreiben, wenn wir die 100 einschließen wollen.

Zufallszahl zwischen zwei Werten

Wenn wir häufiger eine Zufallszahl zwischen zwei vorgegebenen Werten benötigen, sollten wir die Erzeugung in eine Hilfsmethode auslagern:

public class RandomUtils
  public static int nextInt(Random random, int origin, int bound) {
    if (origin >= bound) {
      throw new IllegalArgumentException();
    }
    return origin + random.nextInt(bound - origin);
  }
}Code-Sprache: Java (java)

Diese können wir dann bspw. wie folgt aufrufen, um eine Zufallszahl zwischen 1 und 6 inklusive zu generieren:

Random random = ThreadLocalRandom.current();
int randomNumberFrom1To6 = RandomUtils.nextInt(random, 1, 7);Code-Sprache: Java (java)

So kannst du z. B. den Wurf eines Würfels simulieren.

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();
}Code-Sprache: Java (java)

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();
}Code-Sprache: Java (java)

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();
}Code-Sprache: Java (java)

Alternativ kannst du auch eine der zahlreichen Methoden der Klasse RandomStringUtils aus dem Open Source Projekt Apache Commons Lang einsetzen.

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 der Systemzeit generiert. 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));
}Code-Sprache: Java (java)

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 angeforderte 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);
}Code-Sprache: Java (java)

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

(Ich habe die ursprüngliche Implementierung bis Java 1.3 abgedruckt, da diese am einfachsten zu verstehen ist. Die aktuelle – optimierte, aber funktionell gleiche – Implementierung findest du weiter unten im Kapitel "Änderungen der Implementierungen im Laufe der Zeit".)

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));
}
Code-Sprache: Java (java)

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;
}Code-Sprache: Java (java)

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);
}Code-Sprache: Java (java)

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);
}Code-Sprache: Java (java)

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 ist, dass in Fließkommazahlen mit doppelter Genauigkeit 53 Bit für Vorzeichen und Mantisse verwendet werden und 11 Bit für den Exponenten. Eine detailliertere Erklärung findest du im Wikipedia-Artikel "Doppelte Genauigkeit".

Analog verwendet die nextFloat()-Methode 24 Bit und nicht 32 (s. Wikipedia-Artikel "Einfache Genauigkeit"):

public float nextFloat() {
    return next(24) / ((float)(1 << 24));
}Code-Sprache: Java (java)

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, dass 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 relativ leicht die weiteren Zufallszahlen 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 berechen.

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;
}Code-Sprache: Java (java)

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;
}Code-Sprache: Java (java)

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
...Code-Sprache: Klartext (plaintext)

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
Code-Sprache: Klartext (plaintext)

Der ersten 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 auseinanderfolgenden Zufallszahlen alle weiteren vorhersagen kann.

Für gewisse Anforderungen (z. B. Kryptographie) ist diese Vorhersagberkeit 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 "kryptographisch starke" Zufallszahlen, wie sie in RFC 1750 "Randomness Recommendations 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 wesentich 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();Code-Sprache: Java (java)

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.

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 Synchronisation-Overhead:

public static synchronized double random() {
    if (randomNumberGenerator == null)
        randomNumberGenerator = new Random();
    return randomNumberGenerator.nextDouble();
}Code-Sprache: Java (java)

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();
}Code-Sprache: Java (java)

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 oben verlinkten Wikipedia-Artikel.

Erst in Java 8 wurde dieser Fehler erkannt und auf das "Initialization on Demand Holder"-Pattern umgestellt:

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

public static double random() {
    return RandomNumberGeneratorHolder.randomNumberGenerator.nextDouble();
}Code-Sprache: Java (java)

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.

An dieser Implementierung hat sich bis Java 18 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 Java-1.0-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 Code aus Java 1.0:

private long seed;

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

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));
}Code-Sprache: Java (java)

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));
}Code-Sprache: Java (java)

In Java 6 wurde die AtomicLong-Variable final gemacht. Bis Java 18 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);
}Code-Sprache: Java (java)

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;
}Code-Sprache: Java (java)

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();
}Code-Sprache: Java (java)

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 neugeschrieben. Statt separate Instanzen pro Thread bereitzustellen, liefert ThreadLocalRandom.current() für alle Threads die gleiche, statische Intanz 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-Objekt des aktuellen Threads gespeichert:

Auf dieses Feld wird von ThreadLocalRandom aus per jdk.internal.misc.Unsafe zugegriffen:

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.getId() << 1) + GOLDEN_GAMMA);
    return r;
}
Code-Sprache: Java (java)

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();
}Code-Sprache: Java (java)

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.secure.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 zwei 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 Algorihmus liefert, wie er z. B. für RSA-Schlüsselpaare empfohlen wird.

"Enhanced Pseudo-Random Number Generators" in Java 17

In Java 17 wurden die Zufallszahlengeneratoren im JDK um eine Interface-Hierarchie erweitert, die zukünftige Erweiterungen ermöglich soll. Details dazu 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.

Wenn dir der Artikel gefallen hat, hinterlasse gerne einen Kommentar und teile den Artikel über einen der Share-Buttons am Ende. Wenn du über neue Artikel auf HappyCoders.eu informiert werden möchtest, klicke hier, um dich für den HappyCoders-Newsletter anzumelden.