Java1.8-Arrays源码解析

概述

集合框架的工具类除了Collecions之外，另一个就是Arrays了，上文已经说过，Java中Arrays工具类是针对数组进行操作的，这个类中包含了许多操作数组的静态方法。我们来大致看一下它的源码实现。

构造方法与属性

private Arrays() {}
// 进行并行排序的最小数组长度
private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
// 在使用归并排序中优先使用插入排序的阈值（后续会移除掉）
private static final int INSERTIONSORT_THRESHOLD = 7;

和Collections一样，构造方法私有，不对外提供。我们只需调用Arrays的静态方法来操作数据即可。

sort方法

Arrays提供了一系列重载的sort方法，大体上可以分为两种，一种是针对基本数据类型来进行排序，包括int，long，byte，float，double等类型，另一种是针对Object数组类型来进行排序。默认都是升序排列的。我们来简单看一下int数组的排序：

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

  可以看到，底层都是通过调用DualPivotQuicksort该类的sort方法来实现的。DualPivotQuicksort这个类是JAVA1.7之后专门提供给Java内部排序使用的专用类，被称为双枢轴快速排序，用来优化原先的快速排序，该算法一般能提供O(nlog(n))的时间复杂度，大家有兴趣的可以查看它的源码来学习一下。
  至于其他类型的排序，和int类型排序都是类似的，不多说了。另外简单说一点，就是我们使用的Collections的sort方法就是借助Arrays.sort方法来实现的。

另外一种重载的sort方法：

public static void sort(Object[] a)
public static void sort(Object[] a, int fromIndex, int toIndex)
// 带比较器的排序算法
public static <T> void sort(T[] a, Comparator<? super T> c)
// 带比较器的 数组的部分排序
public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                Comparator<? super T> c)

该方法要求传入的参数必须实现了Comparable，这个排序算法是一种稳定的算法。由于实现大致相似，我们来简单看下sort(Object[] a)。

public static void sort(Object[] a) {
    // 使用归并排序
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    // 使用TimSort排序
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

该算法的实现又分为两种，一种通过归并排序算法来实现，另一种通过使用TimSort排序算法来实现。TimSort算法是一种插入与传统归并算法结合的一种算法，是对归并算法的一种优化。至于使用哪一种算法，需要设置系统变量：java.util.Arrays.useLegacyMergeSort，通过设置为true，来使用归并算法，否则使用TimSort算法。默认情况下我们是不会用到归并算法的，并且在JDK文档中有说明，在后续的版本中，legacyMergeSort归并算法会被移除掉。所以，如果有兴趣，大家可以去看下TimSort算法的实现。这里参考自：
Compile in Java 6, run in 7 - how to specify useLegacyMergeSort?

/**
 * Old merge sort implementation can be selected (for
 * compatibility with broken comparators) using a system property.
 * Cannot be a static boolean in the enclosing class due to
 * circular dependencies. To be removed in a future release.
 */
static final class LegacyMergeSort {
    private static final boolean userRequested =
        java.security.AccessController.doPrivileged(
            new sun.security.action.GetBooleanAction(
                "java.util.Arrays.useLegacyMergeSort")).booleanValue();
}

/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}

parallelSort方法

  Arrays同样提供了一系列重载的parallelSort方法，用于数字类型的并行排序，同样默认也是升序排列的。这一系列算法是JAVA1.8之后引入的，基于JAVA的并行处理框架fork/join框架，而fork/join框架，是Java1.7引入，目的是为了充分利用多核处理器，编写并行程序，提高程序性能的框架。

public static void parallelSort(byte[] a) {
    int n = a.length, p, g;
    // 如果数组长度小于并行排序的最小长度或者并行线程池的大小是1
    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();
}

我们可以看到，程序里进行了判断，如果数组长度太小，小于并行排序的最小长度或者并行线程池的大小是1，这时候就不再使用并行处理，还是使用DualPivotQuicksort的sort方法来进行排序。这里有两点简单说明下：

