为什么ArrayList实现RandomAccess接口？

Question

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

那么在哪种情况下ArrayList,实施它有什么意义呢？

Answer 1

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

根据RandomAccess的JavaDoc:

List实现使用的标记接口,表示
它们支持快速(通常是恒定时间)随机访问.

有关更多信息,请查看两个JavaDoc页面.

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

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

Answer 2

RandomAccess接口没有方法

这称为标记接口,是一种称为标记接口模式的设计模式.

当我检查LinkedList时,它没有实现RandomAccess接口.那么在ArrayList的情况下,实现它有什么意义呢？

因为a中的随机访问LinkedList是O(n),而它是O(1)ArrayList.

它在文档中说明:

操作随机访问列表(例如ArrayList)的最佳算法在应用于顺序访问列表(例如LinkedList)时会产生二次行为

Answer 3

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

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

Answer 4

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

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

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

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