[Java] Java实现高效随机数算法的示例代码

• 生成一个足够大的id池（其实就是需要多少就生成多少）
  
• 对id池中的数字进行随机排序
  
• 依次消费id池中的数字
  

import java.util.random;
 
/**
 * mt19937的java实现
 */
public class mtrandom extends random {
  
  // constants used in the original c implementation
  private final static int upper_mask = 0x80000000;
  private final static int lower_mask = 0x7fffffff;
 
  private final static int n = 624;
  private final static int m = 397;
  private final static int magic[] = { 0x0, 0x9908b0df };
  private final static int magic_factor1 = 1812433253;
  private final static int magic_factor2 = 1664525;
  private final static int magic_factor3 = 1566083941;
  private final static int magic_mask1  = 0x9d2c5680;
  private final static int magic_mask2  = 0xefc60000;
  private final static int magic_seed  = 19650218;
  private final static long default_seed = 5489l;
 
  // internal state
  private transient int[] mt;
  private transient int mti;
  private transient boolean compat = false;
 
  // temporary buffer used during setseed(long)
  private transient int[] ibuf;
 
  /**
   * the default constructor for an instance of mtrandom. this invokes
   * the no-argument constructor for java.util.random which will result
   * in the class being initialised with a seed value obtained by calling
   * system.currenttimemillis().
   */
  public mtrandom() { }
 
  /**
   * this version of the constructor can be used to implement identical
   * behaviour to the original c code version of this algorithm including
   * exactly replicating the case where the seed value had not been set
   * prior to calling genrand_int32.
   * <p>
   * if the compatibility flag is set to true, then the algorithm will be
   * seeded with the same default value as was used in the original c
   * code. furthermore the setseed() method, which must take a 64 bit
   * long value, will be limited to using only the lower 32 bits of the
   * seed to facilitate seamless migration of existing c code into java
   * where identical behaviour is required.
   * <p>
   * whilst useful for ensuring backwards compatibility, it is advised
   * that this feature not be used unless specifically required, due to
   * the reduction in strength of the seed value.
   *
   * @param compatible compatibility flag for replicating original
   * behaviour.
   */
  public mtrandom(boolean compatible) {
  super(0l);
  compat = compatible;
  setseed(compat?default_seed:system.currenttimemillis());
  }
 
  /**
   * this version of the constructor simply initialises the class with
   * the given 64 bit seed value. for a better random number sequence
   * this seed value should contain as much entropy as possible.
   *
   * @param seed the seed value with which to initialise this class.
   */
  public mtrandom(long seed) {
  super(seed);
  }
 
  /**
   * this version of the constructor initialises the class with the
   * given byte array. all the data will be used to initialise this
   * instance.
   *
   * @param buf the non-empty byte array of seed information.
   * @throws nullpointerexception if the buffer is null.
   * @throws illegalargumentexception if the buffer has zero length.
   */
  public mtrandom(byte[] buf) {
  super(0l);
  setseed(buf);
  }
 
  /**
   * this version of the constructor initialises the class with the
   * given integer array. all the data will be used to initialise
   * this instance.
   *
   * @param buf the non-empty integer array of seed information.
   * @throws nullpointerexception if the buffer is null.
   * @throws illegalargumentexception if the buffer has zero length.
   */
  public mtrandom(int[] buf) {
  super(0l);
  setseed(buf);
  }
 
  // initializes mt[n] with a simple integer seed. this method is
  // required as part of the mersenne twister algorithm but need
  // not be made public.
  private final void setseed(int seed) {
 
  // annoying runtime check for initialisation of internal data
  // caused by java.util.random invoking setseed() during init.
  // this is unavoidable because no fields in our instance will
  // have been initialised at this point, not even if the code
  // were placed at the declaration of the member variable.
  if (mt == null) mt = new int[n];
 
  // ---- begin mersenne twister algorithm ----
  mt[0] = seed;
  for (mti = 1; mti < n; mti++) {
    mt[mti] = (magic_factor1 * (mt[mti-1] ^ (mt[mti-1] >>> 30)) + mti);
  }
  // ---- end mersenne twister algorithm ----
  }
 
