Arrays源码解析

参考：Java编程的逻辑

Arrays

类Arrays包含一些对数组操作的静态方法

数组排序 - 自定义比较器

sort可以接受一个比较器作为参数

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)

这个方法可以支持所有对象类型，只要传递这个类型对应的比较器就可以了。
Comparator就是比较器，它是一个接口，定义是：

public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
}

最主要的是compare这个方法，它比较两个对象，返回一个表示比较结果的值，-1表示o1小于o2，0表示相等，1表示o1大于o2。

排序是通过比较来实现的，sort方法在排序的过程中，需要对对象进行比较的时候，就调用比较器的compare方法。

String类有一个public静态成员，表示忽略大小写的比较器：

public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                     = new CaseInsensitiveComparator();

private static class CaseInsensitiveComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
        int n1 = s1.length();
        int n2 = s2.length();
        int min = Math.min(n1, n2);
        for (int i = 0; i < min; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 != c2) {
                c1 = Character.toUpperCase(c1);
                c2 = Character.toUpperCase(c2);
                if (c1 != c2) {
                    c1 = Character.toLowerCase(c1);
                    c2 = Character.toLowerCase(c2);
                    if (c1 != c2) {
                        // No overflow because of numeric promotion
                        return c1 - c2;
                    }
                }
            }
        }
        return n1 - n2;
    }
}

sort默认都是从小到大排序，如果希望按照从大到小排呢？
对于对象类型，可以指定一个不同的Comparator，可以用匿名内部类来实现Comparator，比如可以这样：

Collections类中有两个静态方法，可以返回逆序的Comparator，如

public static <T> Comparator<T> reverseOrder()
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)

传递比较器Comparator给sort方法，体现了程序设计中一种重要的思维方式，将不变和变化相分离，排序的基本步骤和算法是不变的，但按什么排序是变化的，sort方法将不变的算法设计为主体逻辑，而将变化的排序方式设计为参数，允许调用者动态指定，这也是一种常见的设计模式，它有一个名字，叫策略模式，不同的排序方式就是不同的策略。

哈希值

针对数组，计算一个数组的哈希值：

public static int hashCode(int a[]) 

计算hashCode的算法和String是类似的，代码如下：

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

    int result = 1;
    for (int element : a)
        result = 31 * result + element;

    return result;
}

String计算hashCode的算法也是类似的，数组中的每个元素都影响hash值，位置不同，影响也不同；
使用31一方面产生的哈希值更分散，另一方面计算效率也比较高。

toString

toString的实现利用了StringBuilder

public static String toString(int[] 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(", ");
    }
}

拷贝

copyOf和copyOfRange利用了 System.arraycopy

public static int[] copyOfRange(int[] original, int from, int to) {
    int newLength = to - from;
    if (newLength < 0)
        throw new IllegalArgumentException(from + " > " + to);
    int[] copy = new int[newLength];
    //复制的元素可能超出originl，剩下的为null：Math.min(original.length - from, newLength)
    //如original为1，2，要拷贝3个，则copy为1，2，null
    System.arraycopy(original, from, copy, 0,Math.min(original.length - from, newLength));
    return copy;
} 

二分查找

private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
                                     T key, Comparator<? super T> c) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        T midVal = a[mid];
        int cmp = c.compare(midVal, key);
        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

有两个标志low和high，表示查找范围，在while循环中，与中间值进行对比，大于中间值则在后半部分找(提高low)，否则在前半部分找(降低high)。

排序

对于基本类型的数组，Java采用的算法是双枢轴快速排序(Dual-Pivot Quicksort)，这个算法是Java 1.7引入的，在此之前，Java采用的算法是普通的快速排序，双枢轴快速排序是对快速排序的优化，新算法的实现代码位于类java.util.DualPivotQuicksort中。

对于对象类型，Java采用的算法是TimSort， TimSort也是在Java 1.7引入的，在此之前，Java采用的是归并排序，TimSort实际上是对归并排序的一系列优化，TimSort的实现代码位于类java.util.TimSort中。

在这些排序算法中，如果数组长度比较小，它们还会采用效率更高的插入排序。

为什么基本类型和对象类型的算法不一样呢？排序算法有一个稳定性的概念，所谓稳定性就是对值相同的元素，如果排序前和排序后，算法可以保证它们的相对顺序不变，那算法就是稳定的，否则就是不稳定的。

快速排序更快，但不稳定，而归并排序是稳定的。对于基本类型，值相同就是完全相同，所以稳定不稳定没有关系。但对于对象类型，相同只是比较结果一样，它们还是不同的对象，其他实例变量也不见得一样，稳定不稳定可能就很有关系了，所以采用归并排序。

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

public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
    int n = a.length, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
    else
        new ArraysParallelSortHelpers.FJObject.Sorter<T>
        (null, a,
         (T[])Array.newInstance(a.getClass().getComponentType(), n),
         0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
         MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}

public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}