JDK源码解析之Java.util.Collections

栗筝i

发布于 2022-12-01 20:23:03

2420

发布于 2022-12-01 20:23:03

文章被收录于专栏：迁移内容迁移内容

java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类,服务于Java的Collection框架。

一、源码解析

1、不可实例化

  	private Collections() {}

Collections是util包中一个不可实例化的类。

2、优化参数

    private static final int BINARYSEARCH_THRESHOLD   = 5000;
    private static final int REVERSE_THRESHOLD        =   18;
    private static final int SHUFFLE_THRESHOLD        =    5;
    private static final int FILL_THRESHOLD           =   25;
    private static final int ROTATE_THRESHOLD         =  100;
    private static final int COPY_THRESHOLD           =   10;
    private static final int REPLACEALL_THRESHOLD     =   11;
    private static final int INDEXOFSUBLIST_THRESHOLD =   35;

Collecions定义的这些变量叫做优化参数(Tuning Parameter)，其作用在于优化类中方法的性能(permformance)。

3、排序函数sort()

3.1、根据元素的自然顺序对指定列表按升序进行排序

    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

参数：要排序的列表。

3.2、根据指定比较器产生的顺序对指定列表进行排序。此列表内的所有元素都必须可使用指定比较器相互比较。

    @SuppressWarnings({"unchecked", "rawtypes"})
    public static <T> void sort(List<T> list, Comparator<? super T> c) {
        list.sort(c);
    }

参数：list-要排序的列表；c-确定列表顺序的比较器。

3.3、关于list.sort方法

List.sort是JDK在1.8增加的方法

@SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

首先，传入一个比较器作为参数，然后就是将list转换成一个数组，再对这个数组进行排序，排序完之后，再利用iterator重新改变list。

4、二分查找方法binarySearch()

Collection中binarySearch及其相关的方法有很多，这里只选两个有代表性的

4.1、使用二分搜索法搜索指定列表，以获得指定对象，在进行此方法调用前比较要将列表元素按照升序排序，否则结果不确定，此方法会执行O(n)次链接遍历和O(log n)次元素比较。

    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-要搜索的链表，key-要搜索的键。

4.2、根据指定的比较器对列表进行升序排序。

    public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        if (c==null)
            return binarySearch((List<? extends Comparable<? super T>>) list, key);

        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key, c);
        else
            return Collections.iteratorBinarySearch(list, key, c);
    }

参数：list-要搜索的列表，key-要搜索的键，c-排序列表的比较器。

5、反转方法reverse()

转指定列表中元素的顺序，此方法以线性时间运行。

@SuppressWarnings({"rawtypes", "unchecked"})
public static void reverse(List<?> list) {
    int size = list.size();
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
            swap(list, i, j);
    } else {
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator fwd = list.listIterator();
        ListIterator rev = list.listIterator(size);
        for (int i=0, mid=list.size()>>1; i<mid; i++) {
            Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }
}

参数：list-元素要被反转的列表

6、改组方法shuffle()

6.1、用默认随机源对指定列表进行置换，所有置换发生的可能性都是大致相等的

    public static void shuffle(List<?> list) {
        Random rnd = r;
        if (rnd == null)
            r = rnd = new Random(); // harmless race.
        shuffle(list, rnd);
    }

参数：list-要改组的列表

6.2、用指定的随机源对指定列表进行置换

@SuppressWarnings({"rawtypes", "unchecked"})
public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object[] arr = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

参数：list-要改组的列表，rnd-用来改组列表的随机源。

7、其他主要方法

7.1、交换方法swap()

函数定义：public static void swap(List<?> list,int i，int j)
在指定列表的指定位置处交换元素。
参数：list-进行元素交换的列表，i-要交换的一个元素的索引，j-要交换的另一个元素的索引。

7.2、替换方法fill()

函数定义：public static void fill(List<? super T> list,T obj)
使用指定元素替换指定列表中的所有元素，线性时间运行。
参数:list-使用指定元素填充的列表，obj-用来填充指定列表的元素。

7.3、复制方法copy()

函数定义：public static void copy(List<? super T> dest,List<? extends T> src)
将所有元素从一个列表复制到另一个列表。执行此操作后，目标列表中每个已复制元素的索引将等同于源列表中该元素的索引，目标列表的长度至少必须等于源列表。
参数：dest-目标列表，src-源列表。

7.4、最小值法min()

函数定义：public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
根据元素的自然顺序返回给定Collection的最小元素，Collection中的所有元素必须实现Comparable接口，此外，collection中的所有元素都必须是可相互比较的。
参数：coll-将确定其最小元素的collection。
函数定义：public static T min(Collection<? extends T> coll,Comparator<? super T> comp)
根据指定比较器产生的顺序，返回给定collection的最小元素。
参数：coll-将确定其最小元素的collection，comp-用来确定最小元素的比较器。

7.5、最大值方法max()

函数定义：public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
根据元素的自然顺序，返回给定collection的最大元素。
参数：coll-将确定其最大元素的collection。
函数定义：public static T max(Collection<?extends T> coll,Comparator<? super T> comp)
根据指定比较器产生的顺序，返回给定collection的最大元素。
参数：coll-将确定其最大元素的collection，comp-用来确定最大元素的比较器

7.6、轮换方法rotate()

函数定义：public static void rotate(List<?> list，int distance)
根据指定的距离轮转指定列表中的元素。
参数：list-要轮换的列表，distance-列表轮换的距离，可以使0、负数或者大于list.size()的数。

7.7、替换所有函数replaceAll()

函数定义：public static boolean replaceAll(List list,T oldVal,T newVal)
使用另一个值替换列表总出现的所有的某一指定值。
参数：list-在其中进行替换的列表；oldVal-将被替换的原值；newVal-替换oldVald的新值。

二、Collection和Collections区别

1.Collection:

Collection是集合类的上层接口。本身是一个Interface，里面包含了一些集合的基本操作。

Collection接口是Set接口和List接口的父接口

2.Collections

Collections是一个集合框架的帮助类，里面包含一些对集合的排序，搜索以及序列化的操作。

Collections是一个类,

Collections 是一个包装类，Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许，一些 collection 是有序的，而另一些则是无序的。

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

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

c++

本文分享自作者个人站点/博客前往查看

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

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

c++

登录后参与评论

0 条评论

热度