集合相关的常用工具类

1. 简介

Java中的集合类既可以当做放其他数据的容器，又可以当做常见的数据结构使用。Java中提供了很多好用的工具类来操作这些集合类。本篇博客就来介绍下常用的集合工具类。集合常用的工具类大体可以分为3类：

• JDK本身提供的工具类；
• Guava提供的工具类；
• Apache common-Collection提供的工具类

2. JDK提供的工具类

主要由下面三个：

• Arrays
• Collections
• Objects

Arrays是操作数组对象的工具类， Collections 是操作集合对象的工具类。 Objects 是操作引用数据类型对象的工具类。

Arrays的常用方法：

普通排序：

Arrays.sort(int[] a)
Arrays.sort(int[] a, int fromIndex, int toIndex)

其他非boolean基础数据类型的数组对象以及实现Comparable接口的类的数组对象均有此方法。

并行排序：JDK1.8新增。

Arrays.parallelSort(int[] a)
Arrays.parallelSort(int[] a, int fromIndex, int toIndex)

其他非boolean基础数据类型的数组对象以及实现Comparable接口的类的数组对象均有此方法。

并行计算：JDK1.8新增，支持函数式编程，根据传入的方法进行一次计算。

Arrays.parallelPrefix(int[] array, IntBinaryOperator op)
Arrays.parallelPrefix(int[] array, int fromIndex, int toIndex, IntBinaryOperator op)

其他非boolean基础数据类型的数组对象以及实现Comparable接口的类的数组对象均有此方法。

二分法查找：前提是该数组已经进行了排序

Arrays.binarySearch(int[] a, int key)
Arrays.binarySearch(int[] a, int fromIndex, int toIndex, int key)

其他非boolean基础数据类型的数组对象以及实现Comparable接口的类的数组对象均有此方法。

判断两个数组是否相等：

Arrays.equals(int[] a, int[] a2)

其他基础数据类型的数组对象以及Object数组对象均有此方法,Object调用的是equels()方法。

对数组进行填充：

Arrays.fill(int[] a, int val)
Arrays.fill(int[] a, int fromIndex, int toIndex, int val)

其他基础数据类型的数组对象以及Object数组对象均有此方法。

复制数组：

Arrays.copyOf(int[] original, int newLength)，返回赋值后的数组，数组长度为newLength。
Arrays.copyOfRange(int[] original, int from, int to)

其他基础数据类型的数组对象以及Object数组对象均有此方法。Object数组为浅复制，即复制的是引用。

toString: 将元素用","隔开，包裹在"[ ]"内。

Arrays.toString(int[] a)

其他基础数据类型的数组对象以及Object数组对象均有此方法。Object数组为引用地址。

Arrays.deepToString(Object[] a)方法内部调用了a.toString()。

更改元素值：JDK1.8新增，支持函数式编程

setAll(int[] array, IntUnaryOperator generator)
setAll(long[] array, IntToLongFunction generator)
setAll(double[] array, IntToDoubleFunction generator)
setAll(T[] array, IntFunction<? extends T> generator)

该类方法支持这四种类型。每种类型均有对应的并行设置方法parallelSetAll()

数组转集合：

Arrays.asList(T... a) 返回List<T>

如果是Object数组对象，该方法生成的集合对象持有的是数组对象对应元素的引用。

生成并行遍历的Spliterator，JDK1.8新增

Arrays.spliterator(int[] array)
Arrays.spliterator(int[] array, int startInclusive, int endExclusive)

int、long、double和实现了Spliterator接口的类具有该类型方法。

生成Stream类，JDK1.8新增

Arrays.stream(int[] a)
Arrays.stream(int[] array, int startInclusive, int endExclusive)

int、long、double和实现了Stream接口的类具有该类型方法。

JDK1.8新增的方法基本都是与函数式变成或多核并行操作相关。

接下来看看Arrays常用方法的源码。

1，Arrays.asList()的源码实现分析：

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);  // 为什么JDK的设计者不直接使用ava.util.ArrayList呢？
    }

这个ArrayList是数组的内部实现类，不是经常是用的java.util.ArrayList。这个内部类ArrayList是一个固定大小的list，不支持list.add()和list.remove()，这里一定要注意。