  /**
   * this method resets the state of this instance using the 64
   * bits of seed data provided. note that if the same seed data
   * is passed to two different instances of mtrandom (both of
   * which share the same compatibility state) then the sequence
   * of numbers generated by both instances will be identical.
   * <p>
   * if this instance was initialised in 'compatibility' mode then
   * this method will only use the lower 32 bits of any seed value
   * passed in and will match the behaviour of the original c code
   * exactly with respect to state initialisation.
   *
   * @param seed the 64 bit value used to initialise the random
   * number generator state.
   */
  public final synchronized void setseed(long seed) {
  if (compat) {
    setseed((int)seed);
  } else {
 
    // annoying runtime check for initialisation of internal data
    // caused by java.util.random invoking setseed() during init.
    // this is unavoidable because no fields in our instance will
    // have been initialised at this point, not even if the code
    // were placed at the declaration of the member variable.
    if (ibuf == null) ibuf = new int[2];
 
    ibuf[0] = (int)seed;
    ibuf[1] = (int)(seed >>> 32);
    setseed(ibuf);
  }
  }
 
  /**
   * this method resets the state of this instance using the byte
   * array of seed data provided. note that calling this method
   * is equivalent to calling "setseed(pack(buf))" and in particular
   * will result in a new integer array being generated during the
   * call. if you wish to retain this seed data to allow the pseudo
   * random sequence to be restarted then it would be more efficient
   * to use the "pack()" method to convert it into an integer array
   * first and then use that to re-seed the instance. the behaviour
   * of the class will be the same in both cases but it will be more
   * efficient.
   *
   * @param buf the non-empty byte array of seed information.
   * @throws nullpointerexception if the buffer is null.
   * @throws illegalargumentexception if the buffer has zero length.
   */
  public final void setseed(byte[] buf) {
  setseed(pack(buf));
  }
 
