为什么ArrayList实现RandomAccess接口

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

那么在ArrayList的情况下，实现它有什么意义呢？

没有方法的接口在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

RandomAccess接口没有方法

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

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

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

文档中有说明：

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

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

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

人们认识到，随机和顺序之间的区别访问往往是模糊的。例如，一些List实现提供渐近线性访问时间，如果它们变大，但不变实践中的访问时间。这种清单的执行一般应实现这个接口。根据经验，List实现如果类，这个循环：
for (int i=0, n=list.size(); i < n; i++)
list.get(i);   
比这个循环运行得更快：
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();

1)有两个类实现RandomAccess接口。它们是：

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

2)RandomAccess接口的目的是以相同的速度检索集合中的任何随机元素。示例：我收集了100万个对象。实现RandomAccess接口使您检索第10个元素和第17869个元素的时间相同。这使得CCD_ 12和CCD_。

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

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

List使用的标记接口实现，以表明它们支持快速(通常为常量时间)随机接入。此接口的主要目的是允许改变其行为以提供良好性能的通用算法当应用于随机或顺序访问列表时。随机存取List实现使用的标记接口，用于指示支持快速(通常为恒定时间)随机接入。初级该接口的目的是允许通用算法更改它们提供良好性能的行为随机或顺序访问列表。最佳算法操作随机访问列表(如ArrayList)可以产生应用于顺序访问列表时的二次行为(例如LinkedList)。

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

doc的另一部分通过提供两种不同的访问底层数据的方法来处理被认为是快速随机的，这很容易理解。快速随机访问意味着第一个在任何时候都比第二个运行得更快。

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

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

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

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

接口没有方法(Marker接口)，但您可以使用它来测试特定集合是否支持有效的随机访问

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 
}

标记接口的存在表明(或期望)实现类的特定行为。
因此，在我们的例子中，ArrayList实现了RandomAccess标记接口。
因此，ArrayList类的期望是，当客户端想要访问某个索引处的某个元素时，它应该对ArrayList类别的客户端产生RandomAccess行为。

那么，ArrayList是如何实现这种随机性的呢？

public E get(int index) {
rangeCheck(index); // to check for out of bounds index.
return elementData(index); // another method invocation
}
E elementData(int index) {
return (E) elementData[index]; // accesses internal array.
}
// following is the internal array , used by ArrayList
transient Object[] elementData; // non-private to simplify nested class access

现在，我们知道LinkedList还没有实现RandomAccess，因此，它不应该保证随机访问行为。让我们也检查下面的LinkedList代码，注意这里的for循环，所以，它是一个顺序访问。并观察逐位运算符技巧：size >> 1的意思是，大小除以2。所以，它基本上是检查指数是在上半场还是下半场。如果是在下半场，那么从头开始是有意义的。这是一个优化，好技巧。
`公共E get(int index){checkElementIndex(index)；return node(index).item；}
节点节点(int索引){//assert isElementIndex(index)；
```
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
```
}`

RandomAccess:此接口在Java 1.4版中引入。它标记了可以随机访问的列表的实现。它存在于java.util.RandomAccess中

List实现使用的标记接口，用于指示它们支持快速随机访问。

更准确地说，RandomAccess接口识别使用List.get()方法而不是使用Iterator.next()方法迭代更快的List实现

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

因为ArrayList&矢量是基于索引的&LinkedList在Double Linked List之后。

时间复杂性

ArrayList：Java中的ArrayList由数组支持。随机访问需要O(1)时间

get()–始终是一个恒定时间O(1)操作

LinkedListLinkedList是一种线性数据结构，由持有数据字段的节点和对另一个节点的引用组成。

get()–搜索一个元素需要O(n)时间

注意：ArrayList可以为您提供O(1)复杂度中的任何元素，因为数组具有随机访问属性。您可以直接访问任何索引，而无需遍历整个数组。

LinkedList具有顺序访问属性。它需要遍历每个元素才能到达给定的索引，因此从LinkedList中通过索引获取值的时间复杂度为O(N)。

RandomAccess：标记接口

java.util.RandomAccess-自JDK1.4以来，集合框架的成员。实现：ArrayList和CopyOnWriteArrayList。

用于数据的随机访问(基于索引)

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

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

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

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

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

有关详细信息，请参阅我的博客：
http://javaexplorer03.blogspot.in/2015/07/randomaccess-java.html

相关内容

最新更新

热门标签：