JDK Collections.shuffle(List<?> list, Random rnd)源码分析

jdk的源码如下

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
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
 }

一、首先是判断要打乱的list的属性：list的size和是否实现RandomAccess接口

如果list的size小于SHUFFLE_THRESHOLD(5) 或者 list实现了RandomAccess接口，则直接交换list内元素的位置。具体的交换策略如下：

令list的size为n, 从n-1位开始，将该位的元素与其前面某一位(随机得到)元素交换，直到第1位结束。

使用的函数：

• swap(List<?> list, int i, int j)

public static void swap(List<?> list, int i, int j) {
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        final List l = list;
        l.set(i, l.set(j, l.get(i)));   //将j位置的值和i位置的值进行交换
}

• E set(int index, E element)接口

/**
     * Replaces the element at the specified position in this list with the
     * specified element (optional operation).
     * 
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     */
    E set(int index, E element)

• E set(int index, E element)某一实现

public E set(int index, E element) {
      try {
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);    
            return oldVal;      //将index的值设置为element，并返回原来的值
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
}

二、如果list没有实现RandomAccess接口且长度大于SHUFFLE_THRESHOLD(5)

这时候首先要做的是将list转化成数组，这个和RandomAccess有关

/**
 * Marker interface used by <tt>List</tt> implementations to indicate that
 * they support fast (generally constant time) random access.  The primary
 * purpose of this interface is to allow generic algorithms to alter their
 * behavior to provide good performance when applied to either random or
 * sequential access lists.
 *
 * <p>The best algorithms for manipulating random access lists (such as
 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * <tt>instanceof</tt> this interface before applying an algorithm that would
 * provide poor performance if it were applied to a sequential access list,
 * and to alter their behavior if necessary to guarantee acceptable
 * performance.
 *
......
public interface RandomAccess {
}

RandomAccess用于标识ist的实现类是否支持快速地随机访问(一般是O(1)的时间复杂度)，例如ArraryList实现了RandomAccess接口，随机访问一个元素(get(i))所花费的时间复杂度是O(1)，而LinkedList却没有实现这个接口，所以随机一个元素的时间复杂度是O(n)(最坏情况)。所以在遍历一个list时，可以先判断它是否实现了RandomAccess接口，根据数据结构的不同先进行相应的处理，避免出现O(n²)的时间复杂度。
如在shuffle()的else代码段中，就先将没有实现RandomAccess接口的list转换成数组，然后在执行交换策略，这样避免O(n²)的时间复杂度。

---

以上内容如有不正确的地方，欢迎支持。