  /**
   * this method resets the state of this instance using the integer
   * array of seed data provided. this is the canonical way of
   * resetting the pseudo random number sequence.
   *
   * @param buf the non-empty integer array of seed information.
   * @throws nullpointerexception if the buffer is null.
   * @throws illegalargumentexception if the buffer has zero length.
   */
  public final synchronized void setseed(int[] buf) {
  int length = buf.length;
  if (length == 0) throw new illegalargumentexception("seed buffer may not be empty");
  // ---- begin mersenne twister algorithm ----
  int i = 1, j = 0, k = (n > length ? n : length);
  setseed(magic_seed);
  for (; k > 0; k--) {
    mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * magic_factor2)) + buf[j] + j;
    i++; j++;
    if (i >= n) { mt[0] = mt[n-1]; i = 1; }
    if (j >= length) j = 0;
  }
  for (k = n-1; k > 0; k--) {
    mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * magic_factor3)) - i;
    i++;
    if (i >= n) { mt[0] = mt[n-1]; i = 1; }
  }
  mt[0] = upper_mask; // msb is 1; assuring non-zero initial array
  // ---- end mersenne twister algorithm ----
  }
 
  /**
   * this method forms the basis for generating a pseudo random number
   * sequence from this class. if given a value of 32, this method
   * behaves identically to the genrand_int32 function in the original
   * c code and ensures that using the standard nextint() function
   * (inherited from random) we are able to replicate behaviour exactly.
   * <p>
   * note that where the number of bits requested is not equal to 32
   * then bits will simply be masked out from the top of the returned
   * integer value. that is to say that:
   * <pre>
   * mt.setseed(12345);
   * int foo = mt.nextint(16) + (mt.nextint(16) << 16);</pre>
   * will not give the same result as
   * <pre>
   * mt.setseed(12345);
   * int foo = mt.nextint(32);</pre>
   *
   * @param bits the number of significant bits desired in the output.
   * @return the next value in the pseudo random sequence with the
   * specified number of bits in the lower part of the integer.
   */
  protected final synchronized int next(int bits) {
  // ---- begin mersenne twister algorithm ----
  int y, kk;
  if (mti >= n) {     // generate n words at one time
 
    // in the original c implementation, mti is checked here
    // to determine if initialisation has occurred; if not
    // it initialises this instance with default_seed (5489).
    // this is no longer necessary as initialisation of the
    // java instance must result in initialisation occurring
    // use the constructor mtrandom(true) to enable backwards
    // compatible behaviour.
 
    for (kk = 0; kk < n-m; kk++) {
    y = (mt[kk] & upper_mask) | (mt[kk+1] & lower_mask);
    mt[kk] = mt[kk+m] ^ (y >>> 1) ^ magic[y & 0x1];
    }
    for (;kk < n-1; kk++) {
    y = (mt[kk] & upper_mask) | (mt[kk+1] & lower_mask);
    mt[kk] = mt[kk+(m-n)] ^ (y >>> 1) ^ magic[y & 0x1];
    }
    y = (mt[n-1] & upper_mask) | (mt[0] & lower_mask);
    mt[n-1] = mt[m-1] ^ (y >>> 1) ^ magic[y & 0x1];
 
    mti = 0;
  }
 
  y = mt[mti++];
 
  // tempering
  y ^= (y >>> 11);
  y ^= (y << 7) & magic_mask1;
  y ^= (y << 15) & magic_mask2;
  y ^= (y >>> 18);
  // ---- end mersenne twister algorithm ----
  return (y >>> (32-bits));
  }
 
  // this is a fairly obscure little code section to pack a
  // byte[] into an int[] in little endian ordering.
 
  /**
   * this simply utility method can be used in cases where a byte
   * array of seed data is to be used to repeatedly re-seed the
   * random number sequence. by packing the byte array into an
   * integer array first, using this method, and then invoking
   * setseed() with that; it removes the need to re-pack the byte
   * array each time setseed() is called.
   * <p>
   * if the length of the byte array is not a multiple of 4 then
   * it is implicitly padded with zeros as necessary. for example:
   * <pre>  byte[] { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06 }</pre>
   * becomes
   * <pre>  int[] { 0x04030201, 0x00000605 }</pre>
   * <p>
   * note that this method will not complain if the given byte array
   * is empty and will produce an empty integer array, but the
   * setseed() method will throw an exception if the empty integer
   * array is passed to it.
   *
   * @param buf the non-null byte array to be packed.
   * @return a non-null integer array of the packed bytes.
   * @throws nullpointerexception if the given byte array is null.
   */
  public static int[] pack(byte[] buf) {
  int k, blen = buf.length, ilen = ((buf.length+3) >>> 2);
  int[] ibuf = new int[ilen];
  for (int n = 0; n < ilen; n++) {
    int m = (n+1) << 2;
    if (m > blen) m = blen;
    for (k = buf[--m]&0xff; (m & 0x3) != 0; k = (k << 8) | buf[--m]&0xff);
    ibuf[n] = k;
  }
  return ibuf;
  }
}

// mt19937的java实现
mtrandom mtrandom=new mtrandom();
map<integer,integer> map=new hashmap<>();
//循环次数
int times=1000000;
long starttime=system.currenttimemillis();
for(int i=0;i<times;i++){
  //使用map去重
  map.put(mtrandom.next(32),0);
}
//打印循环次数
system.out.println("times:"+times);
//打印map的个数
system.out.println("num:"+map.size());
//打印非重复比率
system.out.println("proportion:"+map.size()/(double)times);
//花费的时间(单位为毫秒)
system.out.println("time:"+(system.currenttimemillis()-starttime));

times:1000000
num:999886
proportion:0.999886
time:374