RandomAccess接口的作用

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

RandomAccess接口-LMLPHP

译:这个接口是被用来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));

RandomAccess接口-LMLPHP

这里的随机访问,就是能够随机的访问 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));

RandomAccess接口-LMLPHP

明白了不,不同 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接口 仅仅是个标志接口

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

总结:数据结构决定算法

12-01 12:14