1. Arrays的常量MIN_ARRAY_SORT_GRAN ，如果数组容量太小，而使用并行处理的话，通常会导致跨任务的内存竞争，这样的话并行的速度就没有预想中的那么令人满意。
2. ForkJoinPool是fork/join框架中的一个核心类，通过ForkJoinPool的getCommonPoolParallelism方法我们可以获取到并行线程池的大小，如果是1的话，也就是单核，就不需要使用并行处理了。因为默认情况下，并行线程池的大小等于CPU的核数。

parallelPrefix方法

public static void parallelPrefix(int[] array, IntBinaryOperator op)
public static <T> void parallelPrefix(T[] array, int fromIndex,int toIndex, BinaryOperator<T> op)

Arrays提供了一系列parallelPrefix方法，用于对数组进行并行的二元迭代操作，其中方法的最后一个参数是二元操作符的意思，该运算符其实是一个函数表达式。说起来有点绕口，先看个例子：

public static void main(String[] args) {
    int[] numbers = {1, 2, 3, 4, 5};
    System.out.println("old array: ");
    Arrays.stream(numbers).forEach(n -> System.out.print(n + " "));

    // 二元迭代：累加
    System.out.println("\noperator: + ");
    IntBinaryOperator binaryOperator = (x, y) -> (x + y);
    Arrays.parallelPrefix(numbers, binaryOperator);
    Arrays.stream(numbers).forEach(n -> System.out.print(n + " "));

    // 二元迭代：累乘
    System.out.println("\noperator: * ");
    Arrays.parallelPrefix(numbers, (x, y) -> x * y);
    Arrays.stream(numbers).forEach(n -> System.out.print(n + " "));
}

output：

old array: 
1 2 3 4 5 
operator: + 
1 3 6 10 15 
operator: * 
1 3 18 180 2700 

例子参考自：Java 8 Arrays parallelPrefix method Example
也就是说，该方法是一种累计的操作，比如累加，数组中的每个元素依次与前面的所有元素累加，然后替换原来的元素。对于大型数组，并行迭代操作通常比顺序循环性能更好。同样，该方法也有多种重载方式，支持int，long，double等类型的操作。

该方法是JDK1.8之后引入的，底层是通过JDK内部提供的ArrayPrefixHelpers类来实现的，当然最终还是通过fork/join框架来实现的。

源码如下：

public static void parallelPrefix(int[] array, IntBinaryOperator op) {
    Objects.requireNonNull(op);
    if (array.length > 0)
        new ArrayPrefixHelpers.IntCumulateTask
                (null, op, array, 0, array.length).invoke();
}

binarySearch方法

public static int binarySearch(int[] a, int key)
public static int binarySearch(int[] a, int fromIndex, int toIndex,int key)

顾名思义，这个方法是二分查找的意思，用来在数组中查找元素。当然，使用该方法之前，必须保证该数组已经排序完成，并且是升序完成。否则，查找将没有什么意义。如果数组包含多个指定查找值的元素，则无法保证找到具体哪一个值。
源码如下：

public static int binarySearch(int[] a, int key) {
    return binarySearch0(a, 0, a.length, key);
}

/**
 * 其中该方法和binarySearch的public方法一样，就是没有索引校验
 */
 // Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                 int key) {
    // 开始下标
    int low = fromIndex;
    // 结束下标
    int high = toIndex - 1;

    while (low <= high) {
        // 通过位移运算符计算中间下标值
        int mid = (low + high) >>> 1;
        // 保存数组中间值
        int midVal = a[mid];
        // 中间值比要查找的值小，往数组高位进行查询
        if (midVal < key)
            low = mid + 1;
        // 中间值比要查找的值大，往数组低位进行查询
        else if (midVal > key)
            high = mid - 1;
        else
            // 如果相等，直接返回
            return mid; // key found
    }
    // 查找不到，返回负值
    return -(low + 1);  // key not found.
}

该方法比较简单，当然也是提供了一系列重载的方法，其中也可以自定义查找时的比较规则：
private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
大家等用到的时候可自行查看。

equals方法

