java - Collection.shuffle 与种子随机 - 列表大小为 16 的异常

Question

当使用递增 1 的随机种子(例如 epochDay)来为列表生成确定性洗牌时，我观察到对于种子的某些序列，某个条目将始终位于结果的最后位置。

这只发生在尺寸为 16 的集合中。

我已将范围缩小到这段代码:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        for (int i = 0; i < 50; i++) {
            List<String> values = Arrays.asList(
                "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
                "A", "B", "C", "D", "E", "F"
            );

            Random r = new Random(i);
            Collections.shuffle(values, r);
            System.out.println(values);
        }
    }
}

产生以下输出:

[0, 7, C, 9, 6, 5, A, 4, 3, 1, 2, E, 8, F, D, B]
[A, 5, 0, C, 3, 8, 6, 7, E, 4, F, 2, 9, 1, D, B]
[D, 5, 7, E, A, 2, 3, F, 0, 6, 1, 9, 8, 4, C, B]
[4, F, 8, E, A, 3, D, 1, C, 9, 2, 0, 7, 6, 5, B]
[E, 6, A, 5, F, 2, 8, 0, C, D, 4, 3, 9, 1, 7, B]
[2, 9, 0, 1, C, F, 5, 3, 8, D, E, 6, A, 4, 7, B]
[5, F, 0, D, 3, A, 8, 2, C, 7, 4, 1, 9, E, 6, B]
[3, C, 1, 6, 2, 0, 7, 9, 5, 8, D, 4, A, F, E, B]
[3, 9, 2, A, 5, 6, F, D, 8, E, 7, 0, C, 4, 1, B]
[0, D, 4, 5, E, 2, A, 7, 6, 3, 9, C, F, 8, 1, B]
[2, 5, E, 3, 8, D, 1, 6, 4, C, 7, A, F, 9, 0, B]
[C, 3, 5, A, 6, E, 4, 1, 2, 0, 7, 9, F, D, 8, B]
[F, 7, 3, D, 8, E, C, 9, 5, 0, A, 4, 1, 6, 2, B]
[8, 0, 5, D, E, 6, 4, 9, 2, 3, C, 7, 1, F, A, B]
[5, 4, 7, A, 1, 3, 0, 8, F, 6, E, 2, C, D, 9, B]
[8, C, 6, 4, D, F, 3, 5, 7, 9, A, 1, 0, E, 2, B]
[9, F, A, 4, 0, 6, E, 8, 5, 3, 2, C, 1, D, 7, B]
[8, 5, 9, A, 7, 6, 1, E, 3, F, C, D, 2, 4, 0, B]
[9, D, 5, 6, C, A, 3, 7, 2, 8, 0, F, 1, 4, E, B]
[D, 3, 1, 6, 5, 4, 7, F, 9, C, 2, A, 0, 8, E, B]
[6, 8, 0, 7, A, C, 4, D, 9, 3, F, 5, 2, E, 1, B]
[2, 7, 1, D, C, A, 0, E, F, 4, 5, 8, 3, 6, 9, B]
[D, A, 9, 5, 1, 6, 4, F, E, 7, C, 3, 2, 8, 0, B]
[E, 7, A, C, 2, 9, 1, D, 5, 0, 4, 6, 3, F, 8, B]
[9, E, 8, D, 4, 0, 3, C, 1, F, 7, 2, 5, 6, A, B]
[D, A, C, F, E, 2, 8, 0, 6, 5, 7, 1, 4, 9, 3, B]
[A, 0, C, 2, D, 1, 3, E, 6, 7, 5, 8, 4, F, 9, B]
[D, 5, A, 9, C, 3, 6, 8, E, 0, 7, F, 4, 1, 2, B]
[F, 5, 1, E, D, 3, 9, 0, C, 2, A, 6, 7, 8, 4, B]
[C, 9, 1, 2, 6, 8, 0, 3, E, F, A, 5, 7, D, 4, B]
[1, 0, 9, C, 8, 7, 2, E, F, 6, A, 4, 5, D, 3, B]
[E, 2, 8, C, D, 1, 7, 5, 0, 9, A, 3, 6, 4, F, B]
[4, 2, 6, F, C, 8, 5, A, E, 0, 3, 7, D, 9, 1, B]
[0, 5, E, 7, 4, 2, 1, 6, 8, F, 3, C, A, D, 9, B]
[0, 9, 3, 2, 4, A, E, F, C, 6, 1, 5, 7, D, 8, B]
[D, F, 2, 6, 9, A, 1, 0, 5, 7, 3, C, E, 4, 8, B]
[2, 5, 4, 0, 1, C, D, 7, 8, 9, 6, 3, E, F, A, B]
[7, A, 8, E, 1, 5, 0, 9, 4, C, 6, D, F, 2, 3, B]
[7, 3, D, 0, C, 9, A, F, 5, 6, 4, 1, 8, E, 2, B]
[5, 3, 7, E, C, 8, F, 4, 1, A, D, 0, 9, 6, 2, B]
[C, 5, 1, 2, 7, 0, E, 3, 6, A, 9, 8, F, D, 4, B]
[7, 8, 5, 0, D, 3, 1, 6, A, 2, 9, F, E, 4, C, B]
[F, 4, 0, 1, 7, A, E, 9, 2, 5, 8, D, C, 6, 3, B]
[1, C, 7, 3, 2, 4, 6, 0, 9, A, 8, 5, D, E, F, B]
[1, A, 2, 5, 6, E, 9, 7, 3, 8, F, C, 0, 4, D, B]
[7, F, 5, D, 4, 8, E, 2, A, 1, C, 3, 0, 9, 6, B]
[7, 3, 8, 2, 6, D, 4, 1, F, 5, E, A, 0, 9, C, B]
[2, 9, 7, F, 3, 6, A, 4, E, 8, 0, C, 1, D, 5, B]
[7, 6, 1, D, 8, 5, 0, 4, A, C, 3, 9, 2, E, F, B]
[5, A, 1, F, 6, 2, 9, 7, 8, C, 4, 0, E, D, 3, B]

(在 Oracle JRE 1.8、10 和 12 上测试)

如您所见，条目 B 始终位于列表的最后位置。当我让种子运行到其他范围内的值时，不同的元素将被放置在最后，但对于 100-300 增量种子值的间隔始终是相同的元素。

我可以通过在随机播放之前调用 r.nextInt() 来解决这个问题，但是我仍然对这种行为感到困惑，并且想知道是否有对此的解释或文档。

Answer 1

源代码shuffle(List<?> list, Random rnd)

public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
        ...

所以问题是random.nextInt(16)总是返回11

和Random.java

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

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

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

public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);

    int r = next(31);
    int m = bound - 1;
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        r = (int)((bound * (long)r) >> 31);
    else {
        for (int u = r;
             u - (r = u % bound) + m < 0;
             u = next(31))
            ;
    }
    return r;
}

第一次来电random.nextInt(16)

int bound = 16;
long seed = (i ^ multiplier) & mask;
long r = (seed * multiplier + addend) & mask;
r = (r >>> (48 - 31));
r = (bound * r) >> 31;

简化后

//j is in [-64, 64]
r = (((multiplier + j) * multiplier + addend) >>> 44) & 0xF

和multiplier < (1 << 35) ，所以

r = ((multiplier * multiplier) >> 44) & 0xF

即11