RandomAccess接口 / 开普饭

RandomAccess接口的作用
算法的差异

序言：许多人看完，ArrayList源码后，自我感觉良好，一问 RandomAccess 这玩意干嘛的，一脸懵，

所以今天来盘盘这个接口

RandomAccess接口的作用

咱先看看官方怎么介绍这个接口的，摘自注释

译：这个接口是被用来List实现的标记接口，支持快速随机访问，且只要你实现了它，你使用for循环遍历，效率会高于迭代器的遍历（说明一下，这里说的 for 循环是普通循环,而增强 for-each 本质就等同于迭代器遍历）

  //避免自动装箱拆箱影响,不声明泛型
        List list = new ArrayList<>();
        int total = 40000000;
        for (int i = 0; i<total; i++){
            list.add(i);
        }
        //1.使用普通for循环的效率
        long start1 = System.currentTimeMillis();
        for(int i = 0; i < total; i++){
            Object temp  = list.get(i);
        }
        long end1 = System.currentTimeMillis();
        System.out.println("普通循环的时间效率:" + (end1 - start1));
        //2.使用迭代器的循环效率
        long start2 = System.currentTimeMillis();
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            Object temp = iterator.next();
        }
        long end2 = System.currentTimeMillis();
        System.out.println("迭代器循环的时间效率:" + (end2 - start2));
        //3.使用增强for循环（其实底层也是用迭代器玩的）
        long start3 = System.currentTimeMillis();
        for(Object num: list){
            Object temp = num;
        }
        long end3 = System.currentTimeMillis();
        System.out.println("增强for循环的时间效率:" + (end3 - start3));

这里的随机访问，就是能够随机的访问 List 中的任何一个元素，不要想多

虽然所有的 List 实现都支持随机访问，只是由于数据结构不同，导致访问效率不同。但是这里的快速随机访问，不是所有 List 集合能干的。

ArrayList，底层为数组，有下标，指哪打哪，随机访问效率 O(1)
LinkedList，底层为链表，访问一个元素，需要遍历，随机访问效率 O(n)

所以 ArrayList 实现了 RandomAccess，LinkedList 则没有

实现了 RandomAccess 的接口有：

ArrayList
Vector
CopyOnWriteArrayList
RandomAccessSubList
UnmodifiableArrayList

可能你看到这，又有疑问了，我知道这个接口是标志接口了，实现了它就能快速随机访问，所以它有什么用？

在上文中，我们通过测试发现只要实现了这个接口，普通 for 循环的效率要高于迭代器，所以你可能会说在追求效率的时候我全用普通 for循环就行了，这个接口的作用还是没有凸显出来。

那么下面我们看这样一个测试, 这次测试对象为 LinkedList。

//注意这次我们使用双线链表LinkedList
        List list = new LinkedList();
        int total = 100000;
        for (int i = 0; i<total; i++){
            list.add(i);
        }
        //1.使用普通for循环的效率
        long start1 = System.currentTimeMillis();
        for(int i = 0; i < total; i++){
            Object temp  = list.get(i);
        }
        long end1 = System.currentTimeMillis();
        System.out.println("普通循环的时间效率:" + (end1 - start1));
        //2.使用迭代器的循环效率
        long start2 = System.currentTimeMillis();
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            Object temp = iterator.next();
        }
        long end2 = System.currentTimeMillis();
        System.out.println("迭代器循环的时间效率:" + (end2 - start2));

明白了不，不同 List 集合使用不同的遍历方式，效率完完全全不一样，不是使用谁效率就一定高，得看对象是谁

所以如果你有这么个诉求，你有个List 对象 A，但是它可能是 LinkedList，可能是ArrayList，也可能是 CopyOnWriteArrayList，但是你就想它是以最高效率去遍历的，这个时候你可以根据这个RandomAccess 去决定以哪种方式去遍历

if(A instanceof RandomAccess){
    //使用普通for循环遍历
} else {
    //使用迭代器遍历
}

算法的差异

上文我们提到有没有实现 RandomAccess接口，会导致不同的集合采取不同的遍历方式，会有不一样的访问效率。但是为什么会这样呢，底层是怎么做的

我们看一下 java.util.Collections#binarySearch

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

我们可以看到，在进行二分查找时，会进行判断是否实现了 RandomAccess接口从而采取不一样的遍历方式

所以看到这你应该明白了，数据结构决定了算法的根本，RandomAccess接口仅仅是个标志接口

不仅是二分查找，底层的普通遍历也会根据其数据结构选择相应的执行策略，选对了和数据结构相性匹配的策略当然就快了

总结：数据结构决定算法

RandomAccess接口

RandomAccess接口的作用

算法的差异

相关推荐