public static boolean equals(Object[] a, Object[] a2)

这个方法很简单，就是判断两个数组是否相等。比较的类型如果重写了equals方法，则按照对象的equals方法进行比较。该方法也有许多重载方法，实现类似，我们来查看下object数组作为参数的源码：

public static boolean equals(Object[] a, Object[] a2) {
    // 如果是同一个数组引用，则相等
    if (a==a2)
        return true;
    // 如果有一个数组为null，则不相等
    if (a==null || a2==null)
        return false;

    int length = a.length;
    // 如果长度不相等，则不相等
    if (a2.length != length)
        return false;
    // 如果对应位置上的值不相等，则不相等
    for (int i=0; i<length; i++) {
        Object o1 = a[i];
        Object o2 = a2[i];
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    如果以上都不满足，则相等
    return true;
}

fill方法

public static void fill(long[] a, long val)
public static void fill(long[] a, int fromIndex, int toIndex, long val)
这个方法也很简单，就是将指定值填充到数组的每个元素。底层实现就是循环遍历填充即可。一般我们批量初始化数组的时候可以使用该方法。

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

copyOf和copyOfRange方法

public static int[] copyOf(int[] original, int newLength)
public static <T> T[] copyOfRange(T[] original, int from, int to)

复制数组，newLength是新数组的长度。如果新数组长度大于原数组长度，则新值填充null或相关类型默认值（比如int，默认填充0，double类型默认为0.0）。先来看下泛型的源码：

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

可以看到，底层是通过System的native方法arraycopy来实现的，这个方法在操作集合的时候也经常用到。而对于类型固定的则和这类似，看一下int类型：

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

而copyOfRange底层实现类似，就多了步对索引的判断，就不多说了。

asList

将数组转为List，该方法与集合的toArray方法一起充当了基于数组和集合之间的桥梁。并且该方法还提供了一种很便捷的方法来创建一个初始化大小的列表，该列表初始化包含几个元素：

List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");

该方法源码如下：

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

这里返回的ArrayList不是我们常用的java.util.ArrayList，而是Arrays的一个静态内部类，并且该内部类中没有add和remove方法，所以不支持添加和移除等操作。

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
{
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }

    @Override
    public int size() {
        return a.length;
    }

    @Override
    public Object[] toArray() {
        return a.clone();
    }

    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        ...
    }

    @Override
    public E get(int index) {
        return a[index];
    }

    @Override
    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }

    @Override
    public int indexOf(Object o) {
        ...
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(a, Spliterator.ORDERED);
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        ...
    }

    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        ...
    }

    @Override
    public void sort(Comparator<? super E> c) {
        Arrays.sort(a, c);
    }
}

hashCode方法

  获取数组的hashCode值，该值是基于数组的每一个元素的hashCode来实现的。
  如果数组中有嵌套数组，我们还想根据里层数组的每个元素的hashCode来获取hash的话，我们可以通过deepHashCode方法，该方法通过递归的方式来实现。

通俗的来讲，hashCode方法只计算到数组的第一层，而deepHashCode方法则会一直递归调用到数组无法再拆分为止。

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;
    int result = 1;
    // 遍历每个元素，调用每个元素的hashCode方法
    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());
    return result;
}

大概看一下deepHashCode的方法：

for (Object element : a) {
            int elementHash = 0;
            if (element instanceof Object[])
                elementHash = deepHashCode((Object[]) element);
            else if (element instanceof byte[])
                elementHash = hashCode((byte[]) element);
            else if (element instanceof short[])
                elementHash = hashCode((short[]) element);
            else if (element instanceof int[])
                elementHash = hashCode((int[]) element);
            else if (element instanceof long[])
                elementHash = hashCode((long[]) element);
            else if (element instanceof char[])
                elementHash = hashCode((char[]) element);
            else if (element instanceof float[])
                elementHash = hashCode((float[]) element);
            else if (element instanceof double[])
                elementHash = hashCode((double[]) element);
            else if (element instanceof boolean[])
                elementHash = hashCode((boolean[]) element);
            else if (element != null)
                elementHash = element.hashCode();

            result = 31 * result + elementHash;
        }

