資訊專欄INFORMATION COLUMN
摘要：容器相關的操作及其源碼分析說明本文是基于分析的。源碼是個好東東，各種編碼技巧，再次佩服老外下一個主題是容器，。在了解容器之前我們先來看下重點的數據吧，還有工具類。第一段話說明返回一個指定數組的固定列表。
容器相關的操作及其源碼分析 說明
1、本文是基于JDK 7 分析的。JDK 8 待我工作了得好好研究下。Lambda、Stream。
2、因為個人能力有限，只能以模仿的形式+自己的理解寫筆記。如有不對的地方還請諒解。
3、記錄的比較亂，但是對自己加深印象還是蠻有作用的。
4、筆記放github了，有興趣的可以看看。喜歡的可以點個star。
5、讀過源碼的可以快速瀏覽一遍，也能加深自己的理解。
6、源碼是個好東東，各種編碼技巧，再次佩服老外！！！
7、下一個主題是容器，gogogo。感覺可以的話可以關注哈。
1、Array、Arrays在了解容器之前我們先來看下重點的數據吧，還有Arrays工具類。
首先看一個栗子，利用數組計算大數字。完整的點這里，重點思想就是計算數組中的每一個數，關鍵字是怎么進和留。
/**
* Created by guo on 2018/2/2.
* 利用數組計算大數字
*/
public static int[] get(int[] ints, int num) {
//計算每一位
for (int i = 0; i < ints.length; i++) {
ints[i] *= num;
}
//進和留
for (int i = ints.length - 1; i > 0; i--) {
//把個位數除10，加上前面的數
ints[i - 1] += ints[i] / 10;
//把最后的數模10，剩余個位數。1-9
ints[i] = ints[i] % 10;
}
return ints;
}
需要注意的還有一個System.arrayscopy()方法，那就是底層數組的拷貝，這個也是關鍵點。完整代碼
/**
* 底層實現的數組拷貝，是一個本地方法
* void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
* src the source array.
* srcPos starting position in the source array.
* dest the destination array.
* destPos starting position in the destination data.
* length the number of array elements to be copied.
*/
System.arraycopy(src,-1,dest,2,3);
/**
* 參數：
* src：源，從哪個數組中拷貝數據
* dest：目標：把數據拷貝到哪一個數組中
* srcpos：從原數組中哪一個位置開始拷貝
* destPos：在目標數組開始存放的位置
* length：拷貝的個數
*/
static void arrayCopy(int[] src, int srcPos, int[] dest, int destPos, int length) {
if(srcPos < 0 || destPos < 0 || length < 0) {
throw new RuntimeException("出異常了，重新檢查");
}
for (int index = srcPos; index < srcPos + length; index++) {
dest[destPos] = src[index];
destPos++;
}
}
static void print(int[] arr) {
String str = "[";
for (int i = 0; i < arr.length; i++) {
str += arr[i];
if (i != arr.length - 1) { //不是最后一個元素
str = str + ",";
}
}
str = str + "]";
System.out.println(str);
}
其他內容不是今天的重點，這里只是容器中需要數組的底層Copy。
ArraysArrays類是Java中用于操作數組的類，使用這個工具類可以減少平常很多工作量。 主題框架參考這里，寫的非常不錯，
我們具體現看看它有哪些方法
1、sort 排序
2、binarySearch 二分查找(折半查找)
3、equals 比較
4、fill 填充
5、asList 轉列表 記得一個toArray嗎？
6、indexOf str首次出現的位置
6、hash 哈希(重點)
7、toString 重寫Object中方法
首先來看看排序的
/**
* Sorts the specified array into ascending numerical order.
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a);
}
需要關注的是底層默認是按升序(asc),還有調用這個DualPivotQuicksort.sort(a)方法是什么鬼？中文意思為雙軸快速排序，它在性能上優于傳統的單軸快速排序。 它是不穩定的。
重點在這里O(n log(n)),還有這句話` and is typically
faster than traditional (one-pivot) Quicksort implementations.` 具體看大佬的博文友情提示
/**
* This class implements the Dual-Pivot Quicksort algorithm by
* Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*/
final class DualPivotQuicksort {
}
上面的sort傳進去的是int[] a,接下來看看傳Object對象的。All elements in the array must implement the Comparable interface.
/**
* Sorts the specified array of objects into ascending order, according
* to the {@linkplain Comparable natural ordering} of its elements.
* All elements in the array must implement the {@link Comparable}
* interface. Furthermore, all elements in the array must be
* mutually comparable (that is, {@code e1.compareTo(e2)} must
* not throw a {@code ClassCastException} for any elements {@code e1}
* and {@code e2} in the array).
*/
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a);
}
在來看看帶泛型參數的，這個重點那，有三個點需要關注，Comparator，ClassCastException 和 TimSort算法 是從JDK 7 開始默認支持，
/** * Sorts the specified array of objects according to the order induced by * the specified comparator. All elements in the array must be * mutually comparable by the specified comparator must not throw a * *ClassCastException for any elements and in the array. */ public staticvoid sort(T[] a, Comparator c) { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, c); //注意這個TimSort }
整體上在看看這幾個到底啥意思？
/**
*大概意思就是舊的歸并算法使用了系統屬性，可能會導致循環依賴，不是能是靜態boolean，未來版本將移除
* 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();
}
//傳進Object的排序，
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a);
}
/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
//都要移除啊，看來的JDK8了
/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a,
int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
Object[] aux = copyOfRange(a, fromIndex, toIndex);
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
}
/**
* 列表大小低于插入將優先使用歸并算法，也要移除啊，
* Tuning parameter: list size at or below which insertion sort will be
* used in preference to mergesort.
* To be removed in a future release.
*/
private static final int INSERTIONSORT_THRESHOLD = 7;
/**
* Src is the source array that starts at index 0
* Dest is the (possibly larger) array destination with a possible offset
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset to generate corresponding low, high in src
* To be removed in a future release.
*/
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// Insertion sort on smallest arrays
//小數組將使用普通的插入算法
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; ilow &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Merge sorted halves (now in src) into dest
}
----------------------------------------------------------------------------
/**
* Swaps x[a] with x[b]. 這個可以理解，面試手寫算法時，可以寫這個那。
*/
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
從上面的邏輯可以看出，它的實現方式分為兩種，一種是通過Arrays中的歸并算法實現的,另外一種采用了TimSOrt算法，
這個排序算法是穩定的，JDK8已經刪除了，我們來看看8是怎么實現的。
/**
* Sorts the specified array of objects according to the order induced by
* the specified comparator. All elements in the array must be
* mutually comparable by the specified comparator (that is,
* {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
* for any elements {@code e1} and {@code e2} in the array).
* @since 1.8
*/
@SuppressWarnings("unchecked")
public static void parallelSort(T[] a, Comparator cmp) {
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0); //還是這個
else
new ArraysParallelSortHelpers.FJObject.Sorter
(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, cmp).invoke();
}
需要注意的是方法名變成了parallelSort并行啊，
這個也是重點，除傳入int[]之外其他都變成了parallelSort.慢慢來吧，先JDK7，在JDK 8.還有就是可以傳進其他類型，char、long、byte。etc(等)。
/**
* Checks that {@code fromIndex} and {@code toIndex} are in
* the range and throws an exception if they aren"t.
*/
private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if (toIndex > arrayLength) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
二分查找，
注意接下來，我們只看泛型有關的方法，其他實現大同小異。因為泛型很重要。
/**
* Searches the specified array for the specified object using the binary
* search algorithm. The array must be sorted into ascending order
* according to the specified comparator (as by the
* {@link #sort(Object[], Comparator) sort(T[], Comparator)}
* method) prior to making this call. If it is
* not sorted, the results are undefined.
* If the array contains multiple
* elements equal to the specified object, there is no guarantee which one
* will be found.
*/
public static int binarySearch(T[] a, T key, Comparator c) {
return binarySearch0(a, 0, a.length, key, c);
}
/**
* Searches a range of
* the specified array for the specified object using the binary
* search algorithm.
* The range must be sorted into ascending order
* according to the specified comparator (as by the
* {@link #sort(Object[], int, int, Comparator)
* sort(T[], int, int, Comparator)}
* method) prior to making this call.
* If it is not sorted, the results are undefined.
* If the range contains multiple elements equal to the specified object,
* there is no guarantee which one will be found.
*/
public static int binarySearch(T[] a, int fromIndex, int toIndex,
T key, Comparator c) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key, c);
}
rangeCheck作用就是檢查邊界，看數據是否越界，會拋出ArrayIndexOutOfBoundsException
binarySearch0這是什么鬼？點進去看看
要明白首先看參數
//fromIndex就是開始索引(inclusive)，toIndex結束(exclusive)，key就是指定的數。 * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; */
/** * 二分查找法(折半查找)：前提是在已經排好序的數組中，通過將待查找的元素 * 與中間索引值對應的元素進行比較，若大于中間索引值對應的元素，去右半邊查找， * 否則，去左邊查找。依次類推。直到找到位置；找不到返回一個負數 * * Like public version, but without range checks. *這里沒有邊界檢查，這才是二分查找重點。 */ private staticequalsint binarySearch0(T[] a, int fromIndex, int toIndex, T key, Comparator c) { if (c == null) { //先判斷 return binarySearch0(a, fromIndex, toIndex, key); } int low = fromIndex; //開始下標 int high = toIndex - 1; //結束下標 while (low <= high) { int mid = (low + high) >>> 1; //這里用了向右移2位(左邊補0)，/2 向左就是 *2. T midVal = a[mid]; int cmp = c.compare(midVal, key); //比較key是在左邊還是右邊 if (cmp < 0) //小于0意味著key大， low = mid + 1; //則去掉左邊的值。中間的索引+1就是新的開始下標 else if (cmp > 0) //key比中間的小 high = mid - 1; //則去掉右邊的，中間下標-1，就是新的結束下標 else return mid; // key found } return -(low + 1); // key not found.這里是-1 -(0 + 1) }
接下來在看看比較的，這個是重點。這里只看Object[]，其他還有很多，如int、byte、char
重點看這句話：
In other words, the two arrays are equal if
they contain the same elements in the same order.
Also, two array references are considered equal if both are null
以相同的順序，并且互相包含，則返回true，
兩個數組引用都為null，則返回true。
