Java 为什么 ArrayList 实现了 RandomAccess 接口？

Why does ArrayList implement RandomAccess Interface?

提问by GD_Java

ArrayListimplements RandomAccessinterface. RandomAccessinterface has no methods. When I checked LinkedListit does not implement RandomAccessinterface.

ArrayList实现RandomAccess接口。RandomAccess接口没有方法。当我检查LinkedList它没有实现RandomAccess接口。

So in case of ArrayList, what is the point of implementing it?

那么，在 情况下ArrayList，实施它的意义何在？

采纳答案by peter.petrov

Interfaces with no methods are called marker interfaces in Java.

没有方法的接口在 Java 中称为标记接口。

As per the JavaDoc of RandomAccess:

根据 RandomAccess 的 JavaDoc：

Marker interface used by List implementations to indicate
that they support fast (generally constant time) random access.

List 实现使用的标记接口来指示
它们支持快速（通常是恒定时间）随机访问。

For more information check the two JavaDoc pages.

有关更多信息，请查看两个 JavaDoc 页面。

http://docs.oracle.com/javase/6/docs/api/java/util/RandomAccess.html

http://docs.oracle.com/javase/6/docs/api/java/util/RandomAccess.html

http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

回答by lejlot

This seems pretty well described in the documentation: http://docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html

这似乎在文档中得到了很好的描述：http: //docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html

RandomAccess Marker interface used by 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. The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an 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.

It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, 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();

List 实现使用的 RandomAccess Marker 接口来指示它们支持快速（通常是恒定时间）随机访问。此接口的主要目的是允许通用算法改变其行为，以在应用于随机或顺序访问列表时提供良好的性能。用于操作随机访问列表（例如 ArrayList）的最佳算法在应用于顺序访问列表（例如 LinkedList）时可以产生二次行为。鼓励通用列表算法在应用算法之前检查给定列表是否是此接口的实例，如果将其应用于顺序访问列表，则会提供较差的性能，并在必要时更改它们的行为以保证可接受的性能。

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

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

运行速度比这个循环快：

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

回答by user2336315

RandomAccess interface has no method

RandomAccess 接口没有方法

This is called a marker interface and is a design pattern called marker interface pattern.

这称为标记界面，是一种称为标记界面模式的设计模式。

When I checked LinkedList it does not implement RandomAccess interface. So in case of ArrayList what is the point of implementing it?

当我检查 LinkedList 时，它没有实现 RandomAccess 接口。那么在 ArrayList 的情况下，实现它的重点是什么？

Because random access in a LinkedListis O(n), while it's O(1) in an ArrayList.

因为 a 中的随机访问LinkedList是 O(n)，而a 中的随机访问是 O(1) ArrayList。

It's stated in the doc:

它在文档中说明：

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList)

用于操作随机访问列表（如 ArrayList）的最佳算法在应用于顺序访问列表（如 LinkedList）时可以产生二次行为

回答by Mahesh Reddy

1) There are two classes which implement RandomAccessInterface. They are:

1）有两个实现RandomAccess接口的类。他们是：

ArrayList (Part of List<I>)
Vector    (Part of List<I>)

2) The purpose of RandomAccessInterface is to retrieve any random element in the Collection at the same speed. Example: I have a collection of 1 million objects. Implementing RandomAccessinterface makes your time to retrieve the 10th element and 17869th element the same. This makes ArrayListand Vectormore powerful.

2) RandomAccessInterface的目的是以相同的速度检索 Collection 中的任何随机元素。示例：我有 100 万个对象的集合。实现RandomAccess接口使您检索第 10 个元素和第 17869 个元素的时间相同。这使得ArrayList和Vector更强大。

3) RandomAccessInterface has no methods or fields and is also called a Marker Interface. These are used to indicate something to the compiler, in other words implementing these interfaces is meant to imply some special treatment of the implementing class.

3）RandomAccess接口没有方法或字段，也称为标记接口。这些用于向编译器指示某些内容，换句话说，实现这些接口意味着对实现类进行一些特殊处理。

回答by Rajesh Dixit

RandomAccess: Marker interface

RandomAccess：标记接口

java.util.RandomAccess - Since JDK 1.4, member of collection framework. Implemetations: ArrayList and CopyOnWriteArrayList.

java.util.RandomAccess - 从 JDK 1.4 开始，集合框架的成员。实现：ArrayList 和 CopyOnWriteArrayList。

For Random access of data (Index basis)

对于数据的随机访问（索引基础）

Marker interface used by 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.

List 实现使用的标记接口来指示它们支持快速（通常是恒定时间）随机访问。此接口的主要目的是允许通用算法改变其行为，以在应用于随机或顺序访问列表时提供良好的性能。

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList).

用于操作随机访问列表（例如 ArrayList）的最佳算法在应用于顺序访问列表（例如 LinkedList）时可以产生二次行为。

Generic list algorithms are encouraged to check whether the given list is an 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.

鼓励通用列表算法在应用算法之前检查给定列表是否是此接口的实例，如果将其应用于顺序访问列表，则会提供较差的性能，并在必要时更改它们的行为以保证可接受的性能。

It is recognized that the distinction between random and sequential access is often fuzzy.

人们认识到随机访问和顺序访问之间的区别通常是模糊的。

A List implementation should implement this interface if, for typical instances of the class, this loop:

如果对于类的典型实例，此循环，则 List 实现应实现此接口：

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();

For more information, see my blog:
http://javaexplorer03.blogspot.in/2015/07/randomaccess-java.html

