1. <span style="font-size: small;">/**
2. * Randomly permute the specified list using the specified source of
3. * randomness. All permutations occur with equal likelihood
4. * assuming that the source of randomness is fair.<p>
5. *
6. * This implementation traverses the list backwards, from the last element
7. * up to the second, repeatedly swapping a randomly selected element into
8. * the "current position". Elements are randomly selected from the
9. * portion of the list that runs from the first element to the current
10. * position, inclusive.<p>
11. *
12. * This method runs in linear time. If the specified list does not
13. * implement the {@link RandomAccess} interface and is large, this
14. * implementation dumps the specified list into an array before shuffling
15. * it, and dumps the shuffled array back into the list. This avoids the
16. * quadratic behavior that would result from shuffling a "sequential
17. * access" list in place.
18. *
19. * @param list the list to be shuffled.
20. * @param rnd the source of randomness to use to shuffle the list.
21. * @throws UnsupportedOperationException if the specified list or its
22. * list-iterator does not support the <tt>set</tt> operation.
23. */
26. public static void shuffle(List<?> list, Random rnd) {
27. int size = list.size();
28. if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {//注意这一句中的instanceof
29. for (int i=size; i>1; i--)
30. swap(list, i-1, rnd.nextInt(i));
31. } else {
32. Object arr[] = list.toArray();
34. // Shuffle array
35. for (int i=size; i>1; i--)
36. swap(arr, i-1, rnd.nextInt(i));
38. // Dump array back into list
39. ListIterator it = list.listIterator();
40. for (int i=0; i<arr.length; i++) {
41. it.next();
42. it.set(arr[i]);
43. }
44. }
45. }</span>

由以上的jdk源码可见,在对实现list接口的对象进行洗牌,打乱时,区分了该类是否是RandomAccess的实例,这样做有什么意义呢?请继续向下看:

介绍:

public interface RandomAccess

List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

将操作随机访问列表的最佳算法（如 ArrayList ）应用到连续访问列表（如 LinkedList ）时，可产生二次项的行为。如果将某个算法应用到连续访问列表，那么在应用可能提供较差性能的算法前，鼓励使用一般的列表算法检查给定列表是否为此接口的一个 instanceof ，如果需要保证可接受的性能，还可以更改其行为。

现在已经认识到，随机和连续访问之间的区别通常是模糊的。例如，如果列表很大时，某些 List 实现提供渐进的线性访问时间，但实际上是固定的访问时间。这样的 List 实现通常应该实现此接口。

强调:

JDK中推荐的是对List集合尽量要实现RandomAccess接口

如果集合类是RandomAccess的实现，则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历，在效率上要差一些。反过来，如果List是Sequence List，则最好用迭代器来进行迭代。

JDK中说的很清楚，在对List特别是Huge size的List的遍历算法中，要尽量来判断是属于RandomAccess(如ArrayList)还是Sequence List (如LinkedList），因为适合RandomAccess List的遍历算法，用在Sequence List上就差别很大，常用的作法就是：
要作一个判断：
if (list instance of RandomAccess) {
for(int m = 0; m < list.size(); m++){}
}else{
Iterator iter = list.iterator();
while(iter.hasNext()){}
}

验证:

1. <span style="font-size: small;">/*
2. * To change this template, choose Tools | Templates
3. * and open the template in the editor.
4. */
5. package testrandomaccess;
7. import java.util.ArrayList;
8. import java.util.Iterator;
9. import java.util.LinkedList;
10. import java.util.List;
11. import java.util.RandomAccess;
13. /**
14. *
15. * @author bolong
16. */
17. public class TestRandomAccess {
18. // 初始化列表
20. public static void initList(List list, int n) {
21. for (int i = 0; i < n; i++) {
22. list.add(i);
23. }
24. }
25. //使用循环进行对列表的迭代
27. public static void traverseWithLoop(List list) {
28. long starttime = 0;
29. long endtime = 0;
30. starttime = System.currentTimeMillis();
31. for (int count = 0; count <= 1000; count++) {
32. for (int i = 0; i < list.size(); i++) {
33. list.get(i);
34. }
35. }
36. endtime = System.currentTimeMillis();
37. System.out.println("使用loop迭代一共花了" + (endtime - starttime) + "ms时间");
39. }
40. //使用迭代器对列表进行迭代
42. public static void traverseWithIterator(List list) {
43. long starttime = 0;
44. long endtime = 0;
45. starttime = System.currentTimeMillis();
46. for (int count = 0; count <= 1000; count++) {
47. for (Iterator itr = list.iterator(); itr.hasNext();) {
48. itr.next();
49. }
50. }
51. endtime = System.currentTimeMillis();
52. System.out.println("使用Iterator迭代一共花了" + (endtime - starttime) + "ms时间");
53. }
55. public static void traverse(List list) {
57. long starttime = 0;
58. long endtime = 0;
59. if (list instanceof RandomAccess) {
60. System.out.println("该list实现了RandomAccess接口");
61. starttime = System.currentTimeMillis();
62. for (int count = 0; count <= 1000; count++) {
63. for (int i = 0; i < list.size(); i++) {
64. list.get(i);
65. }
66. }
67. endtime = System.currentTimeMillis();
68. System.out.println("迭代一共花了" + (endtime - starttime) + "ms时间");
69. } else {
70. System.out.println("该list未实现RandomAccess接口");
71. starttime = System.currentTimeMillis();
72. for (int count = 0; count <= 1000; count++) {
73. for (Iterator itr = list.iterator(); itr.hasNext();) {
74. itr.next();
75. }
76. }
77. endtime = System.currentTimeMillis();
78. System.out.println("迭代一共花了" + (endtime - starttime) + "ms时间");
79. }
80. }
82. public static void main(String[] args) {
83. ArrayList arraylist = new ArrayList();
84. LinkedList linkedlist = new LinkedList();
85. initList(arraylist, 1000);
86. initList(linkedlist, 1000);
87. traverse(arraylist);
88. traverse(linkedlist);
89. traverseWithIterator(arraylist);
90. traverseWithLoop(arraylist);
91. traverseWithIterator(linkedlist);
92. traverseWithLoop(linkedlist);
93. }
94. }
95. </span>

运行程序输出的结果为:

该list实现了RandomAccess接口
迭代一共花了47ms时间
该list未实现RandomAccess接口
迭代一共花了15ms时间
使用Iterator迭代一共花了79ms时间
使用loop迭代一共花了46ms时间
使用Iterator迭代一共花了47ms时间
使用loop迭代一共花了797ms时间

结论:

根据程序输出的结果的确证明了,arraylist等实现了RandomAccessj接口的类在进行迭代时使用loop效率更高,而linkedList那些未实现该接口的类在进行迭代时使用Iterator进行迭代效率更高.