【Java 集合类】Collections 类源码分析

Collections 类源码分析

包路径：jdk1.8.0_111/rt.jar/java/util/Collections.java

Collections是JDK提供的工具类，同样位于java.util包中。它提供了一系列静态方法，能更方便地操作各种集合。

内部集合类

Collections 类在内部定义了一系列实用的集合类获取方法，主要包括不可变集合（unmodifiable）、线程安全集合（synchronized）、可检查集合（checked）、空集合（empty）和单元素集合（singleton）。

不可变集合

在 Collections 类内部，定义了一个静态类 UnmodifiableCollection，通过公用方法 unmodifiableCollection 获取：

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
    return new UnmodifiableCollection<>(c);
}

static class UnmodifiableCollection<E> implements Collection<E>, Serializable {...}

从字面意思来看，这是一个不可变的集合类，它的类方法与 Collection 基本相同，只不过如果调用添加、删除、修改相关的方法，就会抛出一个UnsupportedOperationException异常。这种封装实际上是通过创建一个代理对象，拦截掉所有修改方法的实现。封装后创建的代理对象确实是不能修改的，但用于创建该对象的原始对象的可变性是不变的。如果可变的原始对象被修改，由于不可变集合保留了对原始对象的引用，所以这种修改会同样出现在封装后的对象中。因此，要保证集合不变性，在封装完成创建代理对象后，最好将原来的对象引用抛弃，避免后续意外修改对象的数据。

类似的，还定义了如unmodifiableSet、unmodifiableSortedSet、unmodifiableNavigableSet、unmodifiableList、unmodifiableRandomAccessList、unmodifiableMap、unmodifiableEntrySet、unmodifiableSortedMap、unmodifiableNevigableMap的不可修改的集合类。

空集合

要注意的是，空集合都是不可变集合，也就是说，当空集合创建以后，不能再向其中添加或者删除元素。除了使用空集合的创建方法去获取一个空集合，还能使用对应集合接口提供的of()方法去创建空集合。例如：

List<String> lst1 = List.of();
List<String> lst2 = Collections.emptyList();

单元素集合

要注意的是，单元素集合也是不可变集合。类似的，还能使用对应集合接口提供的of(T)方法去创建单元素集合。例如：

List<String> lst1 = List.of("test");
List<String> lst2 = Collections.singletonList("test");

线程安全集合

Collections 类提供了一组方法，把线程不安全的集合变为线程安全的集合。但是从 Java 5 开始就引入了更高效的并发集合类，因此这部分的同步方法几乎很少会用到了。

算法

Collections 类的方法都是静态方法，每一种方法都对应一种集合算法的实现，且每一种实现都有两种，一种是适用于实现了RandomAccess接口的集合类（例如ArrayList），另一种是适用于序列存储的，例如（LinkedList）。Collections类包含的算法实现大致如下：

• 排序：排序采用归并排序，所以排序算法是稳定的，时间复杂度是确定的。
• 混淆：常规的集合数据操作（适用于List） ，包括reverse、fill、copy、swap、addAll等
• 搜索：适用于List，binarySearch
• 极值：求集合的最大元素、最小元素

Collections 中的大多数算法都只是适用于 List，使用与 List 的算法主要有：

• sort，shuffle，reverse，rotate
• swap，replaceAll，fill，copy
• binarySearch
• indexOfSubList，lastIndexofSubList

排序 sort

void sort(List<T> list) {list.sort(null);}
void sort(List<T> list, Comparator<? super T> c) {list.sort(c);}

方法内部将列表 list 转化成一个数组，通过使用 Arrays 类的 sort 方法进行排序，然后新建一个列表迭代器，依次将排序后的元素写入，构成新的有序的列表。

void Arrays.sort(t[] a, Comparator<? super T> c);

入参的比较器可以为 null，方法内部根据 LegacyMergeSort.userRequested 的布尔值，为 true 则采用归并排序（merge sort）；为 false 则采用 TimSort 算法进行排序。

legacyMergeSort 字面意思大概就是传统的归并排序，在方法实现内部，有一个 INSERTIONSORT_THRESHOLD = 7的字段，如果用于归并排序的序列或者子序列长度小于该值，则直接使用插入排序。值得注意的是，注释中表名，该算法相关的内容在未来的版本会被移除。

TimSort，亦或者是 ComparableTimSort 是优化后的归并排序，是一种混合、稳定高效的排序算法，源自归并排序和插入排序，旨在很好地处理多种真实数据。 它由 Tim Peters 于 2002 年实施使用在 Python编程语言中。 该算法查找已经排序的数据的子序列，并使用该知识更有效地对其余部分进行排序。若待排序的数组长度小于 MIN_MERGE = 32，则直接调用二分排序（binary sort）；否则先找到从数组开始处出现的一组升序或者严格降序（反转成升序）的区间，然后使用二分查找将后续的元素插入到之前的已排序的数组中。

