Arrays.java是Java中用來(lái)操作數(shù)組的類(lèi)澡谭。使用這個(gè)工具類(lèi)可以減少平常很多的工作量诈嘿。了解其實(shí)現(xiàn)算谈，可以避免一些錯(cuò)誤的用法嘉冒。

它提供的操作包括：

1. 排序 sort
2. 查找 binarySearch()
3. 比較 equals
4. 填充 fill
5. 轉(zhuǎn)列表 asList()
6. 哈希 Hash()
7. 轉(zhuǎn)字符串 toString()

這個(gè)類(lèi)的代碼量很多曹货，Java1.7中有4000多行。因?yàn)槊恳环N基本類(lèi)型都做了兼容讳推，所以整個(gè)類(lèi)真正邏輯不多顶籽。下面簡(jiǎn)單介紹一下它各個(gè)功能的實(shí)現(xiàn)：

排序

這里的排序?qū)崿F(xiàn)有兩種

一種是為基本類(lèi)型數(shù)組設(shè)計(jì)的，它的對(duì)外接口有兩種银觅，如下:

//whole array
public static void sort(primitive[] a);

//sub array
public static void sort(primitive[] a, int fromIndex, int toIndex);

它們的具體實(shí)現(xiàn)方式是一樣的都是調(diào)用了DualPivotQuicksort.sort(...)方法礼饱。這個(gè)方法的中文含義是 雙軸快速排序。它在性能上優(yōu)于傳統(tǒng)的單軸快速排序究驴。

算法的邏輯可以參考國(guó)外一篇博客
如果想要閱讀源碼可以參考我的另一篇博客雙軸快速排序源碼閱讀筆記

它是不穩(wěn)定的

另一種是為Object對(duì)象設(shè)計(jì)的镊绪，它要求傳進(jìn)來(lái)的數(shù)組對(duì)象必須實(shí)現(xiàn)Comparable接口。
它提供的接口如下：

// whole array, default asec
public static void sort(Object[] a);

// subArray, default asec
public static void sort(Object[] a, int fromIndex, int toIndex);

還有帶泛型參數(shù)的接口洒忧，它需要指定一個(gè)比較器蝴韭。

// whole array with comparator
public static <T> void sort(T[] a, Comparator<? super T> c);

// sub array with comparator
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c);

他的實(shí)現(xiàn)方式如下：

// java/utils/Arrays.java
static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
}

//sort 方法的實(shí)現(xiàn)
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
       legacyMergeSort(a);
    else
       //與TimSort的邏輯是相同的
       ComparableTimSort.sort(a);
}

//legacyMergeSort
private static void legacyMergeSort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}                    

//歸并排序
    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        // 小數(shù)組直接進(jìn)行普通插入排序
        if (length < INSERTIONSORT_THRESHOLD) {
             ///...
            return;
        }

        //下面是歸并排序的實(shí)現(xiàn)，
        ///...
    }

從上面的邏輯可以看出來(lái)熙侍，它的實(shí)現(xiàn)方式分為兩種万皿，一種是通過(guò)Arrays.java中的歸并排序?qū)崿F(xiàn)的摧找，另一種采用了TimSort算法。其中Arrays.java中的歸并排序的邏輯相對(duì)簡(jiǎn)單牢硅，是一種插入排序與傳統(tǒng)歸并排序的結(jié)合蹬耘。當(dāng)待排序的數(shù)組小于INSERTIONSROT_THERSHOLD的時(shí)候直接進(jìn)行插入排序，不再遞歸减余。TimSort算法也是一種插入排序與歸并排序結(jié)合的算法综苔，不過(guò)它的細(xì)節(jié)優(yōu)化要比Arrays.java中的算法做的多。詳細(xì)介紹可以參考維基百科或者我的TimSort 源碼筆記位岔。

兩種算法的切換依靠運(yùn)行時(shí)系統(tǒng)變量的設(shè)置如筛。具體參考StackOverFlow上的一篇回答。我們默認(rèn)情況下是不打開(kāi)這個(gè)開(kāi)關(guān)的抒抬，也就是說(shuō)沒(méi)有特殊要求的情況下杨刨，我們默認(rèn)使用TimSort算法來(lái)實(shí)現(xiàn)排序。從注釋上來(lái)看擦剑，在未來(lái)某個(gè)版本妖胀，Arrays.java中的merge方法將會(huì)被刪除掉。

這個(gè)排序方法是 穩(wěn)定 的惠勒。

查找

Arrays.java中只提供了二分查找赚抡。二分查找的前提就是數(shù)組是經(jīng)過(guò)升序排序的，所以使用之前務(wù)必確保數(shù)組是有序的纠屋。

調(diào)用的接口比較簡(jiǎn)單：

public static int binarySearch(primative[] a, primative key);
public static int binarySearch(primative[] a, int fromIndex, int toIndex, primative key);
public static int binarySearch(Object[] a, Object key);
public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key);
public static <T> int binarySearch(T[] a, T key, Comparator< ? super T> c);
public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key,Comparator<? super T> c);

equals

