ArrayList 为什么要实现 RandomAccess 接口？

JavaFish

发布于 2020-01-14 15:04:08

4830

发布于 2020-01-14 15:04:08

文章被收录于专栏：狗哥的 Java 世界

题图：pexels

出处：https://dwz.cn/aqL14tuI

预计阅读时间：5.99分钟

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

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E> extends AbstractSequentialList<E>    
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

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

public interface RandomAccess {}

RandomAccess 接口

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

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

public static <T> int binarySearch
    (List<? extends Comparable<? super T>> 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 方法。** 接下来看一下这两个方法。

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

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

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> 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 <T> int iteratorBinarySearch
    (List<? extends Comparable<? super T>> list, T key){
    int low = 0;
    int high = list.size()-1;
    ListIterator<? extends Comparable<? super T>> i = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> 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() {
        List<Integer> 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() {
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            arrayList.add(i);
        }
        //记录开始时间
        long startTime = System.currentTimeMillis();
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        //记录结束时间
        long endTime = System.currentTimeMillis();
        //遍历消耗时间
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //测试LinkedList通过for遍历所消耗时间
    public static long linkedListIndexed() {
        List<Integer> 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() {
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 10000; i++) {
            linkedList.add(i);
        }
        //记录开始时间
        long startTime = System.currentTimeMillis();
        Iterator<Integer> 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 循环来遍历数据更高效。

-END-

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-01-04，如有侵权请联系 cloudcommunity@tencent.com 删除

access

编程算法

java

本文分享自一个优秀的废人微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

access

编程算法

java

登录后参与评论

0 条评论

热度