Arrays源碼閱讀
提供了排序，并行排序墙贱，二分查找热芹，范圍填充，相等比較惨撇，深度比較等方法伊脓，深入理解一下實現(xiàn)方法
私有屬性：
MIN_ARRAY_SORT_GRAN
private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
當(dāng)數(shù)組長度小于MIN_ARRAY_SORT_GRAN將不會執(zhí)行并行排序算法，源碼注釋中說原因是因為長度太小魁衙，劃分任務(wù)也會很小报腔，會導(dǎo)致內(nèi)存爭用，反而不會加速剖淀，所以設(shè)置一個閾值纯蛾。
NaturalOrder
static final class NaturalOrder implements Comparator<Object> {
@SuppressWarnings("unchecked")
public int compare(Object first, Object second) {
return ((Comparable<Object>)first).compareTo(second);
}
static final NaturalOrder INSTANCE = new NaturalOrder();
}
一個用于自然排序的靜態(tài)內(nèi)部類，實現(xiàn)了Comparator接口纵隔，重寫了compare方法翻诉，在方法中對比較類型進行了Comparable類型強轉(zhuǎn)炮姨，調(diào)用了Comparable接口的compareTo方法，要求比較的對象實現(xiàn)Comparable接口
LegacyMergeSort
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}
安全檢查碰煌，若用戶自己確定可以比較大小舒岸，則userRequested為true。這個類未來會被棄用芦圾，若未使用蛾派，不推薦使用。不過可以到時候看看安全檢查的細節(jié)//TODO
INSERTIONSORT_THRESHOLD
private static final int INSERTIONSORT_THRESHOLD = 7;
若元素數(shù)量小于7个少，則采用插入算法
ArrayList
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
這是調(diào)用asList（）后得到的就是這個類洪乍，一個只讀的類，不是util.Arraylist稍算。
方法
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);
}
sort底層調(diào)用DualPivotQuicksort典尾，雙軸快排役拴，一個優(yōu)化了排序方法糊探，根據(jù)元素數(shù)量或是歸并分組長度和數(shù)量，選擇優(yōu)化過的成對插入排序河闰，雙軸快排或歸并算法科平。
sort支持int，short姜性，long，char，byte纵刘，float,double土榴，自定義類型數(shù)組。
[fromIndex,toIndex)左閉右開
- 自定義類型
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, 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);
}
安全檢查儡炼，legacyMergeSort(a)：底層調(diào)用歸并排序妓湘，若遞歸中，若元素小于INSERTIONSORT_THRESHOLD乌询，則直接插入排序
若沒有榜贴，調(diào)用ComparableTimSort.sort，一個優(yōu)化過的歸并排序妹田，考慮了最壞情況唬党，并且與插入排序混合使用。
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
和上面類似
parallelSort 并行排序
當(dāng)數(shù)據(jù)量較大時鬼佣，并行排序會有較大的差異驶拱，數(shù)據(jù)量小的話影響不大，中等的話晶衷，并行排序會比sort慢幾毫秒屯烦。
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：支持將一個任務(wù)拆分成多個小任務(wù)并行計算然后合并坷随。（見ForkJoinPool，挖個坑驻龟，看多線程的時候?qū)?/TODO）
不太理解parallelSort(int[] a)里面為什么不調(diào)用parallelSort(int[] a, int fromIndex, int toIndex)温眉，代碼部分重復(fù)了呀？//TODO
如果滿足條件則會調(diào)用arraysparallelsorthelpers中的每個基本類型對應(yīng)的類的sort函數(shù))如果滿足條件則會調(diào)用ArraysParallelSortHelpers中的每個基本類型對應(yīng)的類的sort函數(shù)翁狐。
parallelPrefix
并行类溢，lambda//TODO
binarySearch 二分查找
- 基本類型
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
public static int binarySearch(int[] a, int fromIndex, int toIndex,
int key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
該方法會返回一個查找的key的index，如果沒找到露懒，就會記錄這個值可以插入數(shù)組的index闯冷，返回-（index+1）
Object[] a = { 1 , 2 ,3, 5 , 6 , 7 };
System.out.println ( Arrays.binarySearch (a , 3));//2
System.out.println ( Arrays.binarySearch (a , 4));//-4
binarySearch(int[] a, int key)在內(nèi)部調(diào)用了binarySearch(int[] a, int fromIndex, int toIndex,int key)，上面parallelSort（）為什么不這么做呢懈词？
- 自定義類型
public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,T key, Comparator<? super T> c) {
return binarySearch0(a, 0, a.length, key, c);
}
如果類沒有實現(xiàn)Comparable或其他情況蛇耀，那么查找的時候也要把比較函數(shù)傳進來
- equals 和 deepEquals
public static boolean equals(Object[] a, Object[] 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++) {
Object o1 = a[i];
Object o2 = a2[i];
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return true;
}
各種類型都差不多，先比較地址坎弯，再判斷null纺涤，再長度，最后一個一個元素判斷抠忘，不過自定義類型還需要再判斷一次取出的元素是不是null的撩炊！ deepEquanls用來比較多維的，因為多維存的是引用崎脉，直接用equals比較的是地址拧咳，如果是object類型，會調(diào)用類型自己的equals方法
- fill
public static void fill(Object[] a, Object val) {
for (int i = 0, len = a.length; i < len; i++)
a[i] = val;
}
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;
}
初始化數(shù)組囚灼，填充范圍內(nèi)全為指定值
-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;
}
先進行類型判斷 底層調(diào)用的是本地方法System.arraycopy骆膝，會對指定的長度進行合法判斷，copyOfRange與copyOf類似
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
- asList
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
返回一個Arrays內(nèi)部定義的一個ArrayList灶体，若要轉(zhuǎn)化為數(shù)組阅签，基本類型就用循環(huán)，實例對象則如下
Integer[] a = { 1 , 2 , 5 , 6 , 7 , 4 , 3 , 0 };
Integer[] b = new Integer[ a.length ];
Arrays.asList(a).toArray (b);
- hashCode 和 deepHashCode
基本類型：
int
public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
return result;
}
循環(huán)疊加結(jié)果赃春，result = 31 * result + element;
double
public static int hashCode(double a[]) {
if (a == null)
return 0;
int result = 1;
for (double element : a) {
long bits = Double.doubleToLongBits(element);
result = 31 * result + (int)(bits ^ (bits >>> 32));
}
return result;
}
小數(shù)比較的話有精讀問題愉择，這里使用Double的doubleToLongBits方法處理的。
Double.doubleToLongBits(element);將double的元素轉(zhuǎn)換為longbit
object類型和基本類型差不多织中，不過多了一個deepHashCode
public static int deepHashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
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;
}
return result;
}
當(dāng)數(shù)組里存放數(shù)組時锥涕，若用hashCode（object[])，數(shù)組會根據(jù)數(shù)組地址去計算hashcode狭吼，而用deepHashCode則會計算數(shù)組中的值
hashcode 例子：
int[] m = { 1 };
int[] n = { 1 };
Object[] a = { 1 , 2 , 5 , 6 , 7 , 4 , 3 , m };
Object[] b = { 1 , 2 , 5 , 6 , 7 , 4 , 3 , n };
System.out.println (Arrays.hashCode (a)==Arrays.hashCode (b));//false
System.out.println (Arrays.deepHashCode (a)==Arrays.deepHashCode (b));//true
- toStirng 和deepToString
public static String toString(Object[] 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(String.valueOf(a[i]));
if (i == iMax)
return b.append(']').toString();
b.append(", ");
}
}
deepToStriing层坠，原理和之前deepHashCode差不多，太長了就不貼了刁笙，需要的時候可以點進去看看破花，里面還是有一些細節(jié)注意谦趣，比如初始化StringBuilder大小，回溯座每，還用了個set前鹅，用...表示重復(fù)元素
剩下一堆java 8的方法，留坑//TODO
