对啊,我就是认定你不知道ArrayList为什么要实现RandomAccess接口!

来自:蔡先森_caiyq

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

public class ArrayList<Eextends AbstractList<E>
        implements List<E>, RandomAccessCloneablejava.io.Serializable
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneablejava.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方法。接下来看一下这两个方法。

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循环来遍历数据更高效。


推荐↓↓↓
Java编程
上一篇:e.printStackTrace()导致的锁死 下一篇:从Servlet、Dubbo、Mybatis聊聊责任链究竟怎么用