ArrayList为什么要实现RandomAccess接口？

点击上方“后端技术精选”，选择“置顶公众号”

技术文章第一时间送达！

作者：蔡先森_caiyq www.jianshu.com/p/3e2a9e4c9e01

www.jianshu.com/p/3e2a9e4c9e01

在我们的开发中，List接口是最常见不过，而且我们几乎每天都在用ArrayList或者LinkedList，但是细心的同学有没有发现，ArrayList中实现了RandomAccess接口，而LinkedList却没有实现RandomAccess接口，这是为什么呢？

public class ArrayListE extends AbstractListE
        implements ListE, RandomAccess, Cloneable, java.io.Serializable

public class LinkedListE
    extends AbstractSequentialListE
    implements ListE, DequeE, Cloneable, java.io.Serializable

RandomAccess接口中是空的，RandomAccess接口又是什么呢？

public interface RandomAccess {
}

RandomAccess接口

RandomAccess是一个标记接口，官方解释是只要List实现这个接口，就能支持快速随机访问。而什么是随机访问呢？接下来我们来举例说明。

Collections是集合的一个工具类，我们看一下Collections源码中的二分搜索方法。

public static 
    int binarySearch(List? extends Comparable? super  list, T key) {
        if (list instanceof RandomAccess || list.size()BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

在源码中可以看出，判断list是否是RandomAccess的实例，如果是，则执行indexedBinarySearch方法，如果不是，则执行iteratorBinarySearch方法。接下来看一下这两个方法。

private static 
    int indexedBinarySearch(List? extends Comparable? super  list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low = high) {
            int mid = (low + high)  1;
            Comparable? super  midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp  0)
                low = mid + 1;
            else if (cmp  0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

private static 
    int iteratorBinarySearch(List? extends Comparable? super  list, T key)
    {
        int low = 0;
        int high = list.size()-1;
        ListIterator? extends Comparable? super  i = list.listIterator();

        while (low = high) {
            int mid = (low + high)  1;
            Comparable? super  midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp  0)
                low = mid + 1;
            else if (cmp  0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

上述两个方法的源码表示，实现了RandomAccess接口的List使用索引遍历，而未实现RandomAccess接口的List使用迭代器遍历。那么为什么要这么设计呢？

既然涉及到二分搜索的遍历操作，那么现在我们来分析一下ArrayList和LinkedList遍历元素的性能如何？

public class CollectionTest {
    public static void main(String[] args){
        long arrayListIndexedTime = arrayListIndexed();
        long arrayListIteratorTime = arrayListIterator();
        long linkedListIndexedTime = linkedListIndexed();
        long linkedListIteratorTime = linkedListIterator();
        System.out.println("测试ArrayList通过for遍历所消耗时间：" + arrayListIndexedTime);
        System.out.println("测试ArrayList通过iterator遍历所消耗时间：" + arrayListIteratorTime);
        System.out.println("测试LinkedList通过for遍历所消耗时间：" + linkedListIndexedTime);
        System.out.println("测试LinkedList通过iterator遍历所消耗时间：" + linkedListIteratorTime);
    }

    //测试ArrayList通过for遍历所消耗时间
    public static long arrayListIndexed() {
        ListInteger arrayList = new ArrayList();
        for (int i = 0; i  10000; i++) {
            arrayList.add(i);
        }
        //记录开始时间
        long startTime = System.currentTimeMillis();
        for (int i = 0; i  arrayList.size(); i++) {
            arrayList.get(i);
        }
        //记录结束时间
        long endTime = System.currentTimeMillis();
        //遍历消耗时间
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //测试ArrayList通过iterator遍历所消耗时间
    public static long arrayListIterator() {
        ListInteger arrayList = new ArrayList();
        for (int i = 0; i  10000; i++) {
            arrayList.add(i);
        }
        //记录开始时间
        long startTime = System.currentTimeMillis();
        IteratorInteger iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        //记录结束时间
        long endTime = System.currentTimeMillis();
        //遍历消耗时间
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //测试LinkedList通过for遍历所消耗时间
    public static long linkedListIndexed() {
        ListInteger linkedList = new LinkedList();
        for (int i = 0; i  10000; i++) {
            linkedList.add(i);
        }
        //记录开始时间
        long startTime = System.currentTimeMillis();
        for (int i = 0; i  linkedList.size(); i++) {
            linkedList.get(i);
        }
        //记录结束时间
        long endTime = System.currentTimeMillis();
        //遍历消耗时间
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //测试LinkedList通过iterator遍历所消耗时间
    public static long linkedListIterator() {
        ListInteger linkedList = new LinkedList();
        for (int i = 0; i  10000; i++) {
            linkedList.add(i);
        }
        //记录开始时间
        long startTime = System.currentTimeMillis();
        IteratorInteger iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        //记录结束时间
        long endTime = System.currentTimeMillis();
        //遍历消耗时间
        long resultTime = endTime - startTime;
        return resultTime;
    }
}

测试结果如下

测试ArrayList通过for遍历所消耗时间：1 测试ArrayList通过iterator遍历所消耗时间：2 测试LinkedList通过for遍历所消耗时间：47 测试LinkedList通过iterator遍历所消耗时间：1

我们来分析一下测试结果：ArrayList通过for遍历比通过iterator遍历要稍快，LinkedList通过iterator遍历比通过for遍历要快。

所以说在我们的应用中，要考虑使用List接口的哪种实现类，可以更好更高效的满足实际场景需求。所以在这里通过实现RandomAccess接口来区分List的哪种实现类。

最后总结一句话：实现RandomAccess接口的List可以通过for循环来遍历数据比使用iterator遍历数据更高效，未实现RandomAccess接口的List可以通过iterator遍历数据比使用for循环来遍历数据更高效。

推荐阅读(点击即可跳转阅读)

1. SpringBoot内容聚合

**2. **面试题内容聚合

**3. **设计模式内容聚合

**4. **Mybatis内容聚合

**5. **多线程内容聚合

原文始发于微信公众号（后端技术精选）：ArrayList为什么要实现RandomAccess接口？