RandomAccess接口的作用-蒲公英云

RandomAccess接口的作用

通过源码我们得知该RandomAccess是一个空的接口？为什么是空的接口呢？那它的作用到底是用来干嘛的呢？又有谁实现了它呢？实现这个接口又有什么用呢？

带着问题我们先来看djk的注释信息：这是一个标记接口，标识实现这个接口(在恒定时间内)可以支持快速随机访问…，文档中还提到了ArrayList和LinkedList，那我们去分别看下它们的源码，发现ArrayList实现了该接口，而LinkedList却没有实现该接口。
RandomAccess接口
可以看到ArrayList接口实现了该接口：

而LinkedList接口没有实现该接口：

我们知道Collection是集合的顶级接口，它封装了一系列对集合操作的通用方法，例如add(),remove(),isEmpty(),size()…等方法，而ArrayList则间接地实现了该接口；
附一张很久之前收藏的一张图片(我真的找不到出处了,如有侵权请联系撤销)：
在这里插入图片描述
而Collections则是封装了一系列对集合遍历、排序、线程安全化等操作。既然如此，那我们就去Collections里看看ArrayList是实现了RandomAccess接口后是如何进行快速随机访问的。

通过Collections的binarySearch()方法我们可以看到里面有用到RandomAccess，它先判断集合是否实现了RandomAccess从而判断是使用indexedBinarySearch()方法还是iteratorBinarySearch()方法，也就是说这两个方法才是决定ArrayList是如何进行快速随机访问的关键，那接下来我们就去看下这两个个方法的区别；

乍一看好像一样，但是它们取值的方式不一样，一个是通过索引遍历，一个是通过iterator迭代器遍历，难道是循环遍历比迭代器速度快吗？
那我们接下来实验对比一下
在这里插入图片描述
ArrayList和LinkedList各自循环遍历和迭代器遍历性能大比拼：

//10000条数据测试结果: for循环遍历下：ArrayList速度远大于LinkedList，迭代器遍历下：LinkedList速度稍快于ArrayList
注：我试了下10W条数据测试，LinkedList进行for循环遍历需要3-4秒左右, 其他性能变换不大
在这里插入图片描述

//ArrayList 10000条数据测试：
在这里插入图片描述
//LinkedList 10000条数据测试：

稍微总结一下，这次测试我参考了其他朋友的博客，结果基本一致，那最后我们也明白RandomAccess接口是如何让ArrayList进行快速随机访问的了，其实就是判断list是否实现了该接口，从而选取特定的遍历方式；

那问题又来了QAQ，为什么ArrayList的遍历中for比Iterator快，而LinkedList中却是Iterator远快于for？

ArrayList是数组结构，长度是可变的，原理是（创新数组+复制数组），查询快(时间复杂度是O(1))，增删慢，不同步。ArrayList不是线程安全的，只能用在单线程环境下，多线程可以考虑Collections.synchronizedList函数返回一个线程安全的ArrayList类，或者使用Concurrent并发包下对应的集合类
LinkedList的底层实现则是基于双向循环链表实现的，是链表结构，不同步的，增删速度快(时间复杂度为O(1))，查询较慢(时间复杂度却是O(n))。由于实现了Queue接口，因此也可以用于实现堆栈，队列。