从上一篇我们看到，ArrayList实现了RandomAccess接口，而LinkedList没有实现这个接口。这是为什么呢？而RandomAccess到底是什么呢？
/**
* Marker interface used by {@code List} 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
* {@code ArrayList}) can produce quadratic behavior when applied to
* sequential access lists (such as {@code LinkedList}). Generic list
* algorithms are encouraged to check whether the given list is an
* {@code instanceof} 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.
*
* <p>It is recognized that the distinction between random and sequential
* access is often fuzzy. For example, some {@code List} implementations
* provide asymptotically linear access times if they get huge, but constant
* access times in practice. Such a {@code List} implementation
* should generally implement this interface. As a rule of thumb, a
* {@code List} implementation should implement this interface if,
* for typical instances of the class, this loop:
* <pre>
* for (int i=0, n=list.size(); i < n; i++)
* list.get(i);
* </pre>
* runs faster than this loop:
* <pre>
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
* </pre>
*
* <p>This interface is a member of the
* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
* Java Collections Framework</a>.
*
* @since 1.4
*/
public interface RandomAccess {
}
典型的注释比代码还多。就一个空的接口。那么，我们看看注释说些什么。
RandomAccess 是 List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
这个接口的主要目的是允许通用算法来改变他们的行为时提供良好的性能应用于随机或顺序访问列表。
原来，第一段注释说明，这只是个标记接口。带这个标记的类随机访问都非常快，而且耗时固定！
这不就是印证了我们之前分析ArrayList的随机访问get通过内存地址偏移计算得出，时间复杂度是O(1)吗？
而LinkedList之所以不没有这个标记接口，就是因为它随机访问做不到O(1)。
所以，一个类先拥有了某种能力，然后作者给它打上一个标记，声明我这个类拥有这种能力。这就是标记接口的作用。
再来看第二段注释。
操作随机访问列表(如{@code ArrayList})的最佳算法在应用于顺序访问列表(如{@code LinkedList})时可能产生二次行为。我们鼓励通用列表算法检查给定列表是否是一个{@code instanceof}这个接口，然后再应用一个如果应用于顺序访问列表会导致性能低下的算法，并在必要时改变它们的行为以保证可接受的性能。
注释说，ArrayList随机访问还是最快的（直接用索引），但是这种算法用在遍历LinkedList就很慢。所以呢，作者就鼓励使用这些List的容器的时候，先用个 instanceof 判断下，有没有标记这个RandomAccess接口。如果有，就可以用顺便遍历。如果没有，就得用其它算法提升遍历性能。
这一段主要说用法，是通过 instanceof 判断。
再看第三段。
人们认识到随机访问和顺序访问之间的区别常常是模糊的。例如，一些{@code List}实现提供了渐进线性的访问时间(如果它们获得了巨大的但实际上是常量的访问时间)。这样的一个{@code List}实现通常应该实现这个接口。根据经验，如果对于类的典型实例，这个循环:
* for (int i=0, n=list.size(); i < n; i++)
* list.get(i);
* 上面这个循环就快过下面这个循环:
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
到这里终于明白了RandomAccess 的作用。就是防止一些程序员啊对随机访问和顺序访问的区别不太清楚，乱用索引或者乱用迭代器。
所以呢，java的开发者对拥有随机访问任意下标的元素都比较快的容器，加上了这个RandomAccess 标记，让大家用的时候，通过instanceof来判断，这个容器有没有这个能力。
那么怎么用？看看Collections的binarySearch函数实现：
RandomAccess的用法
通过判断传进来的List是否标记了随机访问，如果是，就用下标访问，如果不包含这个标记，就只能用迭代器来访问。
你现在明白了吗？
网友评论