由于在面试中遭遇毒打，今天准备重新夯实基础，开始从Java集合中最常用的ArrayList开始看起，然后就发现了一个没见过的接口RandomAccess，点进去一看，还是个空的，对于一个优秀的CV工程师来说，面向搜索引擎开发必然是驾轻就熟，一番搜索下来，发现了其中的奥秘。
RandomAccess是一个标记接口，只要实现了这个接口，就意味着支持随机存取，像ArrayList底层是数组，数组在内存中是连续的，天然便支持随机存取，而像LinkedList底层是双向链表，数据在内存中不连续，所以不支持随机存取，打开LinkedList的源码，发现并没有实现RandomAccess接口。
在了解了RandomAccess的含义后，就得谈谈他的使用场景了。
Collections是一个集合工具类，在Collections中，就有RandomAccess的应用，在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
return Collections.iteratorBinarySearch(list, key);
}
可以看出，方法里内对List是否实现了RandomAccess接口进行了判断，如果实现了，则执行indexedBinarySearch方法，否则，则执行iteratorBinarySearch方法。仔细研究了一下这两个方法，总结下来就是，实现了RandomAccess接口的List使用索引遍历，而没实现的则采用迭代器进行遍历，至于为什么这么设计，那就要涉及到不同集合使用索引遍历喝使用迭代器遍历的性能差异了。
用经典的ArrayList和LinkedList来做对比，口说无凭，来一份测试代码，遍历十万条数据
public class Test {
public static final List<Integer> arrayList = new ArrayList<>();
public static final List<Integer> linkedList = new LinkedList<>();
public static void init() {
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
linkedList.add(i);
}
}
public static void main(String[] args) {
init();
arrayListByIndexed();
arrayListByIterator();
linkedListByIndexed();
linkedListByIterator();
}
//计算ArrayList通过for遍历时间
public static void arrayListByIndexed() {
StopWatch stopWatch = new StopWatch();
stopWatch.start();
for (int i = 0; i < arrayList.size(); i++) {
arrayList.get(i);
}
stopWatch.stop();
System.out.println("ArrayList使用for遍历时间：" + stopWatch.getTotalTimeMillis());
}
//计算ArrayList通过Iterator遍历时间
public static void arrayListByIterator() {
StopWatch stopWatch = new StopWatch();
stopWatch.start();
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
iterator.next();
}
stopWatch.stop();
System.out.println("ArrayList使用Iterator遍历时间：" + stopWatch.getTotalTimeMillis());
}
//计算ArrayList通过for遍历时间
public static void linkedListByIndexed() {
StopWatch stopWatch = new StopWatch();
stopWatch.start();
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i);
}
stopWatch.stop();
System.out.println("LinkedList使用for遍历时间：" + stopWatch.getTotalTimeMillis());
}
//计算ArrayList通过Iterator遍历时间
public static void linkedListByIterator() {
StopWatch stopWatch = new StopWatch();
stopWatch.start();
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()) {
iterator.next();
}
stopWatch.stop();
System.out.println("LinkedList使用Iterator遍历时间：" + stopWatch.getTotalTimeMillis());
}
}
运行结果如下：
ArrayList使用for遍历时间：5
ArrayList使用Iterator遍历时间：6
LinkedList使用for遍历时间：4637
LinkedList使用Iterator遍历时间：5
通过分析测试结果，我们可以发现，在ArrayList中使用for遍历比迭代器稍快一些，而在LinkedList中，迭代器的遍历速度远远快于for遍历，所以我们在实际应用中，要考虑使用List接口的哪种实现类，可以更好更高效的满足实际场景需求。所以在这里通过实现RandomAccess接口来区分List的哪种实现类。
