【基础】RandomAccess

　　在List集合中，我们经常会用到ArrayList以及LinkedList集合，但是通过查看源码，就会发现ArrayList实现RandomAccess接口，但是RandomAccess接口里面是空的！Linked并没有实现RandomAccess接口。

 

RandomAccess接口是一个标志接口（Marker）

List集合实现这个接口，就能支持快速随机访问

Collections类中的binarySearch（）方法，源码如下：

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);
    } 

 

indexedBinarySerach(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
    }

 

iteratorBinarySerach(list,key)源码：

 

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集合采用一般的for循环遍历，而未实现这接口则采用迭代器。

 

ArrayList用for循环遍历比iterator迭代器遍历快，LinkedList用iterator迭代器遍历比for循环遍历快，

所以说，当我们在做项目时，应该考虑到List集合的不同子类采用不同的遍历方式，能够提高性能！

然而有人发出疑问了，那怎么判断出接收的List子类是ArrayList还是LinkedList呢？

这时就需要用instanceof来判断List集合子类是否实现RandomAccess接口！

 

总结：RandomAccess接口这个空架子的存在，是为了能够更好地判断集合是否ArrayList或者LinkedList，从而能够更好选择更优的遍历方式，提高性能

转自：https://blog.csdn.net/weixin_39148512/article/details/79234817