這個(gè)也比較簡(jiǎn)單涂臣，equals方法與==的不同大家應(yīng)該都很熟悉了，這里直接貼出接口:

    // 基本類(lèi)型
    public static boolean equals(long[] a, long[] a2) {
        //...
    }
    // 對(duì)象
    public static boolean equals(Object[] a, Object[] a2) {
        //...
    }
    // 高維數(shù)組的equal比較售担，通過(guò)遞歸實(shí)現(xiàn)
    // 這里沒(méi)有對(duì)循環(huán)引用進(jìn)行檢查赁遗，如果兩個(gè)如組同時(shí)存在循環(huán)引用的情況下可能出現(xiàn)死循環(huán)的風(fēng)險(xiǎn)。
    public static boolean deepEquals(Object[] a1, Object[] a2) {
       //...
    }

fill 填充

批量初始化的時(shí)候不要自己寫(xiě)for循環(huán)了族铆，已經(jīng)有人幫我們寫(xiě)好了吼和。

// 基本類(lèi)型批量賦值
public static void fill(int[] a, int fromIndex, int toIndex, int val) {
    rangeCheck(a.length, fromIndex, toIndex);
    for (int i = fromIndex; i < toIndex; i++)
        a[i] = val;
}
// 對(duì)象批量賦值
public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
    rangeCheck(a.length, fromIndex, toIndex);
    for (int i = fromIndex; i < toIndex; i++)
        a[i] = val;
}

復(fù)制

數(shù)組復(fù)制的最終實(shí)現(xiàn)是調(diào)用了JVM中的方法。具體沒(méi)有深究骑素，但在數(shù)據(jù)量大的時(shí)候應(yīng)該能快些炫乓。

// @file Arrays.java
// 基本類(lèi)型的復(fù)制，從0開(kāi)始到指定長(zhǎng)度
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;
}
// 基本類(lèi)型復(fù)制献丑，從指定起點(diǎn)到指定終點(diǎn)
public static byte[] copyOfRange(byte[] original, int from, int to) {
    int newLength = to - from;
    if (newLength < 0)
        throw new IllegalArgumentException(from + " > " + to);
    byte[] copy = new byte[newLength];
    System.arraycopy(original, from, copy, 0,
                    Math.min(original.length - from, newLength));
    return copy;
}
//這里是泛型數(shù)組的復(fù)制末捣， 結(jié)合泛型進(jìn)階中的內(nèi)容，這里好理解很多创橄。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    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;
}

// @file System.java
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

// 

轉(zhuǎn)換成列表 asList

將一組對(duì)象轉(zhuǎn)換成列表箩做，這里一定要注意返回的ArrayList并非平常用的java.util.ArrayList ，而是Arrays.java中定義的一個(gè)簡(jiǎn)單的靜態(tài)內(nèi)部類(lèi)--ArrayList妥畏。它不支持添加和移除元素邦邦，不支持?jǐn)U容安吁。

@file java/util/Arrays.java

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

//注意，此ArrayList非平常用的ArrayList;這里的實(shí)現(xiàn)比較簡(jiǎn)單燃辖。
//不能擴(kuò)容鬼店，所以不支持add,remove等操作。
private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable {
    /// ...
}

哈希 hash

高維數(shù)組的哈希計(jì)算黔龟，采用遞歸實(shí)現(xiàn)妇智。同樣，如果自己的某個(gè)元素直接或者間接持有自己氏身，會(huì)出現(xiàn)死循環(huán)巍棱。

    // 基本類(lèi)型哈希
    public static int hashCode(long a[]) {
       // ...
    }
    
    // 對(duì)象哈希
    public static int hashCode(Object a[]) {
       //...
    }
    
    // 高維數(shù)組哈希，采用遞歸實(shí)現(xiàn)蛋欣。如果自己的某個(gè)元素直接或者間接持有自己航徙，會(huì)出現(xiàn)死訊環(huán)，
    // 所以`Object[]`最好直接使用`hashcode(Object)`陷虎。
    public static int deepHashCode(Object a[]) {
       //...
    }

toString

有了這個(gè)方法到踏，打Log的時(shí)候就不需要寫(xiě)循環(huán)了。
這里的高維數(shù)組直接或者間接持有自己的情況不會(huì)出現(xiàn)死循環(huán)泻红。因?yàn)檫@里做了特殊處理夭禽，用一個(gè)Set保存了打印過(guò)的數(shù)組霞掺。

    // 基本類(lèi)型
    public static String toString(int[] a) {
       // ...
    }
    // 對(duì)象
    public static String toString(Object[] a) {
        // ...
    }
    // 高維數(shù)組toString(). 這里處理了自我持有的問(wèn)題谊路。
    public static String deepToString(Object[] a) {
        // ...
        deepToString(a, buf, new HashSet<Object[]>());
        return buf.toString();
    }
    // 真正的實(shí)現(xiàn)方法， 遞歸實(shí)現(xiàn)菩彬。
    // 使用了一個(gè)Set來(lái)存儲(chǔ)已經(jīng)打印過(guò)的類(lèi)缠劝，如果再次出現(xiàn)這個(gè)對(duì)象，直接打印[...]
    private static void deepToString(Object[] a, StringBuilder buf,
                                     Set<Object[]> dejaVu) {
       //...
    }