Arrays类深入分析

一、概述
二、Arrays 类源码分析
- 1、sort()
- - 1.1、数字类型
  - - 1.1.1、DualPivotQuicksort
  - 1.2、其他类型
- 2、parallelSort()
- - 2.1、MIN_ARRAY_SORT_GRAN
  - 2.2、int 类型为例
- 3、equals()
- - 3.1、作用
  - 3.2、源码分析
- 4、fill()
- - 4.1、作用
  - 4.2、源码分析
- 5、copyOf()
- - 5.1、作用
  - 5.2、源码分析
  - 5.3、copyRangeOf()
- 6、asList()
- 7、hashCode()
- 8、stream()

一、概述

Arrays

类是一个用于操作数组的工具类，位于 JDK 的

java.util

包路径下，为开发者提供了许多操作数组的实用 API，如创建 ArrayList、数组排序、数组比较、二进制搜索算法搜索数组、数组填充和数组复制等等。

Arrays 的官方描述如下：

此类包含用于操纵数组的各种方法（例如排序和搜索）。 此类还包含一个静态工厂，该工厂允许将数组视为列表。 如果指定的数组引用为null，则除非另有说明，否则此类中的方法都抛出NullPointerException 。 此类中所包含方法的文档包括对实现的简要说明。 此类描述应被视为实现说明，而不是规范的一部分。 只要遵守规范本身，实现者就可以随意替换其他算法。 （例如， sort(Object[])使用的算法不必是MergeSort，但必须是稳定的。） 此类是Java Collections Framework的成员。

二、Arrays 类源码分析

由于 Arrays 类内容比较多，不可能一次性贴出源码，也不可能对所有方法都进行源码分析，因此，本人会根据自己的 Java 使用经验，重点分析经常实用以及虽然没经常使用但其功能比较值得学习的 API 方法进行源码分析。

1、sort()

由于 Arrays 类只有一个无参构造方法，因此没必要大费周章地用一个小结来分析 Arrays 类的构造方法。

Arrays 类中针对不同数据类型的数组和参数列表，一共提供了

个sort() 方法，下面进行详细分析。

1.1、数字类型

数字类型主要有 int 数组、long 数组、short 数组、float 数组和 double 数组，并且每种 sort 细分为只传递一个数组参数和传递数组与范围下标三个参数两种，罗列如下：

