1.Collections.shuffler
最近有个需求是生成十万级至百万级的所有随机数，最简单的思路是一个个生成，生成新的时候排重，但是这样时间复杂度是o(n^2),网上看了几个博客的解决方法都不是很理想
因为是要求生成所有随机数，可以换个思路，即生成顺序数，然后打乱即可。最后用到了shuffler方法，效率很高，百万级的数据毫秒就能打乱完， 其实这个算法也可以用于生成范围内一定量的随机数。
先介绍下源码实现吧，其实思路很简单。
jdk:
shuffle
public static void shuffle(List<?> list)使用默认随机源对指定列表进行置换。所有置换发生的可能性都是大致相等的。
前面描述中使用了不确定的词“大致”，因为随机源只是大致上独立选择位的无偏源。如果它是一个随机选择位的最佳源，那么算法将完全一致的选择置换。
此实现向后遍历列表，从最后一个元素一直到第二个元素，将随机选择的元素重复交换到“当前位置”。元素是从列表的一部分随机选择的，该部分列表从第一个元素一直到当前位置（包括）。
此方法以线性时间运行。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此实现在改组列表前将指定列表转储到数组中，并将改组后的数组转储回列表中。这避免了二次行为，该行为是原地改组一个“有序访问”列表引起的。
参数：
list - 要改组的列表。
抛出：
UnsupportedOperationException - 如果指定列表或其列表迭代器不支持 set 操作。
shuffle
public static void shuffle(List<?> list,
Random rnd)使用指定的随机源对指定列表进行置换。所有置换发生的可能性都是相等的，假定随机源是公平的。
此实现向后遍历列表，从最后一个元素一直到第二个元素，将随机选择的元素重复交换到“当前位置”。元素是从列表的一部分随机选择的，该部分列表从第一个元素一直到当前位置（包括）。
此方法以线性时间运行。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此实现在改组列表前将指定列表转储到一个数组中，并将改组后的数组转储回列表中。这避免了二次行为，该行为是原地改组一个“有序访问”列表引起的。
参数：
list - 要改组的列表。
rnd - 用来改组列表的随机源。
抛出：
UnsupportedOperationException - 如果指定列表或其列表迭代器不支持 set 操作。
重载函数的思路是一样的， 如果没有穿随机类就生成一个调第二个函数。
java.util.Collections
public static void shuffle(List<?> list) {
if (r == null) {
r = new Random();
}
shuffle(list, r);
}
private static Random r;
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 {
Object arr[] = list.toArray();
// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));
// Dump array back into list
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
核心就是遍历，首先获取集合的元素个数，如果小于5个或者实现了RandomAccess接口，就循环一遍，随机交换集合中两个相邻的元素的位置，RandomAccess是一个标记接口，如果实现了这个接口就表示支持快速的随机访问操作，类似于数组。
如果大于等于5个元素也没有实现RandomAccess接口，那么就转为数组，之后也是循环，随机交换集合中两个相邻的元素的位置，最后再将数组放回原来的list中。