二分排序（binary sort）是已知对短序列排序的最优排序。在最差情况下，它通常需要 O(n log n) 次的比较以及 O(n^2) 次的移动。当原始序列已经有部分区间是有序时，二分排序能更高效地完成排序任务。

在二分排序的实现中有一行代码需要注意：

int mid = (left + right) >>> 1;

这是通过位移运算的方式实现求两个数平均数的操作。类似的实现方式还有：

int mid = (left + right) >> 1;
int mid = (left + right) / 2;

从效率上看，在没有编译器做优化的前提下，位移运算的速度更快。位移运算只对整型有效，且当 left 和 right 都为正整数时，过程都是等价的。至于 >>> 和 >> 的区别，在于前者是无符号运算，不管原来的数是正数还是负数，位移后高位补 0；后者属于有符号运算，正数右移后高位补 0，负数位移后高位补 1。在这里使用 >>>，而不是除以 2 或者 >>，一方面是排序算法中下标的值必然为正整数；另一方面，当 left + right 的结果越界时，>>> 能保证结果是一个正整数，仍然正确。

查找 search

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

其中 binarysearch_threshold = 5000。

这里出现了一个接口RandomAccess，其源码定义是一个空的接口，也就说这个接口起到一个标志接口（marker）的作用。根据源码里注释的说明，这个标志接口用于声明实现这个接口的类支持随机访问的功能，而这个功能对于随机访问的列表（如 ArrayList）或者序列化的列表（如 LinkedList）在某些通用算法的性能有很大的影响。因此，在执行一些通用的列表算法前，就可以通过检查这个标志接口以确保当前列表使用该算法能有较好的性能，否则就应该作出相应的调整，应保证运行性能。

一般来说，list 的相关算法通常都会有两种实现，一种是适合随机访问的 list，另一种是适合序列化的（sequential）的 list。在大多数情况下，随机访问的列表会比长度短的序列化列表的表现得更好。在 Collections 类定义了一系列的阈值，作为选用哪种实现方法的边界。

我们看看 ArrayList 和 LinkedList 的定义：

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接口，后者没有，且后者还继承了AbstractSequentialList类。所以，通过判断 list 实现了RandomAccess接口或者其长度小于定义的阈值，可以认定当前的 list 是一个 ArrayList 或者 是一个长度小于 5000 的 LinkedList。那么在查找的实现中，采用通过下标直接获取元素的方式（实际上就是一个 for 循环遍历到指定下标）。否则，对于长度大于 5000 的 LinkedList 采用迭代器的方式依次遍历元素，从而找到目标位置的元素。

之所以存在以上的处理方式，是因为 ArrayList 用 for 循环遍历比迭代器遍历快，LinkedList 用迭代器遍历比 for 循环遍历快。因此，RandomAccess这个接口的存在，是为了能够更好地判断集合是否为 ArrayList 或者 LinkedList，从而能够选择更优的遍历方式，提高性能。不过如果单单从数据结构的定义出发，ArrayList 二分处理的速度还是会比 LinkedList 快，主要在获取元素的时间复杂度上分别为 O(1) 和 O(n)。

类似的情况还出现在这些方法中：

int binarySearch(List<? extends Comparable<? super T>> list, T key);
void reverse(List<?> list);
void shuffle(List<?> list, Random rnd);
void fill(List<? super T> list, T obj);
void copy(List<? super T> dest, List<? extends T> src);
void rotate(List<?> list, int distance);
void replaceAll(List<T> list, T oldVal, T newVal);
void indexOfSubList(List<?> source, List<?> target);
void lastIndexOfSubList(List<?> source, List<?> target);

总的一个思路就是，如果需要处理的 list 是一个比较大的 LinkedList，那么就通过使用迭代器 ListIterator，或者先将整个 list 转化成数组 array 进行处理后，再通过迭代器逐个元素进行写入，返回最终处理的结果。

复制 copy

这里先贴上copy方法的源代码：

public static <T> copy(List<? super T> dest, List<? extends T> src) {
    int srcSize = src.size();
    if (srcSize > dest.size())
        throw new IndexOutOfBoundsException("Source does not fit in dest");
    
    if (srcSize < COPY_THRESHOLD ||
        (src instanceof RandomAccess && dest instanceof RandomAccess)) {
        for (int i=0; i<srcSize; i++)
            dset.set(i, src.get(i));
    } else {
        ListIterator<? super T> di=dest.listIterator();
        ListIterator<? extends T> si=src.listIterator();
        for (int i=0; i<srcSize; i++) {
            di.next();
            di.set(si.next());
        }
    }
}

