Java集合04 - RandomAccess-蒲公英云

Java集合04 - RandomAccess

1.什么是RandomAccess

2.RandomAccess具体实现

3.两种遍历方法性能测试

笔者JDK版本：1.8.0_202

1.什么是RandomAccess

   RandomAccess和Cloneable、Serializable接口一样，本质上都是一种标志性接口，无具体实现，意在告知JVM此类(在恒定时间内)可支持快速随机访问。源码中一大段话翻译过来讲了这么几件事：
 （1）给List使用的标记型接口，目的是使其支持（在恒定时间内）的快速随机访问
 （2）推荐在遍历集合的时候检查该List是否实现了RandomAccess接口，以便让不同的集合使用更优的遍历算法（ArrayList用for循环遍历快一些，LinkedList用迭代器遍历快一些）
 （3）通常来说，如果一个List用for循环遍历比用迭代器遍历的速度快，那么推荐实现RandomAccess接口

2.RandomAccess具体实现

   Java中的Collectons类提供了静态操作集合的方法，一起看下Collectons中对RandomAccess接口的判断：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2

   如果这个集合实现了RandomAccess接口或者集合大小小于二分查找阀值时，按下标二分查找，否则使用迭代器实现二分查找，对应源码中说到的第2点和第3点。

3.两种遍历方法性能测试

DEMO：

private static void computingTime(List list) {
        long startTime;
        long endTime;
        if (list instanceof RandomAccess) {
            System.out.println(list.getClass() + "实现了RandomAccess接口");
        } else {
            System.out.println(list.getClass() + "未实现RandomAccess接口");
        }
        startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("采用for循环的方式遍历集合耗时：" + (endTime - startTime) + "ms");
        startTime = System.currentTimeMillis();
        for (Iterator iter = list.iterator(); iter.hasNext(); ) {
            Object o = iter.next();
        }
        endTime = System.currentTimeMillis();
        System.out.println("采用迭代器的方式遍历集合耗时：" + (endTime - startTime) + "ms");
}
public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        int listSize = 100000;
        for (int i = 0; i < listSize; i++) {
            arrayList.add(i);
        }
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < listSize; i++) {
            linkedList.add(i);
        }
        computingTime(arrayList);
        computingTime(linkedList);
}

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3

   测试demo很简单，10W条数据存入ArrayList和LinkedList后，分别用for循环和迭代器来遍历这两个集合记录遍历时间。通过结果可知，ArrayList for循环遍历的时间小于迭代器遍历时间，而LinkedList for循环遍历的时间选超迭代器遍历时间。原因就和这两个集合的底层实现有关了（在接下来的文章内会详谈），ArrayList底层动态扩容数组，查询时间复杂度O(1)，所以两种方式遍历区别不大，快速随机访问略胜一筹；而LinkedList底层基于双向循环链表，因为链表的特性，迭代器查找比快速随机访问（时间复杂度O(n)）快的多。