Java 源码--Arrays

前言

数组比较特殊，一个数组属于一个对象，但是它的创建方式却不同于一般对象。

Java中的数组创建数组有以下三种方式：

// 第一种
int[] array = new int[5];
// 第二种
int[] array = {1, 2, 3, 4, 5};
// 第三种
int[] array = new int[]{1, 2, 3, 4, 5};

判断数组是否属于一个对象可使用下列语句：

System.out.println(new int[2] instanceof Object);

源码分析

接下来我们就来看一下对数据进行操作的工具类Arrays。

Arrays源代码看似很多，其实核心方法只有几个，Arrays给每种数据类型都提供了方法。

sort()

sort()方法有两种实现。第一种使用双轴快速排序算法。

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(Object[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a, fromIndex, toIndex);
    else
        ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}

parallelSort()

parallelSort()是Java8新增的并行排序算法，基于fork/join框架。PS：Fork/Join框架是Java7提供的一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。

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

ArraysParallelSortHelpers类中源码有些复杂，就先不探究它了。我们来比较一下sort()和parallelSort()的性能。从数组长度10开始，到长度100000000，打印俩个闹钟功能排序消耗的时间。

public static void main(String[] args) {
    for (int i = 10; i <= 100000000; i *= 10) {
        test(i);
    }
}

static void test(int limit) {
    IntStream intStream = new Random().ints(limit);
    int[] arr1 = intStream.toArray();
    int[] arr2 = Arrays.copyOf(arr1, arr1.length);

    long t1 = System.currentTimeMillis();
    Arrays.sort(arr1);
    long t2 = System.currentTimeMillis();
    Arrays.parallelSort(arr2);
    long t3 = System.currentTimeMillis();
    System.out.println("数组长度：" + limit + "\tsort：" + (t2 - t1) + "ms\tparallelSort：" + (t3 - t2) + "ms");
}

输出结果：

数组长度：10	sort：1ms	parallelSort：0ms
数组长度：100	sort：0ms	parallelSort：0ms
数组长度：1000	sort：0ms	parallelSort：1ms
数组长度：10000	sort：3ms	parallelSort：10ms
数组长度：100000	sort：16ms	parallelSort：22ms
数组长度：1000000	sort：105ms	parallelSort：48ms
数组长度：10000000	sort：1235ms	parallelSort：412ms
数组长度：100000000	sort：10194ms	parallelSort：4820ms

可以看出，从长度1000000开始，并行排序消耗的时间比串行排序消耗的时间变短。所以，在一般情况下，使用sort()方法即可，当数组长度很大时，使用parallelSort()方法。

parallelPrefix()

串行计算数组累加值。

public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
    Objects.requireNonNull(op);
    if (array.length > 0)
        new ArrayPrefixHelpers.CumulateTask<>
                (null, op, array, 0, array.length).invoke();
}

binarySearch()

二分查找。使用的前提是数组是已经从小到大排好序的。

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

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                 long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long 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.
}

equals()

判断两个数组是否相等，包括基本类型、对象的判等。基本类型的判等就是先判断结构上是否相等，然后调用ArraysSupport类的mismatch()方法判断内容的相等性。

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;

    return ArraysSupport.mismatch(a, a2, length) < 0;
}

fill()

填充。

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

copyOf()和copyOfRange()

复制和复制指定范围。

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

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

asList()

返回List。这里返回的ArrayList是Arrays中的一个静态内部类。

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

hashCode()

返回哈希值。

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

toString()

返回字符串。

public static String toString(long[] a) {
    if (a == null)
        return "null";
    int iMax = a.length - 1;
    if (iMax == -1)
        return "[]";

    StringBuilder b = new StringBuilder();
    b.append('[');
    for (int i = 0; ; i++) {
        b.append(a[i]);
        if (i == iMax)
            return b.append(']').toString();
        b.append(", ");
    }
}