deepEquals方法

同样，对于数组的equals方法，也是只比较第一层，如果有多层嵌套的话，我们可以使用deepEquals方法来比较。

toString方法

这个方法我们经常用到，这里就是返回数组的字符串表示形式，我们可以更直观的看到数组里保存的都是什么。

public static String toString(Object[] a) {
    if (a == null)
        return "null";

    int iMax = a.length - 1;
    if (iMax == -1)
        return "[]";
    // 内部使用StringBuilder来表示
    StringBuilder b = new StringBuilder();
    b.append('[');
    for (int i = 0; ; i++) {
        b.append(String.valueOf(a[i]));
        if (i == iMax)
            return b.append(']').toString();
        b.append(", ");
    }
}

同理，还有一个deepToString方法，用来返回嵌套数组的字符串表示形式。这里就不多说了。

setAll方法

public static <T> void setAll(T[] array, IntFunction<? extends T> generator)

使用生成器函数更新数组的每个元素，其中最后一个参数是JDK1.8之后的一个一元操作符，也是函数式接口。我们先看一个例子：

public static void main(String[] args) {
    int[] number = {1, 2, 3, 4, 5, 6};
    Arrays.setAll(number, x -> x * 3);
    System.out.println(Arrays.toString(number));
}

output：

[0, 3, 6, 9, 12, 15]

上述方法是为数组的每个元素乘以3，重新赋值给数组。
源码如下：

public static <T> void setAll(T[] array, IntFunction<? extends T> generator) {
    Objects.requireNonNull(generator);
    for (int i = 0; i < array.length; i++)
        array[i] = generator.apply(i);
}

通过调用函数式接口generator的apply方法来实现一元运算符操作。

parallelSetAll方法

同样，parallelSetAll方法是setAll的并行方式，通过借助JDK1.8的IntStream对象来实现。

public static <T> void parallelSetAll(T[] array, IntFunction<? extends T> generator) {
    Objects.requireNonNull(generator);
    IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.apply(i); });
}

spliterator方法

JDK8之后引入的并行迭代器，目的就是并行遍历数组中的元素。可以与原先的Iterator迭代器相比较。Spliterator是很有意思的一个类，如果有时间，再单独分析一下，现在先简单看一下源码即可：

public static <T> Spliterator<T> spliterator(T[] array) {
    return Spliterators.spliterator(array,Spliterator.ORDERED | Spliterator.IMMUTABLE);
}

stream方法

Stream也是JDK8之后引入的用于处理集合或者数组等类型的流，一般Stream配合lambda表达式使用，可以极大的提高我们编程的效率和程序的可读性。对于Stream，我们也是等有时间了单独分析一下，现在也是先简单看一下源码，顺便看一下简单的实现：

public static <T> Stream<T> stream(T[] array) {
    return stream(array, 0, array.length);
}

public static <T> Stream<T> stream(T[] array, int startInclusive, int endExclusive) {
    return StreamSupport.stream(spliterator(array, startInclusive, endExclusive), false);
}

看一下简单的实现：

public static void main(String[] args) {
    int[] number = {1, 2, 3, 4, 5, 6};
    Arrays.stream(number).forEach(n -> System.out.print(n + " "));
}

output：

1 2 3 4 5 6 

总结

Arrays的源码到现在基本上已经看完了，我们可以做个大致的总结：

1. Arrays的源码大致分为三种：parallel开头的都是并行处理的，deep开头的都是用于数组嵌套相关的操作，另一种就是我们常用的简单操作；
2. Arrays中基本上每个方法都有一系列的重载方法用于满足不同类型的操作，我们可以根据需要选择性的调用。

本文参考的链接如下：
https://docs.oracle.com/javase/8/docs/api/
读 Java Arrays 源码 笔记
快速排序实现及优化 | DualPivotQuicksort
Java8里面的java.util.Spliterator接口有什么用？

参考网站主要是：stackoverflow，搜索引擎：Google。