Java集合04 - RandomAccess

绝地灬酷狼 2022-12-27 12:54 124阅读 0赞

**目录**

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)）快的多。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70]: /images/20221120/fa97c0ee8a504f9a85f47aab7002325f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1]: /images/20221120/2d1936f371764ce28024a985c804dfdc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2]: /images/20221120/7d28924198b54f77a9d0990662297f19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201211153756179.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70