An introduction to the methods and principles of java.util.Random implementation

The class java.util.Random in the Java utility class library provides methods for generating various types of random numbers. The following article mainly introduces relevant information about the implementation principle of java.util.Random. The article adopts The sample code is introduced in great detail, friends in need can refer to it.

Overview

java.util.Random can generate random numbers of types such as int, long, float, double and Goussian. This is also the biggest difference between it and the method Random() in java.lang.Math, which only generates double-type random numbers.

Instances of this class are used to generate a stream of pseudo-random numbers. This class uses a 48-bit seed that is modified by a linear congruential formula. If two instances of Random are created with the same seed, they will generate and return the same sequence of numbers by completing the same sequence of method calls on each instance.

Example

##

public class RandomTest {
 public static void main(String[] args) {
 testRandom();
 System.out.println("---------------------");
 testRandom();
 System.out.println("---------------------");
 testRandom();
 }
 
 public static void testRandom(){
 Random random = new Random(1);
 for(int i=0; i<5; i++){
  System.out.print(random.nextInt()+"\t");
 }
 System.out.println("");
 }
}

Output result:

It is found from the results that as long as the seeds are the same, the sequence of random numbers obtained is consistent. It is an implementation of pseudo-random numbers, not true random numbers.

Random source code analysis

Random class structure

##

class Random implements java.io.Serializable {
 private final AtomicLong seed;

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

Construction method with parameters

public Random(long seed) {
 if (getClass() == Random.class)
  this.seed = new AtomicLong(initialScramble(seed));
 else {
  // subclass might have overriden setSeed
  this.seed = new AtomicLong();
  setSeed(seed);
 }
}

private static long initialScramble(long seed) {
 return (seed ^ multiplier) & mask;
}

Generate random numbers by passing in a seed. Through the above example, we found that the random number sequence generated by the same seed is the same. If you want to generate a different sequence every time you use it, sequence, then you can only pass in a different seed each time.

No-parameter construction method

public Random() {
 this(seedUniquifier() ^ System.nanoTime());
 }
private static long seedUniquifier() {
 // L'Ecuyer, "Tables of Linear Congruential Generators of
 // Different Sizes and Good Lattice Structure", 1999
 for (;;) {
  long current = seedUniquifier.get();
  long next = current * 181783497276652981L;
  if (seedUniquifier.compareAndSet(current, next))
   return next;
 }
}

Found through the source code, the parameter-free construction method, which helps We automatically generate a seed and use the CAS spin method to ensure that the seed obtained is different each time, thus ensuring that the random sequence obtained each time

new Random()

is inconsistent.

nextInt() method: Get int random number

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

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));
}

We can find from the code, As long as the seed is determined, the number generated each time is generated using a fixed algorithm, so as long as the seed is determined, the sequence generated each time is fixed.

Every time the seed is updated, CAS is used to update it. If it is in a high-concurrency environment, performance is a problem.

Security issuesJust imagine, if this is a lottery platform, as long as the seed is determined, the sequence generated will be the same every time . In this way, this loophole can be used to predict the numbers of the next lottery draw, which can easily be exploited by some people.

jdk recommends that you try to use SecureRandom to generate random numbers.

SecureRandomSecureRandom is a strong random number generator. The main application scenarios are: data numbers for security purposes, such as generating secrets. Key or session ID. In the above article "Security of Pseudo-Random Numbers", the security issues of weak random number generators have been revealed to you. Using a strong random number generator like SecureRandom will greatly Reduce the risk of things going wrong.

There are two important factors to generate high-strength random numbers: seed and algorithm. There can be many algorithms, and usually how to choose the seed is a very critical factor. For example, Random, its seed is System.currentTimeMillis(), so its random numbers are predictable and weak pseudo-random numbers.

Ideas for generating strong pseudo-random numbers: collect various computer information, keyboard input time, memory usage status, hard disk free space, IO delay, number of processes, number of threads and other information, CPU clock, to get an approximately random number The seeds mainly achieve unpredictability.

To put it simply, use an encryption algorithm to generate a very long random seed, so that you cannot guess the seed, and therefore cannot deduce the random sequence number.

Random performance issuesFrom the Random source code we found that CAS is used to update the seed every time a random number is obtained. value. In this way, there will be a large number of CAS retries in a high-concurrency environment, resulting in performance degradation. At this time, it is recommended that you use the ThreadLocalRandom class to generate random numbers.

ThreadLocalRandom implementation principle

Thread class

There is a threadLocalRandomSeed property in the Thread class.

ThreadLocalRandom structure

The SEED variable is the offset of threadLocalRandomSeed in the Thread object.

ThreadLocalRandom.nextSeed() method

From this method, we find that the seed value of each thread is stored in In the threadLocalRandomSeed property of the Thread object.

Conclusion

Because the seeds in ThreadLocalRandom are stored in Thread objects, CAS will not be used to ensure high concurrency when acquiring Random objects. The values ​​obtained each time are inconsistent.
Each thread maintains its own seed. When each thread needs to obtain a random number, it obtains the seed of the current thread from the current Thread object and obtains the random number. The performance is greatly improved.

The above is the detailed content of An introduction to the methods and principles of java.util.Random implementation. For more information, please follow other related articles on the PHP Chinese website!