ArrayList 为什么要实现 RandomAccess?

JAVA herman 47浏览

ArrayList 可能是大家使用最频繁的一个集合了,但是很多人对它熟悉而又陌生,结合我前面的《一个 ArrayList 就能让你面试到哭!》这篇文章,今天我们一起来讨论讨论 ArrayList 为什么要实现 RandomAccess 这个接口!

ArrayList

查看 ArrayList 的源码你会发现它的底层就是一个数组,然而它有实现了 RandomAccess 接口。

RandomAccess

我们先来看看 RandomAccess 接口是干什么的?

从源码中得知,RandomAccess 是一个空接口。查阅 java 官方文档得知,RandomAccess 是 List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

看重点,RandomAccess 是一个标记接口。什么意思呢?你看 Serializable 接口你就明白了。

第二个重点是,实现 RandomAccess 接口的集合支持快速(通常是固定时间)随机访问。

这句话好像是一句废话,为什么呢?因为我们开头说了 ArrayList 底层是一个数组。数组的特性就是支持下标(索引)快速访问。你现在用了 RandomAccess 接口能让 ArrayList 有更快的访问速度?

找不到答案,那我们就接着往下看!

此接口(RandomAccess)的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

哦,到现在你可能明白了,实现 RandomAccess 接口是允许一般的算法更改其行为。

那既然明白了它的作用,但是我还想知道,这个算法行为是什么时间被更改的。为什么 LinkedList 没有实现这个接口?

带着这个疑问,我查看了 JDK 的相关源码,结果有了重大发现!

Collections

Java 中还有一个重要的 Collections 类。这个类从一开始就被我们忽略了,我在 Collections 类的排序算法源码找到下面的代码:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key){
    if(list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else // 业余草:www.xttblog.com
        return Collections.iteratorBinarySearch(list, key);
}

BINARYSEARCH_THRESHOLD 的值是5000。

上面代码的意思是 List 的大小少于 5000 或者 list 实现了 RandomAccess, 就采用 index 的方式遍历, 反之就采用 iterator 的方式遍历。

重点是这句代码:list instanceof RandomAccess。

ArrayList 实现了 RandomAccess 接口,所以它的排序算法之类的,就不会采用 iterator 迭代器的方式去遍历。

用了迭代器的方式去遍历 ArrayList ,反而速度会慢!

不行大家自己去用下面两种方式遍历 ArrayList 试一试,看看它们的耗时分别是多少?

for (int i = 0;i < list.size();i++){
    System.out.println(list.get(i));
}
// 业余草:www.xttblog.com
Iterator it = list.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

以 3w 条数据为例,测试结果发现 ArrayList: for 循环遍历耗时: 3 迭代器遍历时间: 7。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847,QQ3群:187424846。QQ群进群密码:xttblog,想加微信群的朋友,可以微信搜索:xmtxtt,备注:“xttblog”,添加助理微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » ArrayList 为什么要实现 RandomAccess?