Collection

橘子君丶

发布于 2023-10-20 19:08:31

820

发布于 2023-10-20 19:08:31

文章被收录于专栏：springBoot3.0springBoot3.0

关于RandomAccess的讨论

在阅读Collectios类源码时，发现一些方法常常出现list instanceof RandomAccess的字样，下面以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);
    }//instanceof用来判断某对象是否为某个类或者接口类型

有了这个限制条件之后返回的方法又有什么区别呢？

下面分别来看indexedBinarySearch和iteratorBinarySearch的源码

indexedBinarySearch

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
   }


iteratorBinarySearch
   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集合一般采用Iterator循环遍历，实现接口的则采用for循环遍历。那么两者性能的区别在哪呢？

下面给出答案：ArrayList用for循环遍历比iterator迭代器遍历快，LinkedList用iterator迭代器遍历比for循环遍历快。

详细编码来自：https://blog.csdn.net/weixin_39148512/article/details/79234817

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

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

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

总结：RandomAccess虽然是个空接口，但通过这个接口可以判断时ArrayList还是LinkedList，从而选择更好的循环遍历方法，提高性能。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-02-24T，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历