巧用RandomAccess接口，集合遍历性能提升几十倍

我是陈皮，一个在互联网 Coding 的 ITer，微信搜索「陈皮的JavaLib」第一时间阅读最新文章，回复【资料】，即可获得我精心整理的技术资料，电子书籍，一线大厂面试资料和优秀简历模板。

前言

假设让你定义一个方法，供他人调用，它的功能是遍历传入的集合，你会怎么实现？方法定义如下：

private void traverse(List<Integer> list) {
     
}

方案一，使用for循环下标定位获取集合元素？

private void traverse(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        list.get(i);
    }
}

方案二，使用迭代器来获取集合元素？

private void traverse(List<Integer> list) {
    for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
        iterator.next();
    }
}

方案验证

针对上述提出的2种方案，我们进行验证，因为我们开发中经常使用的List实现类是ArrayList和LinkedList。所以验证传入这2种集合类型时，验证集合遍历性能。

package com.nobody;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description
 * @Author Mr.nobody
 * @Date 2021/4/25
 * @Version 1.0
 */
public class Demo {
    public static void main(String[] args) {
		// 集合大小
        int ListSize = 200000;
		// 初始化ArrayList集合
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < ListSize; i++) {
            arrayList.add(i);
        }
        System.out.println("ArrayList Type：");
        traverseWithFor(arrayList);
        traverseWithIterator(arrayList);

		// 初始化LinkedList集合
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < ListSize; i++) {
            linkedList.add(i);
        }
        System.out.println("LinkedList Type：");
        traverseWithFor(linkedList);
        traverseWithIterator(linkedList);
    }

    private static void traverseWithFor(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            list.get(i);
        }
        System.out.println("traverseWithFor:" + (System.currentTimeMillis() - startTime));
    }

    private static void traverseWithIterator(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
            iterator.next();
        }
        System.out.println("traverseWithIterator:" + (System.currentTimeMillis() - startTime));
    }
}

输出结果如下，发现集合类型是ArrayList时，使用for下标定位（方案一）遍历集合效率更高；集合类型是LinkedList时，使用迭代器（方案二）遍历集合效率更高。特别地，如果LinkedList集合量很大并且使用for下标遍历，效率极其差。

ArrayList Type：
traverseWithFor:9
traverseWithIterator:15

LinkedList Type：
traverseWithFor:35548
traverseWithIterator:12

RandomAccess 接口

通过以上验证，发现不能单纯的使用其中一种方案来遍历传入的集合，因为传入参数的List的实现类是未知的。那我们可以判断传入参数的具体实现类，来决定使用哪种遍历算法不就可以了。

private static void traverse(List<Integer> list) {
    if (list instanceof ArrayList) {
        for (int i = 0; i < list.size(); i++) {
            list.get(i);
        }
    } else if (list instanceof LinkedList) {
        for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
            iterator.next();
        }
    }
}

以上是比较理想化的情况，如果List的实现类随着时间，会增多或者减少，那岂不是要经常修改此方法，增加或者减少instanceof的条件判断？

所以在JDK1.4之后，出现了RandomAccess接口，它是一个空的标记接口。

package java.util;

public interface RandomAccess {
}

它的作用是，如果一个集合的实现类实现了此标记接口，表明此实现类支持快速随机访问（通常是固定时间）。RandomAccess 接口的主要目的是允许一般的算法能更改其行为，从而在随机或连续访问列表时能提供良好的性能。

通俗讲，就是在随机访问或者顺序遍历集合时候，我们可以根据集合实现类是否实现了RandomAccess接口，来决定使用不同的遍历策略。官方鼓励，对于那些遍历呈现线性访问时间，而且随机访问是固定时间的集合类，推荐实现RandomAccess接口。

例如ArrayList类实现了RandomAccess接口，LinkedList类是没有实现RandomAccess接口的。

官方也说明了，如果集合类实现了RandomAccess接口，推荐使用for (int i=0, n=list.size(); i < n; i++)遍历，避免使用Iterator迭代器遍历集合。反之，如果集合类是Sequence List（例如LinkedList），则推荐使用迭代器。

package com.nobody;

import java.util.*;

/**
 * @Description
 * @Author Mr.nobody
 * @Date 2021/4/25
 * @Version 1.0
 */
public class Demo {
    public static void main(String[] args) {

        // 集合大小
        int ListSize = 200000;
        // 初始化ArrayList集合
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < ListSize; i++) {
            arrayList.add(i);
        }
        System.out.println("ArrayList Type：");
        traverseWithFor(arrayList);
        traverseWithIterator(arrayList);
        traverse(arrayList);

        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < ListSize; i++) {
            linkedList.add(i);
        }
        System.out.println("LinkedList Type：");
        traverseWithFor(linkedList);
        traverseWithIterator(linkedList);
        traverse(linkedList);
    }

    private static void traverseWithFor(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            list.get(i);
        }
        System.out.println("traverseWithFor:" + (System.currentTimeMillis() - startTime));
    }

    private static void traverseWithIterator(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
            iterator.next();
        }
        System.out.println("traverseWithIterator:" + (System.currentTimeMillis() - startTime));
    }
    
    private static void traverse(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        if (list instanceof RandomAccess) {
            for (int i = 0; i < list.size(); i++) {
                list.get(i);
            }
        } else {
            for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
                iterator.next();
            }
        }
        System.out.println("traverse:" + (System.currentTimeMillis() - startTime));
    }
}

输出结果如下，发现巧用了RandomAccess之后，无论是List的哪个实现类，遍历集合都能获得很好的性能。

ArrayList Type：
traverseWithFor:12
traverseWithIterator:15
traverse:12

LinkedList Type：
traverseWithFor:27189
traverseWithIterator:6
traverse:7

总结

• 如果一个List的实现类实现了RandomAccess标记接口，表明此实现类支持快速随机访问（通常是固定时间）。RandomAccess接口的主要目的是允许一般的算法能更改其行为，从而在随机或连续访问列表时能提供良好的性能。
• 官方鼓励，对于那些遍历呈现线性访问时间，而且随机访问是固定时间的集合类，推荐实现RandomAccess接口。
• 如果集合类实现了RandomAccess接口，推荐使用for (int i=0, n=list.size(); i < n; i++)遍历，反之使用Iterator迭代器遍历集合。
• 不过现在机器性能很高了，对于集合大小很小的情况下，其实2种遍历方案性能差不多，如果数据量极大则可以根据情况进行决策。简而言之就是因材施教，切不可盲目滥用。