简单看下以上的代码，首先检查了入参出参的长度，确保dest的长度只能大于或者等于src的长度，至于多出来的长度不会有影响。之后进行的处理与我们上面讨论的情况一样。

这里值得注意的地方在于该方法两个参数类型的定义方式，也就是通配符的使用方法。通配符的使用是基于泛型的基本原理，泛型是一种类似”模板代码“的技术，在 Java 语言中泛型的实现方式是擦拭法（type erasure）。擦拭法指的是，虚拟机对泛型的实现一无所知，所有的工作都是编译器在编译过程中实现的。在编译时，编译器内部总是会将所有的类型T视为Object处理，在需要转型的时候，再根据T的类型自动实现安全的强制类型转换。

假设现在定义了两个列表List<Number> lst1和List<Integer> lst2。显然Integer是Number的子类，但List<Integer>却不是List<Number>的子类，因此作为参数传入时，不能将 lst2 直接作为 lst1传入，只允许通过元素逐个写入的方法进行赋值，因为超类可以接收子类的值。为了解决这种情况，我们可以使用List<? extends Number>和List<? super Integer>两种形式。

使用List<? extends Number>的泛型成为上界通配符，它把泛型T的上界限定在了Number类型，这样就可以传入List<Integer>类型，因为Integer是Number的子类，同时相应的 get 方法实际上也变成了<? extends Number> getFirst()，因此该方法的结果可以赋给Number类型的变量，但不能赋给Integer型，因为此时获得的结果也可以是Number的另一个子类Double类型。如果反过来调用 set 方法，即便传入Double满足了<? extends Number>，但由于泛型实现采用擦拭法的缘故，编译完成前Integer和Double都是被识别成Object类，因此Integer实际上是无法接受Double类型的赋值，在编译检查的时候这种情况就会报错，只有 set 的内容是 null 除外。

类似的，使用List<? super Integer>的泛型成为下界通配符，它把泛型T的下界限定在了Integer类型。相应的，它能够通过 set 方法接收Number和Object的超类的数值，但不能使用 get 方法，只有获取 Object 类型除外。

实际上，还存在一种无限定通配符<?>，它既没有extends，也没有super。因此基于上面的分析思路，它既不能 set（null 除外），也不能 get （Object 除外）。因此这种通配符常常只能用于做一些 null 判断，或者通过 get 方法看作 Object 类型，用equals()方法进行比较。<?>是所有<T>的超类，在大多数情况下也可以使用<T>来消除<?>。

综上所述，

• <? extends T>允许调用读方法T get()获取T的引用，但不允许调用写方法set(T)传入T的引用（传入null除外）；
• <? super T>允许调用写方法set(T)传入T的引用，但不允许调用读方法T get()获取T的引用（获取Object除外）。
• <?>不允许调用set(T)传入引用（null除外），也不允许调用T get()方法获取T的引用（只能获取Object引用）。

讨论了这么多，让我们回到上面的 copy 方法。我们可以看到传入的两个参数List<? super T> dest, List<? extends T> src，根据上面对上界通配符和下界通配符特点的分析，对于变量src我们可以安全地获取类型T的引用；而对于变量dest我们可以安全地传入T的引用。这样就保证了方法内部只能从src读入数据，只能向dest写入数据，如果在实现过程中出现了错误的操作，亦或者反过来进行获取添加，那么就会导致编译错误。

旋转 rotate

rotate 的实现同样区分两种：

• rotate1：实现RandomAccess接口的 list 或者长度小于阈值 100 的序列 list；
• rotate2：长度大于阈值 100 的序列 list。

第一种实现方式，利用了随机访问的特性，主要是从第一个元素开始，将其交换到正确的i = i + distance的位置上，被交换出来的元素，会继续交换到下一个i = i + distance的位置上，重复以上操作直到起始的位置被放置了新的元素。如果distance正好是列表长度的约数，那么此时需要从起始位置偏移到下一个位置，重复上述步骤直至所有位置的元素都被移动过，则旋转完成。其中每移动一次元素，用于计数的变量nMoved就会加 1。

第二种实现方式，主要是针对类似 LinkedList 这样的序列列表，首先通过mid = -distance % size找到一个连接位置，然后以这个位置为界，将 list 拆分成两个子列表，分别进行反转，最后再将整个列表反转。

reverse(list.subList(0, mid));
reverse(list.subList(mid, size));
reverse(list);

前两次反转子列表的目的是为了将原列表的首尾相连，并且找到旋转后的首尾位置并从原列表中断开，最后整个列表的反转是为了将列表恢复到原来的相对顺序。