2，Arrays.sort()的源码实现分析：

public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

这里用到了DualPivotQuicksort.sort()。DualPivotQuicksort是java.util包下的final类，专门用来对基础数据类型的数据进行排序的。DualPivotQuicksort.sort()源码分析：

static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
        // 对于数组长度小的情况采用快速排序
        if (right - left < QUICKSORT_THRESHOLD) { // QUICKSORT_THRESHOLD = 286
            sort(a, left, right, true);
            return;
        }
      // 归并+快排 （引入了TimSort的run的概念）
    ...省略算法源码
    }

快排算法sort()的源码分析：

private static void sort(int[] a, int left, int right, boolean leftmost) {
        int length = right - left + 1;
        // 对于数组长度很小的情况采用插入排序
        if (length < INSERTION_SORT_THRESHOLD) { // INSERTION_SORT_THRESHOLD) = 47
        // 插入排序 insertion sort
        ...省略算法源码
        }

    // 双轴快排 dual-pivot quicksort 
    ...省略算法源码（递归插入排序）
    }

具体的算法实现源码不做深究，以后有机会的话写一些关于算法拾遗。这里主要是一些 阀值 要注意。

3，Arrays.sort(Object[] a)的源码实现分析：

public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested) // 如果用户强制要求使用传统的排序方法。
            // -Djava.util.Arrays.useLegacyMergeSort=true 
            // 或者System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
            legacyMergeSort(a); // 使用传统方法排序
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0); // 使用TimSort算法排序
    }

传统的排序算法legacyMergeSort()源码：

private static void legacyMergeSort(Object[] a, int fromIndex, int toIndex) {
        Object[] aux = copyOfRange(a, fromIndex, toIndex);
        mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
    }
    private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) {
        int length = high - low;
        // 如果数组长度很小，采用插入排序 Insertion sort
        if (length < INSERTIONSORT_THRESHOLD) { // INSERTIONSORT_THRESHOLD = 7
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }
        // 将数组分为两个子数组，分别使用递归排序Recursively sort，再进行合并排序
        ...省略算法源码
    }

JDK1.8开始支持TimSort算法，源于Python中的 TimSort （结合了merge sort 和 insertion sort）。

ComparableTimSort.sort()源码：

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // 数组长度为0或1时无需排序
        // 如果数组长度小，采用无合并形式的"mini-TimSort"排序
        if (nRemaining < MIN_MERGE) { // MIN_MERGE = 32
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen); // 二分插入排序
            return;
        }

        // 1，遍历一遍数组，找到已经自然排序好顺序的序列；3，这个序列入栈（临时数组，排序后的数组就放在这里）；
        // 2，如果这个序列的长度 < minRun 则通过binarySort得到长度为minRun的序列。这个minRun的计算跟数组本身长度有关；

        // 4，同样的方法寻找下一个分段并入另外一个栈；

        // 5，合并排序两个栈中的序列；

        // 6，重复4和5；

        ...省略算法源码

    }

4，Arrays.parallelSort()的源码实现分析:

public static void parallelSort(byte[] a) {

        int n = a.length, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            DualPivotQuicksort.sort(a, 0, n - 1)
        else
            new ArraysParallelSortHelpers.FJByte.Sorter
                (null, a, new byte[n], 0, n, 0,
                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g).invoke();
    }

Arrays.parallelSort()采用的是 cilk排序算法 。

cilk排序算法基本思想：

1. 将数组分为两部分；
2. 针对每一部分：a，再分为2部分（相当于1/4）；b，针对每1/4部分进行排序；c，排序并合并这两个1/4；
3. 将分别排序好的这两部分进行排序合并。

如果当前数组的长度a.length < MIN_ARRAY_SORT_GRAN = 8192，或者当前机器不支持并行排序，则采取普通的sort()。

ForkJoinPool.getCommonPoolParallelism()获取当前ForkJoin线程池的并行度，跟机器的处理器核数有关，可以通过-Djava.util.concurrent.ForkJoinPool.common.parallelism=8或者System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism","8")来指定，如果=1则表示不支持并行执行。

