如何把100万个顺序排列的数字顺序打乱，一种生成不重复伪随机数的高效解决方案

如何生成不重复的伪随机数？

相信这个问题，很多java研发人员都遇到过，或许在面试的过程中，或许在实际的项目开发中。既然是随机，就避免不了不重复，任何算法都实现不了真正的随机，只能够在一定程度上防止高频度的碰撞和相似度，从而给人感觉一个随机的假象。

如何生成不重复的伪随机数？大致有以下几种玩法：

1. 随机生成，即时比对当前所有已生成的数据，若存在，则重新生成，直到成功为止。
2. 寻找一个好的无冲突的hash算法。
3. 按照一定的算法来生成伪随机数，要求满足一定数量级内无相似度。
4. 预先生成好所有无重复随机数并存储，按需取数。

对于1，最开始的时候生成随机数是比较高效的，但是随着生成的数据越来越多，碰撞和冲突的概率越大，性能会越来越低；对于2，好的无冲突的hash算法其实是不存在的，只是冲突概率较低，但不能避免冲突；对于3，按照一定算法生成位随机数，在一定范围内不重复应该还是可以做到的；对于4，预先生成好所有无重复随机数并存储，按需取数，貌似可行，但要考虑存储空间的问题。

在我们的业务系统中，也用到了随机数，我们的策略是3和4的结合，我们预先按照一定的算法生成随机数存储到redis缓存中，按照顺序取出数据，由于业务量和流量是可以预估的，大概能生成多少随机数，我们能提前计算，生成预估值的n倍随机数应该能满足一次活动需求。我们使用了一种双重随机的思路，一方面是考虑存储空间的问题，另一方面也是为了高效避免冲突的问题，一起来看下面的问题吧。

如何把100万个顺序排列的数字顺序打乱？

为什么会有这样的一个问题呢？如果我们能把已知范围的数据随机打乱，就达到了一种随机的目的，需要数据的时候就按照顺序取数就行了，这样对于使用随机数将是件非常高效的事情。但是如何做到把100万个顺序排列的数字顺序打乱效率更高呢？

还是看下面的代码吧，randomSequence是生成[start, end)范围内的全部随机数序列，复杂度为O(n)级别，应该是达到我们的要求了的。这样做没有数据冲突检测，输出的就是一个随机数组，我们只需要把整个数组存入redis就可以了。

/**
 * 生成从start到end的随机数序列
 * 
 * @param start
 *            数据开始 包含start
 * @param end
 *            数据结束 不包含end
 * @return
 */
private static int[] randomSequence(int start, int end) {
    // 数据量
    int total = end - start;
    // 顺序数组
    int[] order = new int[total];
    // 乱序数组
    int[] disorder = new int[total];
    // 初始化顺序数组
    for (int i = 0; i < total; i++) {
        order[i] = start + i;
    }
    Random random = new Random();
    // 顺序数组偏移量,初始值为最后一个元素下标
    int offset = total - 1;
    // 随机获取到的元素位置
    int randomIndex = 0;
    for (int i = 0; i < total; i++) {
        // 在[0,offset]范围内获取到一个随机位置
        randomIndex = random.nextInt(offset + 1);
        // 从顺序表中取出该随机位置的数据放入到乱序数组的第i个位置
        disorder[i] = order[randomIndex];
        // 把最后一个元素的值填充到顺序数组中被取走的元素位置
        order[randomIndex] = order[offset];
        // 偏移量前移
        offset--;
    }
    return disorder;
}

来看看测试代码，生成10个随机数，20个随机数，100万个随机数耗时：

public static void main(String[] args) {
    System.out.println(JSON.toJSONString(randomSequence(0, 10)));
    System.out.println(JSON.toJSONString(randomSequence(0, 20)));
    long start = System.currentTimeMillis();
    randomSequence(0, 1000000);
    long end = System.currentTimeMillis();
    System.out.println("cost " + (end - start) + " ms");
}

下面是运行结果，在普通PC上，生成100万个随机数只需要35毫秒，如果采用生成随机数的过程中去检测数据，生成100万个随机数耗时将是惊人的，毕竟冲突后还要重试。

[1,4,9,8,3,0,7,2,5,6]
[3,6,17,16,12,10,0,13,19,9,15,2,5,4,18,1,11,14,7,8]
cost 35 ms

不重复伪随机数高效解决方案

我们已经解决生成100万个随机数的问题了，接下来再说说如何双重随机最终获取随机数。假设我们现在要生成1个亿的随机数，那么就是100个100万的随机数。先预先生成100组随机数，分别为[0,100万)，[100万,200万)，[200万,300万)……，每组随机数分别存入到Redis的List(List比其他数据结构更好，放入redis的时候使用RPUSH批量插入)中，Key分别为:

RANDOM_GROUP_1,RANDOM_GROUP_2,...,RANDOM_GROUP_100

我们把这组Key也存储到一个Key为RANDOM_GROUP_KEYS的Redis List中。这样一来我们就解决了生成随机数和存储的问题。

接下来谈谈如何使用这些随机数，当用户访问的时候，我们先第一次随机从RANDOM_GROUP_KEYS集合中选取一个分组(这个过程可以使用redis的LINDEX命令，index由程序随机生成，index的取值范围是[0-100))，假设是RANDOM_GROUP_88，我们再使用Redis的命令LPOP取出RANDOM_GROUP_88的第一个元素即可，这个元素就是我们返回给用户的随机数。

这样做我们的随机数都是预先生成的，取数的时候十分高效，redis支持数据分片集群，存储空间的问题已经不是问题。第一次随机是获取key主要是定位到随机数的一个范围，第二次随机取出该范围内的一个数字（这些数字已经乱序/随机了的）。

使用redis随机数需要注意的地方

上面提到最好使用List,是因为我们的随机数生成完全由应用控制，而不是redis控制，所以选择List是比较好的。有可能有人会说，redis不是自己就能随机么？比如使用SPOP命令，是的它的确可以做到，但有时候这样就不受我们控制了，而且SPOP命令在较低的redis版本是有bug的(SPOP不随机的问题)，可参考下面这篇文章：

http://www.dedecms.com/knowledge/data-base/nosql/2012/0820/8964.html

如果对开源产品了解得比较透彻并且你的redis版本支持，那么可以使用Redis的SPOP，这样你就避免了上面100万个数据如何打乱的问题（但是了解一下还是可以的）；如果想在应用程序中控制数据，并且花费的代价也不大的话，我觉得本文是一种不错的解决方案，使用redis高效又简单。