ArrayList 为什么要实现 RandomAccess？

ArrayList 可能是大家使用最频繁的一个集合了，但是很多人对它熟悉而又陌生，结合我前面的《一个 ArrayList 就能让你面试到哭！》这篇文章，今天我们一起来讨论讨论 ArrayList 为什么要实现 RandomAccess 这个接口！

查看 ArrayList 的源码你会发现它的底层就是一个数组，然而它有实现了 RandomAccess 接口。

RandomAccess

我们先来看看 RandomAccess 接口是干什么的？

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

看重点，RandomAccess 是一个标记接口。什么意思呢？你看 Serializable 接口你就明白了。

第二个重点是，实现 RandomAccess 接口的集合支持快速（通常是固定时间）随机访问。

这句话好像是一句废话，为什么呢？因为我们开头说了 ArrayList 底层是一个数组。数组的特性就是支持下标（索引）快速访问。你现在用了 RandomAccess 接口能让 ArrayList 有更快的访问速度？

找不到答案，那我们就接着往下看！

此接口（RandomAccess）的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

哦，到现在你可能明白了，实现 RandomAccess 接口是允许一般的算法更改其行为。

那既然明白了它的作用，但是我还想知道，这个算法行为是什么时间被更改的。为什么 LinkedList 没有实现这个接口？

带着这个疑问，我查看了 JDK 的相关源码，结果有了重大发现！

Collections

Java 中还有一个重要的 Collections 类。这个类从一开始就被我们忽略了，我在 Collections 类的排序算法源码找到下面的代码：

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);
    else // ：www.xttblog.com
        return Collections.iteratorBinarySearch(list, key);
}

BINARYSEARCH_THRESHOLD 的值是5000。

上面代码的意思是 List 的大小少于 5000 或者 list 实现了 RandomAccess, 就采用 index 的方式遍历, 反之就采用 iterator 的方式遍历。

重点是这句代码：list instanceof RandomAccess。

ArrayList 实现了 RandomAccess 接口，所以它的排序算法之类的，就不会采用 iterator 迭代器的方式去遍历。

用了迭代器的方式去遍历 ArrayList ，反而速度会慢！

不行大家自己去用下面两种方式遍历 ArrayList 试一试，看看它们的耗时分别是多少？

for (int i = 0;i < list.size();i++){
    System.out.println(list.get(i));
}
// ：www.xttblog.com
Iterator it = list.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

以 3w 条数据为例，测试结果发现 ArrayList: for 循环遍历耗时: 3 迭代器遍历时间: 7。

： » ArrayList 为什么要实现 RandomAccess？