parallelSort()的基本实现思想：

1. 将需要被排序的数组分为parallelism个子数组交由ForkJoin框架的每个并行线程执行；
2. 每个并行线程将分配到的子数组又分为4个子数组按照cilk算法进行排序，没个1/4子数组都会按照DualPivotQuicksort.sort()排序；
3. 最后将parallelism个子数组进行排序合并。

==================================华丽的分割线==================================

Collections的常用方法：

排序：

Collections.sort(List list) T或其父类需要实现Comparable接口 Collections.sort(List list, Comparator<? super T> c) Collections.sort()的源码：

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

List.sort()的源码：

default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c); // 调用Arrays.sort()来进行排序
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

Collections.sort()最终调用的是Arrays.sort()进行排序。

查到索引

Collections.binarySearch(List<? extends Comparable<? super T>> list, T key) Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

顺序反转

Collections.reverse(List<?> list)

乱序

Collections.shuffle(List<?> list)

指定元素互换

Collections.swap(List<?> list, int i, int j)

填充

Collections.fill(List<? super T> list, T obj)

复制

Collections.copy(List<? super T> dest, List<? extends T> src)

求极值

Collections.min(Collection<? extends T> coll)

Collections.min(Collection<? extends T> coll, Comparator<? super T> comp)

Collections.max(Collection<? extends T> coll)

Collections.max(Collection<? extends T> coll, Comparator<? super T> comp)

转动元素

Collections.rotate(List<?> list, int distance)

distance可以接受负数 将list元素整体向后移动distance的距离，原来最后的distance个元素放到最前面（有点类似与一个圆圈转动）

替换元素

Collections.replaceAll(List list, T oldVal, T newVal)

子集合索引

Collections.indexOfSubList(List<?> source, List<?> target)

Collections.lastIndexOfSubList(List<?> source, List<?> target)

如果不是子集合，返回-1

转换为同步集合

元素受限制集合

生成空的不可变集合

Collections.emptyIterator()

Collections.emptyListIterator()

Collections.emptyEnumeration()

Collections.emptySet()

Collections.emptyList()

Collections.emptyMap()

只有1个元素的不可变集合

Collections.singleton(T)

Collections.singletonList(T)

Collections.singletonMap(K, V)

拥有n个相同元素的不可变集合

Collections.nCopies(int, T)

反序比较器

Collections.reverseOrder(Comparator ) 返回一个Comparator ，返回值与参数值是相反顺序的比较器

转换为枚举类型的API

Collections.enumeration(Collection ) 返回Enumeration

将Enumeration 转换为集合

Collections.list(Enumeration ) 返回ArrayList

元素在集合中的个数

Collections.frequency(Collection<?>, Object) 返回int

两个元素是否有交集

Collections.disjoint(Collection<?>, Collection<?>) 返回boolean

增加元素

addAll(Collection<? super T> c, T... elements)

由于List接口拥有listItegertor()方法，与List相关的大部分操作内部会判断阀值，超过阀值则采用listIterator遍历，小于阀值则采用for循环索引遍历。不同的方法阀值不同。

==================================华丽的分割线==================================

Objects类最主要就一个方法 Objects.equals(Object a, Object b)

public static boolean equals(Object a, Object b) {
    return a == b || (a != null && a.equals(b));
  }

其余的一些比如Obejcts.isNull(Object obj)、Objects.nonNull(Ojbect obj)主要是用来在Stream流式API操作的时候使用。

3. Guava工具类

任何对JDK集合框架有经验的程序员都熟悉和喜欢 java.util.Collections 包含的工具方法。Guava沿着这些路线提供了更多的工具方法：适用于所有集合的静态方法。这是Guava最流行和成熟的部分之一。

我们用相对直观的方式把工具类与特定集合接口的对应关系归纳如下：

在找类似转化、过滤的方法？请看第四章，函数式风格。

详细的介绍可以参考这个 文章

4. Apache提供的Collection

Apache提供的集合工具类功能也非常强大。另外还提供了集合的求交集、并集和差集等功能。

具体可以参考 官网

5. 参考

• https://ifeve.com/google-guava-collectionutilities/