首页 > 国际新闻

Java ArrayList 为什么要实现 RandomAccess 接口?

文章作者:来源:www.kuisparlay.com时间:2019-09-20



RandomAccess接口摘要

在我们的开发中,List接口是最常见的,但我们几乎每天都使用ArrayList或LinkedList,但仔细的学生发现ArrayList实现了RandomAccess接口,但LinkedList没有实现RandomAccess接口,这就是为什么?

公共类ArrayList扩展了AbstractList

实现List,RandomAccess,Cloneable,java.io.Serializable

公共类LinkedList

扩展AbstractSequentialList

实现List,Deque,Cloneable,java.io.Serializable

RandomAccess接口是空的,什么是RandomAccess接口?

公共接口RandomAccess {

}

RandomAccess是一个标记接口。官方解释是,只要List实现了这个接口,它就可以支持快速随机访问。什么是随机访问?让我们举个例子。

集合是一组工具,让我们看一下集合源中的二进制搜索方法。

公共静态

int二进制搜索(list<;扩展可比较的列表,t键){

if(列出随机访问列表的实例。大小())

返回集合。索引的binarysearch(list,key);

其他

返回集合。迭代器binarysearch(list,key);

}

从源代码中可以看到,确定列表是否是随机访问的实例,如果是,则执行索引的BinarySearch方法,如果不是,则执行迭代器BinarySearch方法。接下来,看看这两种方法。

私有静态

int indexed binarysearch(列表<;扩展可比较的列表,t键){

int低=0;

int high=列表。大小()-1;

同时(低<;=高){

int mid=(低+高)>;>;>;1;

Comparable Midval=列表。GeT(中);

int cmp=中间值。比较(键);

如果(cmp<;0)

低=中+1;

其他IF(CMP>;0)

高=中-1;

其他

返回mid;//找到键

}

返回-(low+1);//找不到键

}

私有静态

int迭代器binarysearch(list<;扩展可比较的列表,t键)

{ > <>

int低=0;

int high=列表。大小()-1;

列表迭代器<;扩展可比较的>;i=列表。ListIterator();

同时(低<;=高){

int mid=(低+高)>;>;>;1;

可比较的middval=get(i,mid);

int cmp=中间值。比较(键);

如果(cmp<;0)

低=中+ 1;

其他if(cmp> 0)

高=中 - 1;

其他

回到中间; //找到密钥

}

返回 - (低+ 1); //找不到钥匙

}

上述两种方法的源代码表示实现了随机访问列表接口使用索引遍历,而随机访问列表接口未使用迭代器遍历实现。那为什么这样设计呢?

现在涉及到二进制搜索的遍历操作,让我们分析ArrayList和LinkedList遍历元素的性能。

公共类集合测试{

Public static void main(String [] args){

Long arrayListIndexed Time=arrayListIndexed();

Long arrayListIteratorTime=arrayListIterator();

Long linkedListIndexedTime=linkedListIndexed();

Long linkedListIteratorTime=linkedListIterator();

系统。出来。println('test arraylist for traversal time:'+arraylistindexed time);''

系统。出来。println('test arraylist遍历迭代器的时间:'+arraylisteratorTime);''

系统。出来。println('test linkedlist for traversal time:'+linkedlistindexedtime);''

系统。出来。println('test linkedlist traversal time through iterator:'+linkedlisteratoratortime);''

}

//测试arraylist遍历

公共静态长数组索引()。{

list arraylist=new arraylist();

对于(int i=0;i<;;i++){

数组列表。添加(i);

}

//记录开始时间

长启动时间=系统。当前时间毫秒();

对于(int i=0;i<;arraylist。大小();i++){

数组列表。得到(i);

}

//结束录制时间

Long endTime=系统。 currentTimeMillis();

//遍历消耗时间

long resultTime=endTime - startTime;

结果时间;

}

//通过迭代器

测试ArrayList遍历的经过时间

Public static long arrayListIterator(){

列表arrayList=new ArrayList();

For(int I=0; I&lt; ; I ++){

数组列表。 add(i);

}

//记录开始时间

long startTime=系统。 currentTimeMillis();

Iterator iterator=arrayList。 iterator();

而(iterator。hasNext()){

迭代器。 next();

}

//结束录制时间

Long endTime=系统。 currentTimeMillis();

//遍历消耗时间

long resultTime=endTime - startTime;

结果时间;

}

//测试LinkedList遍历所用的时间

Public static long linkedListIndexed(){

列出linkedList=new LinkedList();

For(int I=0; I&lt; ; I ++){

LinkedList的。 add(i);

}

//记录开始时间

long startTime=系统。 currentTimeMillis();

For(int I=0; I&lt; linkedList。size(); i ++){

LinkedList的。得到(i);

}

//结束录制时间

Long endTime=系统。 currentTimeMillis();

//遍历消耗时间

long resultTime=endTime - startTime;

结果时间;

}

//测试LinkedList遍历迭代器所占用的时间

Public static long linkedListteterator(){

列出linkedList=new LinkedList();

For(int I=0; I&lt; ; I ++){

LinkedList的。 add(i);

}

//记录开始时间

long startTime=系统。 currentTimeMillis();

迭代器迭代器=linkedList。 iterator();

而(iterator。hasNext()){

迭代器。 next();

}

//结束录制时间

Long endTime=系统。 currentTimeMillis();

//遍历消耗时间

long resultTime=endTime - startTime;

结果时间;

}

}

测试结果如下。

测试用于遍历的ArrayList需要时间:1

通过迭代器测试ArrayList遍历所花费的时间:2

测试LinkedList的遍历需要时间:47

测试LinkedList遍历迭代器的时间:1

让我们分析测试结果:ArrayList比forpass遍历的迭代器遍历要快一些,而迭代器的LinkedList遍历比for遍历要快。

因此,在我们的应用程序中,我们应该考虑使用List接口的哪个实现类来更好地满足实际场景要求。所以这里是通过实现RandomAccess接口来实现List的哪个实现类。

最后,总结了一个句子:实现RandomAccess接口的List可以比使用迭代器遍历数据更有效地遍历for循环遍历数据。没有实现RandomAccess接口的List可以比使用for循环遍历数据更有效地遍历迭代器。

资料来源:

: -D搜索微信号(ID:斜坡源),可以获得各种Java源代码分析,原理说明,访谈问题,学习指南。

: -D此外,在回复[Book]之后,您可以从作品推荐的Java中获得100本书,从入门到架构。

: -D此外,在回复[Technology Group]之后,您可以加入专门从事Java,后端和体系结构的技术组。

来吧,骚年

——