RandomAccess接口

背景说明

也是最近在看JDK源码，看到List集合部分的时候看到实现哪些接口的时候，发现List、ArrayList都实现了一个叫RandomAccess的接口，最主要的是这个接口居然没有定义任何方法，是一个空接口，引发了我的好奇心，难道是JDK源码的开发人员多此一举，显然不是的。在进一步了解了RandomAccess接口之后发现其表面上确实没有实际的意义，但是在程序性能优化时它却是可以给我一些启发的，所以简单记录下。

RandomAccess介绍

RandomAccess接口是一个标识接口，本身并没有提供任何方法，任何实现它的对象都可以认为是支持随机访问的对象。此接口的主要目的时标识那些可支持快速随机访问的List实现。
在JDK的实现中，任何一个基于数组的List实现都实现了RandomAccess接口，而基于链表的实现则都没有。从定义上看RandomAccess是随机访问的意思，所以这就好理解了，因为只有数组能够进行快速的随机访问，而对链表的随机访问需要进行链表的遍历。因此，此接口的好处是，可以在应用程序中知道着呢该在处理的List对象是否可以进行快速随机访问，从而对不同的List进行不同的操作，以提高程序性能。

我们先来看一段测试代码：

    @Test
    public void test() {
        List<Integer> list = new ArrayList<>();
//        List<Integer> list = new LinkedList<>();
        for (int i = 0; i<10000000; i++){
            list.add(i);
        }

        Object o;
        StopWatch watch = new StopWatch("ArrayList random access get value start ....");
        watch.start();
        for (int i=0, n = list.size(); i<n; i++){
            o = list.get(i);
        }
        watch.stop();
        System.out.println("ArrayList random access get value cost:"+watch.getTotalTimeMillis());

        StopWatch watch2 = new StopWatch("ArrayList iterator get value start ....");
        watch2.start();
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            o = iterator.next();
        }
        watch2.stop();
        System.out.println("ArrayList iterator get value cost:"+watch2.getTotalTimeMillis());
    }

代码运行结果：

ArrayList random access get value cost:18
ArrayList iterator get value cost:25

结果分析：同样一个List在数据量较多时，for循环中get（int index）即对list的每一个元素进行随机取值的方式要比顺序遍历的方式用时要短，在大数据量的前提下使用快速取值的方式性能可以提升约10%，典型的实现RandomAccess接口的List又ArrayList和Vector，没有实现RandomAccess接口的List则以LinkedList为代表。

那可能有人会有疑问说我平时对于List遍历我都是采用随机取值的方式，几乎不用Iterator遍历器取值的。OK，那我们再来看一段测试代码：

@Test
    public void test() {
        List<Integer> list = new LinkedList<>(); //注意这次我们使用双线链表LinkedList
        for (int i = 0; i<10000; i++){
            list.add(i);
        }

        Object o;
        StopWatch watch = new StopWatch("LinkedList random access get value start ....");
        watch.start();
        for (int i=0, n = list.size(); i<n; i++){
            o = list.get(i);
        }
        watch.stop();
        System.out.println("LinkedList random access get value cost:"+watch.getTotalTimeMillis());

        StopWatch watch2 = new StopWatch("LinkedList iterator get value start ....");
        watch2.start();
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            o = iterator.next();
        }
        watch2.stop();
        System.out.println("LinkedList iterator get value cost:"+watch2.getTotalTimeMillis());
    }

程序运行结果：

LinkedList random access get value cost:88
LinkedList iterator get value cost:2

显然如果你使用的时双线链表，那iterator 的效果会高出几十倍。那这种情况下可能你又会说那我如果使用LinkedList的话，取值我肯定使用遍历器呀，那不是也没有问题吗。

那么问题又来了，如果有一种场景，比如程序运行过程中需要取值，而你只知道数据时是使用List来保存的，而具体是ArrayList、LinkedList还是Vector你并不能确定的情况下如何选择取值（或者就我们这里的遍历）方式呢？？？

如果这里你的数据量不大，那么选用哪种方式问题可能都不大，但是如果在数据量很大的前提下你的取值方式将直接影响到程序的性能甚至会造成严重的后果。这个时候我们的主题RandomAccess就可以派上用场了，怎么用？
其实很简单：

 if (list instanceof RandomAccess) {
      // 使用随机取值，即根据下标取值方式
} else {
     // Iterator遍历器取值
}

我们在取值之前做一层判断即可，如果是继承了RandomAccess的List（即支持随机访问）我们则使用随机取值方式，反之则借助Iterator。这样不对目标容器是ArrayList、LinkedList还是Vector我们都可以保证程序的性能了。

结论

上述说到的不确定使用的那种List的场景确实不多，对于我们普通的开发人员做的事情，我们肯定都会很明确使用了具体那种List。所以需要提醒的是RandomAccess虽然可以知道List是否支持随机访问。但是如果应用程序需要通过索引下标对List做随机访问，尽量不要使用LinkedList，ArrayList和Vector都是不错的选择。