資訊專(zhuān)欄INFORMATION COLUMN
摘要：容器相關(guān)的操作及其源碼分析說(shuō)明本文是基于分析的。源碼是個(gè)好東東，各種編碼技巧，再次佩服老外下一個(gè)主題是容器，。在了解容器之前我們先來(lái)看下重點(diǎn)的數(shù)據(jù)吧，還有工具類(lèi)。第一段話(huà)說(shuō)明返回一個(gè)指定數(shù)組的固定列表。
容器相關(guān)的操作及其源碼分析 說(shuō)明
1、本文是基于JDK 7 分析的。JDK 8 待我工作了得好好研究下。Lambda、Stream。
2、因?yàn)閭€(gè)人能力有限，只能以模仿的形式+自己的理解寫(xiě)筆記。如有不對(duì)的地方還請(qǐng)諒解。
3、記錄的比較亂，但是對(duì)自己加深印象還是蠻有作用的。
4、筆記放github了，有興趣的可以看看。喜歡的可以點(diǎn)個(gè)star。
5、讀過(guò)源碼的可以快速瀏覽一遍，也能加深自己的理解。
6、源碼是個(gè)好東東，各種編碼技巧，再次佩服老外?。?！
7、下一個(gè)主題是容器，gogogo。感覺(jué)可以的話(huà)可以關(guān)注哈。
1、Array、Arrays在了解容器之前我們先來(lái)看下重點(diǎn)的數(shù)據(jù)吧，還有Arrays工具類(lèi)。
首先看一個(gè)栗子，利用數(shù)組計(jì)算大數(shù)字。完整的點(diǎn)這里，重點(diǎn)思想就是計(jì)算數(shù)組中的每一個(gè)數(shù)，關(guān)鍵字是怎么進(jìn)和留。
/**
* Created by guo on 2018/2/2.
* 利用數(shù)組計(jì)算大數(shù)字
*/
public static int[] get(int[] ints, int num) {
//計(jì)算每一位
for (int i = 0; i < ints.length; i++) {
ints[i] *= num;
}
//進(jìn)和留
for (int i = ints.length - 1; i > 0; i--) {
//把個(gè)位數(shù)除10，加上前面的數(shù)
ints[i - 1] += ints[i] / 10;
//把最后的數(shù)模10，剩余個(gè)位數(shù)。1-9
ints[i] = ints[i] % 10;
}
return ints;
}
需要注意的還有一個(gè)System.arrayscopy()方法，那就是底層數(shù)組的拷貝，這個(gè)也是關(guān)鍵點(diǎn)。完整代碼
/**
* 底層實(shí)現(xiàn)的數(shù)組拷貝，是一個(gè)本地方法
* 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);
/**
* 參數(shù)：
* src：源，從哪個(gè)數(shù)組中拷貝數(shù)據(jù)
* dest：目標(biāo)：把數(shù)據(jù)拷貝到哪一個(gè)數(shù)組中
* srcpos：從原數(shù)組中哪一個(gè)位置開(kāi)始拷貝
* destPos：在目標(biāo)數(shù)組開(kāi)始存放的位置
* length：拷貝的個(gè)數(shù)
*/
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) { //不是最后一個(gè)元素
str = str + ",";
}
}
str = str + "]";
System.out.println(str);
}
其他內(nèi)容不是今天的重點(diǎn)，這里只是容器中需要數(shù)組的底層Copy。
ArraysArrays類(lèi)是Java中用于操作數(shù)組的類(lèi)，使用這個(gè)工具類(lèi)可以減少平常很多工作量。 主題框架參考這里，寫(xiě)的非常不錯(cuò)，
我們具體現(xiàn)看看它有哪些方法
1、sort 排序
2、binarySearch 二分查找(折半查找)
3、equals 比較
4、fill 填充
5、asList 轉(zhuǎn)列表 記得一個(gè)toArray嗎？
6、indexOf str首次出現(xiàn)的位置
6、hash 哈希(重點(diǎn))
7、toString 重寫(xiě)Object中方法
首先來(lái)看看排序的
/**
* Sorts the specified array into ascending numerical order.
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a);
}
需要關(guān)注的是底層默認(rèn)是按升序(asc),還有調(diào)用這個(gè)DualPivotQuicksort.sort(a)方法是什么鬼？中文意思為雙軸快速排序，它在性能上優(yōu)于傳統(tǒng)的單軸快速排序。 它是不穩(wěn)定的。
重點(diǎn)在這里O(n log(n)),還有這句話(huà)` 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傳進(jìn)去的是int[] a,接下來(lái)看看傳Object對(duì)象的。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);
}
在來(lái)看看帶泛型參數(shù)的，這個(gè)重點(diǎn)那，有三個(gè)點(diǎn)需要關(guān)注，Comparator，ClassCastException 和 TimSort算法 是從JDK 7 開(kāi)始默認(rèn)支持，
/** * 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); //注意這個(gè)TimSort }
整體上在看看這幾個(gè)到底啥意思？
/**
*大概意思就是舊的歸并算法使用了系統(tǒng)屬性，可能會(huì)導(dǎo)致循環(huán)依賴(lài)，不是能是靜態(tài)boolean，未來(lái)版本將移除
* 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();
}
//傳進(jìn)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);
}
//都要移除啊，看來(lái)的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);
}
/**
* 列表大小低于插入將優(yōu)先使用歸并算法，也要移除啊，
* 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
//小數(shù)組將使用普通的插入算法
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]. 這個(gè)可以理解，面試手寫(xiě)算法時(shí)，可以寫(xiě)這個(gè)那。
*/
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
從上面的邏輯可以看出，它的實(shí)現(xiàn)方式分為兩種，一種是通過(guò)Arrays中的歸并算法實(shí)現(xiàn)的,另外一種采用了TimSOrt算法，
這個(gè)排序算法是穩(wěn)定的，JDK8已經(jīng)刪除了，我們來(lái)看看8是怎么實(shí)現(xiàn)的。
/**
* 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); //還是這個(gè)
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并行啊，
這個(gè)也是重點(diǎn)，除傳入int[]之外其他都變成了parallelSort.慢慢來(lái)吧，先JDK7，在JDK 8.還有就是可以傳進(jìn)其他類(lèi)型，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);
}
}
二分查找，
注意接下來(lái)，我們只看泛型有關(guān)的方法，其他實(shí)現(xiàn)大同小異。因?yàn)榉盒秃苤匾?/p>
/**
* 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作用就是檢查邊界，看數(shù)據(jù)是否越界，會(huì)拋出ArrayIndexOutOfBoundsException
binarySearch0這是什么鬼？點(diǎn)進(jìn)去看看
要明白首先看參數(shù)
//fromIndex就是開(kāi)始索引(inclusive)，toIndex結(jié)束(exclusive)，key就是指定的數(shù)。 * @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; */
/** * 二分查找法(折半查找)：前提是在已經(jīng)排好序的數(shù)組中，通過(guò)將待查找的元素 * 與中間索引值對(duì)應(yīng)的元素進(jìn)行比較，若大于中間索引值對(duì)應(yīng)的元素，去右半邊查找， * 否則，去左邊查找。依次類(lèi)推。直到找到位置；找不到返回一個(gè)負(fù)數(shù) * * Like public version, but without range checks. *這里沒(méi)有邊界檢查，這才是二分查找重點(diǎn)。 */ 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; //開(kāi)始下標(biāo) int high = toIndex - 1; //結(jié)束下標(biāo) while (low <= high) { int mid = (low + high) >>> 1; //這里用了向右移2位(左邊補(bǔ)0)，/2 向左就是 *2. T midVal = a[mid]; int cmp = c.compare(midVal, key); //比較key是在左邊還是右邊 if (cmp < 0) //小于0意味著key大， low = mid + 1; //則去掉左邊的值。中間的索引+1就是新的開(kāi)始下標(biāo) else if (cmp > 0) //key比中間的小 high = mid - 1; //則去掉右邊的，中間下標(biāo)-1，就是新的結(jié)束下標(biāo) else return mid; // key found } return -(low + 1); // key not found.這里是-1 -(0 + 1) }
接下來(lái)在看看比較的，這個(gè)是重點(diǎn)。這里只看Object[]，其他還有很多，如int、byte、char
重點(diǎn)看這句話(huà)：
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，
兩個(gè)數(shù)組引用都為null，則返回true。
