ArrayList真的是因为实现了RandomAccess接口才能做到快速随机访问的吗

RandomAccess 接口

首先，RandomAccess接口是什么，以下代码可见：

public interface RandomAccess {
}

RandomAccess接口其实是一个标记接口，它只负责声明实现该接口的List支持快速随机访问，主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。

Collections.binarySearch()源码

我们来看Collections下的binarySearch方法的源码：

    public static <T>int binarySearch(List<? extends Comparable<? super T>> list, T key) {if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)return Collections.indexedBinarySearch(list, key);elsereturn Collections.iteratorBinarySearch(list, key);}

我们可以看到，在进行二分查找的时候，list会先判断是否是RandomAccess也即是否实现了RandomAccess接口，接着再调用想用的二分查找算法来进行，（其中: BINARYSEARCH_THRESHOLD Collections的一个常量（5000），它是二分查找的阀值。）如果实现了RandomAccess接口的List，执行indexedBinarySearch方法，否则执行 iteratorBinarySearch方法。

分别看下这两个方法的实现:

    private static <T>int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {int low = 0;int high = list.size()-1;while (low <= high) {int mid = (low + high) >>> 1;Comparable<? super T> midVal = list.get(mid);int cmp = midVal.compareTo(key);if (cmp < 0)low = mid + 1;else if (cmp > 0)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found}

indexedBinarySearch 方法是直接通过list.get()方法来访问元素

private static <T>int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key){int low = 0;int high = list.size()-1;ListIterator<? extends Comparable<? super T>> i = list.listIterator();while (low <= high) {int mid = (low + high) >>> 1;Comparable<? super T> midVal = get(i, mid);int cmp = midVal.compareTo(key);if (cmp < 0)low = mid + 1;else if (cmp > 0)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found}

iteratorBinarySearch中是list.listIterator()来查找相应的元素

人们认识到，随机访问和顺序访问之间的区别通常是模糊的。例如，一些List实现提供了渐近线性访问时间，如果它们在实践中获得了巨大但恒定的访问时间。这样的List实现通常应实现此接口。根据经验，如果对于类的典型实例，以下循环：

    for (int i=0, n=list.size(); i < n; i++)list.get(i);

会比下面这个更快

    for (Iterator i=list.iterator(); i.hasNext(); )i.next();

总结

若是集合的for循环访问数据比使用iterator访问来的高效快速，那么最好去实现RandomAccess这个标记接口，这样在一些框架代码中，就可以根据是否实现了RandomAccess接口做出更好的决策方式

（是因为它这个集合用for循环更快所以才实现RandomAccess接口，注意不要搞反了）

如有错误，还请多多指教！
转载或者引用本文内容请注明来源及原作者：橘足轻重；