更多信息请看我的博客：http:
//javaexplorer03.blogspot.in/2015/07/randomaccess-java.html

回答by Shailendra

Let's see how you can practically make use of this marker interface. First the relevant parts from docs(bolds are mine just to emphasise).

让我们看看如何实际使用这个标记界面。首先是文档中的相关部分（粗体是我的，只是为了强调）。

Marker interface used by List implementations to indicate that they supportfast (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. RandomAccess Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithmsto alter their behavior to provide good performancewhen applied to either random or sequential access lists. The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList).

List 实现使用的标记接口来指示它们支持快速（通常是恒定时间）随机访问。此接口的主要目的是允许通用算法改变其行为，以在应用于随机或顺序访问列表时提供良好的性能。List 实现使用的 RandomAccess Marker 接口来指示它们支持快速（通常是恒定时间）随机访问。这个接口的主要目的是让泛型算法来改变自己的行为，以提供良好的性能当应用于随机或顺序访问列表时。用于操作随机访问列表（例如 ArrayList）的最佳算法在应用于顺序访问列表（例如 LinkedList）时可以产生二次行为。

Let's take an example. Suppose you are writing a generic implementation of algorithm such as sort and you are choosing quick sort as you want in-place sorting. Why generic? Because maybe you want the algorithm to be able to work with reasonable and predictable performance characteristics on all kinds of List (there are manykinds out there - aren't). So your algorithm function would take a list as input and return the same list as sorted. For a moment let's leave aside the various factors which influence the performance of quick sort (such as already sorted data, repeated data, right choice of pivot etc.). Apart from the above characteristics of the data/sort another crucial point is that your algorithm makes heavy us of traversing the list - in this case it makes use of random access heavily as it needs to compare and swap elements. So what do you think - will your algorithm perform well on all types of List implementations. Think about LinkedList- there is a provision for random access in the API but it needs lots of traversals because of the very nature of how data is organised in list as nodes pointing to each other and the painful unavoidable act of going through large number of nodes to arrive at a random node. So your generic algorithm has more variability in terms of performance. What if you knew somehow that some Lists provide fast ramdom access and some do not. What if have a marker which says so. In comes the "RandomAccess" marker interface which is implemented (marked/annotated would be better word) by ArrayList to indicate (your code will typically check with instanceofRandomAccess test) that it's quite fast to access randomly it's data and you can rely on that to write an algorithm which performs and if some list does not then try an alternate algorithm or maybe convert it first into ArrayList or at worst reject such an input entirely.

让我们举个例子。假设您正在编写诸如排序之类的算法的通用实现，并且您正在根据需要就地排序选择快速排序。为什么是泛型？因为也许您希望算法能够在各种 List（有很多那里的种类 - 不是）。所以你的算法函数会将一个列表作为输入并返回与排序相同的列表。暂时先抛开影响快速排序性能的各种因素（例如已排序的数据、重复的数据、正确选择枢轴等）。除了数据/排序的上述特征之外，另一个关键点是您的算法使我们大量遍历列表 - 在这种情况下，它大量使用随机访问，因为它需要比较和交换元素。那么你怎么看 - 你的算法会在所有类型的 List 实现上表现良好。考虑链表- 在 API 中有随机访问的规定，但它需要大量的遍历，因为数据在列表中的组织方式的本质是节点相互指向，以及通过大量节点到达的痛苦不可避免的行为一个随机节点。因此，您的通用算法在性能方面具有更大的可变性。如果您以某种方式知道某些列表提供快速随机存取，而有些则不提供，该怎么办。如果有一个这样的标记怎么办。ArrayList 实现了“RandomAccess”标记接口（标记/注释是更好的词）以指示（您的代码通常会检查instanceofRandomAccess 测试），随机访问它的数据非常快，你可以依靠它来编写一个执行算法，如果某些列表没有，那么尝试替代算法，或者可能首先将其转换为 ArrayList 或最坏的情况下完全拒绝这样的输入.

Another part of doc deals with what is considered to be fast random by giving two different ways to access the underlying data which is easy to understand. Fast random access means the first runs faster than second at all times.

文档的另一部分通过提供两种不同的方式来访问易于理解的基础数据来处理被认为是快速随机的内容。快速随机访问意味着第一个始终比第二个运行得快。

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();

回答by Shailesh Pratapwar

RandomAccess interface signifies an Efficient Random accessto elements of Collection.

RandomAccess 接口表示对 Collection 元素的高效随机访问。

In client code, you can check whether the collection is instance of RandomAccess and then only perform the Random access operations.

在客户端代码中，您可以检查集合是否是 RandomAccess 的实例，然后只执行 Random 访问操作。

Elements from both LinkedList and ArrayList can be accessed randomly however ArrayList complexity is O(1) and LinkedList is O(n).

LinkedList 和 ArrayList 中的元素都可以随机访问，但是 ArrayList 复杂度为 O(1)，LinkedList 为 O(n)。

回答by mohsen.nour

The interface has no methods(Marker Interface), but you can use it to test whether a particular collection supports efficient random access

接口没有方法（Marker Interface），但是你可以用它来测试一个特定的集合是否支持高效的随机访问

Collection<Integer> c = new ArrayList<Integer>();
if (c instanceof RandomAccess)
{
        System.out.println("use random access algorithm -> like ArrayList");//fast access date
}
else
{
        System.out.println("use sequential access algorithm -> like LinkedList");//fast delete data 
}