public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
    public static void sort(int[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    }
    public static void sort(long[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
    public static void sort(long[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    }
    public static void sort(short[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
    public static void sort(short[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    }
    public static void sort(float[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
    public static void sort(float[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    }
    public static void sort(double[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
    public static void sort(double[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    }

上面颇费笔墨的罗列出所有数据类型的 sort 方法体，为的就是让大家清晰的看到这些个 sort 的代码逻辑是惊人的一致：

没有传递范围下标的排序则直接调用 DualPivotQuicksort.sort 方法，如果有则先进行一个范围下标合法性的检查再调用

，因此也可以说，Arrays 类提供数组排序方法实际上起作用的是

DualPivotQuicksort.sort

，所以，有必要追踪一下这个方法的源代码：

1.1.1、DualPivotQuicksort

该类有官方说明为：

此类实现了Vladimir Yaroslavskiy，Jon Bentley和Josh Bloch的Dual-Pivot Quicksort(双轴快速排序)算法。 该算法可在许多数据集上提供O（n log（n））性能，从而导致其他快速排序降级为二次性能，并且通常比传统的（单轴）Quicksort实现要快。 所有公开的方法都是程序包专用的，旨在在执行任何必要的数组边界检查并将参数扩展为所需形式之后从公共方法（在Arrays类中）调用。

该类的 sort 方法源代码由于比较长，这里就不贴出来了，不过其思想可以说一下，这种双轴快速排序算法的思想为：

1）将NaNs(数组元素值为NaN)移到数组的末尾。

2）对除NaN（已经存在）以外的所有内容进行排序：

3）将负零放置在正零之前。

查找第一个零或第一个正数或最后一个负数元素。
跳过最后一个负值（如果有）或所有前导负零。

/*
  * 将负零移动到子范围的开头。
  *
  * 分区：
  *
  * +----------------------------------------------------+
  * |   < 0.0   |   -0.0   |   0.0   |   ?  ( >= 0.0 )   |
  * +----------------------------------------------------+
  *              ^          ^         ^
  *              |          |         |
  *             left        p         k
  *
  * 不变量：
  *
  *   all in (*,  left)  <  0.0
  *   all in [left,  p) == -0.0
  *   all in [p,     k) ==  0.0
  *   all in [k, right] >=  0.0
  *
  * 指针k是？部分的第一索引。
  */

更多的双轴快速排序算法的信息可以去百度，或者查看 DualPivotQuicksort 源代码。

1.2、其他类型

主要指的是针对字符数组和字节数组的排序，其源代码就是数字类型的排序算法换个数组类型而已，其他逻辑都没有什么变化。

2、parallelSort()

所谓并行排序就是当数组长度较大时，会将数组分成多个部分开启多个线程对每个部分进行排序，然后再通过多线程的分支合并进行结果合并。

要说这个并行排序算法，首先得看一个属性字段：

MIN_ARRAY_SORT_GRAN

，这个字段得值是触发并行排序的一个阈值。

2.1、MIN_ARRAY_SORT_GRAN

这是 Arrays 类的一个私有属性字段，其声明：

private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;

，其作用：

最小数组长度，低于该最小数组长度，并行排序算法将不会进一步划分排序任务。 使用较小的大小通常会导致跨任务的内存争用，从而导致并行加速的可能性不大。

2.2、int 类型为例

由于这些并行排序算法，只是数组类型不同而已，其他代码逻辑都是一致的，因此这里以 int 类型为例，进行一个源码分析，然后其他类型举一反三即可。

首先贴出源代码：

public static void parallelSort(int[] a) {
        int n = a.length, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
        else
            new ArraysParallelSortHelpers.FJInt.Sorter
                (null, a, new int[n], 0, n, 0,
                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g).invoke();
    }
    public static void parallelSort(int[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        int n = toIndex - fromIndex, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
        else
            new ArraysParallelSortHelpers.FJInt.Sorter
                (null, a, new int[n], fromIndex, n, 0,
                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g).invoke();
    }

毫无悬念地出现了

ForkJoinPool

，这是一个 JUC 里面的用于进行并行任务的一个线程池类，该类的

getCommonPoolParallelism()

方法用于

返回公共池的目标并行度。

也就是说，

只有当数组的规模大于MIN_ARRAY_SORT_GRAN的值，并且公共线程池中正在执行任务的线程数大于1时

，才会开启并行排序任务。

而进行并行排序，主要通过

ArraysParallelSortHelpers.FJInt

的排序器进行，而

ArraysParallelSortHelpers

官方说明如下：

Arrays.parallelSort中的并行排序方法的帮助程序实用程序。

对于每种基本类型，再加上对象，我们定义一个静态类来包含该类型的Sorter和Merger实现, Sorter 主要基于CilkSort 实现。

基本算法：

如果数组大小很小，则只需使用顺序快速排序（通过Arrays）即可。排序）否则：
- 1.将数组分成两半。
- 2.对于每一半：
  - 再折成两半，
  - 对再拆分后的每一半进行排序
  - 将排序后的结果合并在一起
- 将两个部分合并在一起。
- 拆分为四分之一的原因之一是， 保证最终排序在主数组中，而不是在工作区数组中。 （每个子排序步骤上的工作区和主交换角色。）叶级排序使用关联的顺序排序。合并类对Sorter执行合并。它们的结构使得如果基础排序是稳定的（TimSort确实如此），则完整排序也是如此。
如果足够大，他们将两个分区中的最大分区一分为二，通过二进制搜索找到较小分区中的最大值，而不是较大分区的后半部分的开头。然后并行合并两个分区。

为了确保以保持稳定性的顺序触发任务，当前的CountedCompleter设计需要一些小任务来充当占位符，以触发完成任务。这些类（EmptyCompleter和Relay）不需要跟踪数组，并且它们本身永远不会被派生，因此不保留任何任务状态。除类型声明外，基本类版本（FJByte … FJDouble）彼此相同。基本顺序排序依赖于TimSort，ComparableTimSort和DualPivotQuicksort排序方法的非公开版本，这些方法接受我们将已经分配的临时工作空间数组切片，因此避免了冗余分配。（DualPivotQuicksort byte []排序除外，该排序永远不会使用工作区数组。）

FJInt

是 ArraysParallelSortHelpers 针对 int 型数组的一个内部类，有趣的是，这个 FJInt 又嵌套了内部类：

static final class Merger extends CountedCompleter<Void>

和

Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,int size, int wbase, int gran)

，并且无论是 FJInt 类还是 Meger 类，都提供了一个

public final void compute()

方法。但是，从调用逻辑来看，最终其作用的是 Merger 类的 compute 方法。

由于代码量多，并且比较晦涩难懂，就不贴出源码了。有兴趣的同学，自己深入进去查看。

3、equals()

可以毫无意外的再一次看到 JDK 源码的特点：针对不同的数据类型的数组和参数列表，提供不同的 equals 方法，然而实际工作逻辑确是同一个套路。

3.1、作用

equals() 方法的作用就是比较两个数组是否相等，相等则返回 true，不相等则返回 false。那怎么样才算是相等呢？条件如下：

1）两个数组的类型一样
2）两个数组的规模一样，即数组长度相等
3）相同位置上的元素的值一致

特别的，

如果两个数组都是null，则认为是相等的

。官方文档为证：

如果两个指定的long数组彼此相等，则返回true 。 
    如果两个数组包含相同数量的元素，
    并且两个数组中所有对应的元素对都相等，则认为两个数组相等。
     换句话说，如果两个数组包含相同顺序的相同元素，则它们相等。 
     另外，如果两个数组引用都为null，则认为它们相等。

3.2、源码分析

以 long 类型的 equals 方法为例进行 JDK 源码分析。首先贴出源码：

public static boolean equals(long[] a, long[] a2) {
    if (a==a2)
        return true;
    if (a==null || a2==null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    for (int i=0; i<length; i++)
        if (a[i] != a2[i])
            return false;

    return true;
}

其算法逻辑如下：

1）首先判断通过参数传递进来的 a 数组和 a2 数组，是否同一个数组的引用(数组首地址一样)，是则直接返回 true，否则进行下一步。
2）判断传参进来的两个数组，是否是情况：一个数组是 null 而另一个不是，是的话直接返回 false，否则进行下一步。
3）判断传递进来的两个数组是否具有相同的规模即数组长度是否相等，若不等返回 false，否则进行下一步
4）遍历比较两个数组，如果两个数组出现某一位置上的元素值不相等，则返回 false，否则直到遍历完所有的数组元素后返回 true。

4、fill()

还是相同的套路。

4.1、作用

fill 方法，正如单词本身的意思一样：

用于填充数组元素的值

。根据是否指定填充范围分为全填充的 fill 和范围填充的 fill，具体见下面的源代码：

4.2、源码分析

public static void fill(char[] a, char val) {
        for (int i = 0, len = a.length; i < len; i++)
            a[i] = val;
    }
    public static void fill(char[] a, int fromIndex, int toIndex, char val) {
        rangeCheck(a.length, fromIndex, toIndex);
        for (int i = fromIndex; i < toIndex; i++)
            a[i] = val;
    }

方法的功能相当朴素，算法也相当简单，其实 JDK 源码大部分比起 Java 框架诸如 Spring 框架要简单很多。这里主要做的就是将整个数组或将数组从 fromIndex 到 toIndex 范围内的元素的值赋值为参数 val。此外，如果是范围填充，则在进行遍历填充之前，先调用 Arrays 的 rangeCheck 方法检查 fromIndex 和 toIndex 所确定的范围是否合法。

5、copyOf()

5.1、作用

copyOf 方法的作用就是复制数组：从源数组中复制出一个长度为newLength的副本数组，当 newLength 的值大于源数组的长度时，会采用 0或“” 填充超出源数组长度部分的新数组元素。

5.2、源码分析

以数据类型为 byte 型的 copyOf 为分析案例：

public static byte[] copyOf(byte[] original, int newLength) {
        byte[] copy = new byte[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

如源码所示，进行复制时，调用了System类的本地方法

arraycopy

完成操作。而本地方法的源码，一般很难看到。

5.3、copyRangeOf()

先来看看源码：

public static short[] copyOfRange(short[] original, int from, int to) {
        int newLength = to - from;
        if (newLength < 0)
            throw new IllegalArgumentException(from + " > " + to);
        short[] copy = new short[newLength];
        System.arraycopy(original, from, copy, 0,
                         Math.min(original.length - from, newLength));
        return copy;
    }

该方法，

将指定数组的指定范围复制到新数组中

。范围（ from ）的初始索引必须介于零和original.length之间（包括首尾）。 original [from]处的值放置在副本的初始元素中（除非from == original.length或from == to ）。来自原始数组中后续元素的值将放置在副本中的后续元素中。范围（ to ）的最终索引（必须大于或等于from ）可以大于original.length ，在这种情况下，（short）0放置在副本中所有索引大于或等于 original.length-from 的元素中。返回数组的长度为to-from 。

算是 copyOf 方法的一个改进版，改进之处就是指定源数组的哪个范围内的元素将会被复制。

6、asList()

该方法用于将一个数组转为列表，方法源代码如下：

@SafeVarargs
    @SuppressWarnings("varargs")
    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

说明一下，这里的 ArrayList 类可不是我们开发中经常使用的那个 ArrayList，而是 Arrays 类的静态内部类。

7、hashCode()

该方法用于返回指定数组的hash码，源代码如下：

public static int hashCode(long a[]) {
        if (a == null)
            return 0;

        int result = 1;
        for (long element : a) {
            int elementHash = (int)(element ^ (element >>> 32));
            result = 31 * result + elementHash;
        }

        return result;
    }

这里是以数组类型为 long 型的为例，别以为只有一个 hashCode 方法。这里使用的 hash 算法与 String 类中的 hash 算法是一样，因此可以前去参考，这里不再赘述。

8、stream()

这个方法非常非常重要，它提供了数组进行流式计算的入口，以 double 类型的数组为例，进行源码分析：

public static DoubleStream stream(double[] array) {
        return stream(array, 0, array.length);
    }
    public static DoubleStream stream(double[] array, int startInclusive, int endExclusive) {
        return StreamSupport.doubleStream(spliterator(array, startInclusive, endExclusive), false);
    }

一个所有数组元素都参与流式计算，一个只有指定范围的元素参与流式计算。DoubleStream 是一个针对数据类型为 double 的流式计算接口。所谓流式计算，就是 Java 参照 SQL 语法开发的 JDK1.8 之后的新的计算方式，举例如下：

User u1 = new User(11, "a", 23);
        User u2 = new User(12, "b", 24);
        User u3 = new User(13, "c", 22);
        User u4 = new User(14, "d", 28);
        User u5 = new User(16, "e", 26);
        List<User> list = Arrays.asList(u1, u2, u3, u4, u5);
        /*
        * 请按照给出数据，找出同时满足以下条件的用户：<br>
        * 偶数Id且年龄大于24且用户名转为大写且用户名按字母排倒序 
        * 只输出一个用户名字
        */
        // select upper(username) from user where id%=0 and
        // age>24 order by username desc limit 1;
        list.stream()
            .filter(u -> u.getId() % 2 == 0)
            .filter(u -> u.getAge() > 24)
            .map(u -> u.getUsername().toUpperCase())
            .sorted(Comparator.reverseOrder())
            .limit(1)
            .forEach(System.out::println);

也就是说，流式计算使得数组和列表等集合类能够像，在关系数据库中使用 SQL 查询一样，进行数据的过滤、映射、排序、限制输出，十分强悍。

Java高阶之Arrays类深入剖析一、概述二、Arrays 类源码分析