Java源码-快速随机访问RandomAccess
背景
在学习集合工具类Collections时，发现多个方法针对集合是否实现接口RandomAccess，实现的方式也是不同的。如洗牌方法shuffle
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]);
}
}
}
说明
接口RandomAccess是 Java 集合框架的成员。
-
从字面翻译，表示随机访问。而所有集合都是具备这一功能，即方法get()。由于集合对象的结构不同，方法get()的实现也不同，速度也有所不同。
-
虽然集合都具备随机访问功能，但并不都具备快速随机访问功能。
-
因此，集合是否实现这一接口，表示集合是否具备快速随机访问功能。
源码
空接口
接口RandomAccess是空接口，作为标记接口存在，是否实现表示是否具备快速随机访问功能。如下：
public interface RandomAccess {
}
而注释中，针对问题也有相关说明：
RandomAccess类注释
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.
List实现使用的标记接口来指示它们支持快速（通常是恒定时间）随机访问。此接口的主要目的是允许通用算法改变其行为，以在应用于随机或顺序访问列表时提供良好的性能。
判断集合对象存在RandomAccess标记
根据是否存在这一标记，选择不同的访问方式。如何判断是否存在这一标记，可以使用关键字instanceof。在类注释中有说明，如下：
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.
用于操作随机访问列表的最佳算法（例如
ArrayList）在应用于顺序访问列表（如LinkedList）时可以产生二次行为。鼓励通用列表算法在应用一个算法之前检查给定的列表是否是instanceof这个接口，如果它被应用于顺序访问列表会提供较差的性能，并在必要时改变它们的行为以保证可接受的性能。
对于集合对象ArrayList具备快速随机访问功能，如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
ArrayList实现了接口RandomAccess，标记了ArrayList是具备快速访问功能
而对于LinkedList，是不具备快速随机访问功能的，如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
}
区分是否需要实现RandomAccess
It is recognized that the distinction between random and sequential access is often fuzzy. For example, some <tt>List</tt> implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a <tt>List</tt> implementation should generally implement this interface. As a rule of thumb, a <tt>List</tt> implementation should implement this interface if
人们认识到随机访问和顺序访问之间的区别通常是模糊的。例如，一些
List实现提供了渐近线性的访问时间，如果它们变得很大，但实际上访问时间是恒定的。这样的List实现一般应该实现这个接口。根据经验，List实现应该实现这个接口。如果对于类的典型实例
for typical instances of the class, this loop:
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
runs faster than this loop:
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
说明
当随机访问比顺序访问效率更快时，需要实现RandomAccess。那么，当一个集合对象实现了RandomAccess，则使用第一种遍历；否则，可以采用第二个遍历方式。
LinkedList的get()
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// size >> 1 等价于 size / 2^1
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
...
}
简单地说，根据index和size/2的大小，即集合的中间位置和index相对位置。
如果index在集合中间位置的左边，则从起始位置，向右遍历到位置index即可，如下图：
如果index在集合中间位置的右边，则从末尾位置，向左遍历到位置index集合；如下图：
ArrayList的get()
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
}
可以发现，ArrayList是基于数组而来的，所以每个元素都有其对应的index
测试
测试代码
编写测试类，只针对get()操作进行测试，不考虑其它操作
public class RandomAccessTest {
public static void getByLinkedOfFirstLoop(List<Integer> intsOfLinked){
for (int i=0, n=intsOfLinked.size(); i < n; i++){
intsOfLinked.get(i);
// System.out.println(intsOfArray.get(i));
}
}
public static void getByLinkedOfSecondLoop(List<Integer> intsOfLinked){
for (Iterator i = intsOfLinked.iterator(); i.hasNext(); ){
i.next();
// System.out.println(i.next());
}
}
public static void getByArrayOfFirstLoop(List<Integer> intsOfArray){
for (int i=0, n=intsOfArray.size(); i < n; i++){
intsOfArray.get(i);
// System.out.println(intsOfArray.get(i));
}
}
public static void getByArrayOfSecondLoop(List<Integer> intsOfArray ) {
for (Iterator i = intsOfArray.iterator(); i.hasNext(); ) {
i.next();
// System.out.println(i.next());
}
}
public static void main(String[] args) {
List<Integer> intsOfLinkedList = new LinkedList<>();
List<Integer> intsOfArrayList = new ArrayList<>();
int sizes = 5;
for (int i = 0; i < sizes; i++) {
intsOfLinkedList.add(i);
intsOfArrayList.add(i);
}
int count = 0;
int numbers = 1000000;
for (int i = 0; i < numbers; i++) {
long startTime = System.currentTimeMillis();
// 测试链表第1种遍历
// getByLinkedOfFirstLoop(intsOfLinkedList);
// 测试链表第2种遍历
// getByLinkedOfSecondLoop(intsOfLinkedList);
// 测试ArrayList第1种遍历
// getByArrayOfFirstLoop(intsOfArrayList);
// 测试ArrayList第2种遍历
getByArrayOfSecondLoop(intsOfArrayList);
long endTime = System.currentTimeMillis();
count += endTime - startTime;
}
System.out.println(count);
System.out.println("use time : " + (float)count/numbers);
}
}
测试结果
测试结果并不完全正确，不过可以作为参考
测试总结
- 对于链表LinkedList
? 大多数情况下，fori的遍历方式比iterator的耗时长。而特殊情况下均在列表个数较小的情况下发生，但差距并不大。所以可以通过是否实现RandomAccess，选择调用方式。
- 对于ArrayList
? 在多次测试下，耗时最短均发生在遍历方式fori。
- LinkedList和ArrayList
无论是哪一种遍历方式，ArrayList的耗时都是最短的。这也是因为其自身结构导致的。
另外，对于元素个数较少时，fori和iterator差距并不大。验证了在集合处理时，会根据集合的长度进行判断，采取哪一种处理方式。如在类Collections的方法实现如下：
private static final int SHUFFLE_THRESHOLD = 5;
public static void shuffle(List<?> list, Random rnd) {
...
if (size < 5 || list instanceof RandomAccess) {
// 直接处理
}else{
// 先转换为数组处理
}
...
}
}
这样处理，可以避免不具备快速随机访问的集合类使用fori的方式
总结
所以当获取一个集合对象时，首先需要使用关键字instanceof判断集合对象是否具备快速随机访问的特性。在集合对象不扩展的条件下：如果集合对象的长度不大且具备快速随机访问特性，可以使用fori的方式进行遍历；否则，可以将集合对象先转换为数组，再进行处理。如下：
public static void shuffle(List<?> list, Random rnd) {
...
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
// 直接处理
}else{
// 先转换为数组处理
}
...
}