Java源碼系列三-工具類Arrays
? 今天分享java的源碼的第三彈，Arrays這個工具類的源碼。因為近期在復習數據結構，了解到Arrays里面的排序算法和二分查找等的實現，收益匪淺，決定研讀一下Arrays這個類的源碼。不足之處，歡迎在評論區交流和指正。
1.認識Arrays這個類：
? 首先它在java的utils包下，屬于Java Collections Framework中的一員。它的初衷就是一個工具類，封裝了操縱數組的各種方法，比如排序，二分查找，數組的拷貝等等。滿足了我們日常對數組操做的基本需求，了解它的底層實現，不僅能幫助我們更好的使用它，而且還能培養我們更好的代碼的思維。
2.構造方法
? 因為是一個工具類，所以它的構造方法定義為私有的，且所有的實現方法都是靜態方法。也就是說這個類不能被實例化，通俗的講，就是不能new。只能通過類名來直接調用方法(反射除外)。這樣做的目的是強化該類不可實列化的能力，突出該類作為工具類的根本職能。源碼如下：
|
1
2
3
4
|
// Suppresses default constructor, ensuring non-instantiability. private Arrays() {} |
3.常用方法的解析
3.1快速插入集合元素的方法asList(T... a)：
基本使用:
|
1
2
3
4
5
6
7
8
9
10
|
/** * 數組轉化為集合 */@Testpublic void toArrayTest(){ List<Integer> list = Arrays.asList(2,4,5,6,6); for (Integer integer : list) { System.out.print(integer+" "); }} |
輸出結果：
2 4 5 6 6
看一下源碼：
|
1
2
3
4
5
6
7
8
9
10
11
|
@SafeVarargs @SuppressWarnings("varargs") public static <T> List<T> asList(T... a) { return new ArrayList<>(a); }// ArrayList的構造方法和屬性 private final E[] a; ArrayList(E[] array) { a = Objects.requireNonNull(array); } |
? 這個方法的實現比較簡單，就是調用ArrayList的構造方法，并且參數是一個數組，也就是將我們要構造的數傳入到ArrayList的構造方法中去，進行實例化。
3.2.二分查找的方法
Arrays類中的二分查找八種基本類型都有涉及，但都是方法的重載。其實現原理都是一樣，這里以int類型為例，進行說明。
基本使用：
|
1
2
3
4
5
6
7
|
@Testpublic void binarySearchTest(){ int[] arrays = {1,4,6,7,9,3}; // 查找元素為7的下標值 int result = Arrays.binarySearch(arrays,7); System.out.println(result);} |
結果：
3
這個方法主要涉及的一下三個方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
// 我們常用的方法public static int binarySearch(int[] a, int key) { return binarySearch0(a, 0, a.length, key); }/* 參數說明如下： a 待查找的數組 fromIndex 查找的開始位置 toIndex 查找的結束位置 key 查找的目標值 */public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { // 進行異常檢查 rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { // 找出查找范圍的中間值 int mid = (low + high) >>> 1; int midVal = a[mid]; // 進行比較 if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } |
當然實現的核心方法還是上述私有方法binarySearch0()這個方法，實現的邏輯也不復雜。
第一步就是聲明兩個變量存儲查找區域的開始和結束。
第二步 循環，比較，不斷的縮小比較的范圍，直到找到數組中的值和目標值相同，返回下標，如果沒有找到就返回一個負數也就是下面的這l兩行代碼：
|
1
2
|
return mid; // key foundreturn -(low + 1); // key not found. |
我認為：這個二分法實現的亮點就在于求中間值的移位運算：
|
1
|
int mid = (low + high) >>> 1; |
有人就納悶了，為什么還要使用移位運算，除法不行嗎？主要還是為了性能考量。因為移位運算占兩個機器周期，而乘除法占四個運算周期，所以移位運算的速度肯定比乘除法的運算速度快很多，計算量小了可能區別不大，但是計算量很大，就區別很明顯了。
3.3 數組的拷貝
|
1
2
3
4
5
6
7
8
9
|
@Testpublic void testCopyArrange(){ // 原數組 int [] srcArray = {11,2,244,5,6,54}; // 拷貝原數組長度為3的部分 int[] descArray = Arrays.copyOf(srcArray,3); System.out.println(Arrays.toString(descArray));} |
輸出結果：
[11, 2, 244]
源碼分析：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/* 參數說明： original 原數組 newLength 拷貝的數組長度 */public static int[] copyOf(int[] original, int newLength) { // 聲明一個新數組的長度，存儲拷貝后的數組 int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); |
分析： 主要還是調用了本地的方法arraycopy完成數組的指定長度拷貝，可以看到源碼并沒有對數組的長度進行檢查，主要是arraycopy()這個方法時使了Math.min()方法，保證了你聲明的長度在一個安全的范圍之內，如果你拷貝的長度超出了數組的長度，就默認拷貝整個數組。至于native修飾的方法的使用，可以看看這里。
|
1
2
|
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); |
當然如果需要拷貝數組指定的區間 ，可以使用Arrays的copyOfRange(int[] original, int from, int to) 實現原理和arraycopy()方法的原理類似：
|
1
2
3
4
5
6
7
|
@Test public void testCopy(){ int [] srcArray = {11,2,244,5,6,54}; // 拷貝指定范圍的數組 int[] descArray = Arrays.copyOfRange(srcArray,0,3); System.out.println(Arrays.toString(descArray)); } |
輸出結果：
[11, 2, 244]
注： copyOfRange(int[] original, int from, int to)中的參數to是不包含在拷貝的結果中的，上述的例子，就只能拷貝到索引為2的元素，不包含索引為3的元素，這點需要注意。
3.4 equals方法
主要重寫了Object類的equals方法，用來比較兩個數組內容是否相等，也就是他們中的元素是否相等。
基本用法：
|
1
2
3
4
5
6
7
|
@Testpublic void equalTest(){ int[] array ={1,2,3,4}; int[] result ={1,2,3,4}; System.out.println(Arrays.equals(array,result)); System.out.println(array == result);} |
結果：
true
false
看源碼之前，有必要講一下重寫了equals方法之后，兩個對象比較的是值，也就是他們的內容，這點非常的重要。重寫equals方法的注意事項可以移步這里。
源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static boolean equals(int[] a, int[] 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++) if (a[i] != a2[i]) return false; return true;} |
源碼說明如下：
源碼判斷了四次，分別是首地址比較，是否為空，以及長度的比較，最后對于數組的各個元素進行比較。
有必要說明下第一個判斷，也就是首地址的比較。當我們聲明一個數組變量時，這個變量就代表數組的首地址，看下面這個代碼：
|
1
2
3
4
5
6
|
@Testpublic void equalTest(){ int[] array ={1,2,3,4}; System.out.println(array); } |
結果：
[I@4f2410ac // [代表數組 I代表整數 @分隔符 后邊內存地址十六進制
? 這表示的是一個地址。還是因為在聲明一個數組時，會在堆里面創建一塊內存區域，但是這塊內存區域相對于堆來說可能很小，不好找。為了方便查找，所以將數組內存中的首地址表示出來。虛擬機將地址傳給變量名array。這也是引用類型，傳的是地址，也就是理解成array指向內存地址（類似于家庭的地址），每次運行可能地址都不一樣，因為虛擬機開辟的內存空間可能不一樣。
理解了這個，那么a==a2就好理解了，如果兩個數組內存地址都相同，那么兩個數組的肯定是相等的。
還有我認為程序寫的比較好的地方就是源碼中對數組每個元素的比較，也就是下面這段代碼；
|
1
2
3
4
5
|
for (int i=0; i<length; i++) if (a[i] != a2[i]) return false; return true; |
使用a[i] != a2[i] 作為判斷條件，就可以減少比較次數，提高了性能。試想一下如果這里是相等的比較，那每次都要遍歷整個數組，如果數據量大了，無疑在性能上會慢很多。又一次感嘆到源碼的魅力。
3.5 排序相關的方法sort()和parallelSort()
Arrays 這個類中主要涉及了兩種類型的排序方法串行 sort()和并行parallelSort()這兩個方法，當然對象的排序和基本類型的排序也不太一樣。這里還是以int[]類型的為例。進行說明。
首先比較兩個方法的性能：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
public final int UPPER_LIMIT = 0xffffff;final int ROUNDS = 10;final int INCREMENT = 5;final int INIT_SIZE = 1000;@Testpublic void sortAndParallelSortTest(){ // 構造不同容量的集合 for (int capacity = INIT_SIZE; capacity < UPPER_LIMIT ; capacity*= INCREMENT) { ArrayList<Integer> list = new ArrayList<>(capacity); for (int j = 0; j < capacity; j++) { list.add((int) (Math.random()*capacity)); } double avgTimeOfParallelSort = 0; double avgTimeOfSort = 0; for (int j = 0; j <= ROUNDS ; j++) { // 每次排序都打亂順序 Collections.shuffle(list); Integer[] arr1 = list.toArray(new Integer[capacity]); Integer[] arr2 = arr1.clone(); avgTimeOfParallelSort += counter(arr1,true); avgTimeOfSort += counter(arr2, false); } // 輸出結果 output(capacity,avgTimeOfParallelSort/ROUNDS,avgTimeOfSort/ROUNDS); }}private void output(int capacity, double v, double v1) { System.out.println("=======================測試排序的時間========="); System.out.println("Capacity"+capacity); System.out.println("ParallelSort"+v); System.out.println("Sort"+v1); System.out.println("比較快的排序是："+(v < v1 ? "ParallelSort":"Sort"));}// 計算消耗的時間private double counter(Integer[] arr1, boolean b) { long begin,end; begin = System.nanoTime(); if(b){ Arrays.parallelSort(arr1); }else{ Arrays.parallelSort(arr1); } end = System.nanoTime(); return BigDecimal.valueOf(end-begin,9).doubleValue();} |
部分的測試的結果：
=======================測試排序的時間=========
Capacity1000
ParallelSort6.284099999999999E-4
Sort5.599599999999999E-4
比較快的排序是：Sort
=======================測試排序的時間=========
Capacity5000
ParallelSort0.00163599
Sort0.0018313699999999995
比較快的排序是：ParallelSort
可以看到在數據量比較小的情況下，使用sort()方法更快，一旦過了一個閾值，就是ParallelSort()這個方法性能好。這個閾值是多少呢。
我們先看一下parallelSort的源碼:
|
1
2
3
4
5
6
7
8
9
10
11
|
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(); } |
可以看到當數組的長度小于MIN_ARRAY_SORT_GRAN或者p = ForkJoinPool.getCommonPoolParallelism()) == 1 (在單線程下)的時候，調用sort()排序的底層實現的DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);Arrays的開頭定義的常量如下：
|
1
|
private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; // 這個值是8192 |
對比兩者，也就是在數組的長度比較大或者是多線程的情況下，優先考慮并行排序，否則使用串行排序。
兩個排序的核心思想：
- sort()方法的核心還是快排和優化后的歸并排序, 快速排序主要是對哪些基本類型數據（int,short,long等）排序， 而合并排序用于對對象類型進行排序。
- parallelSort()它使用并行排序-合并排序算法。它將數組分成子數組，這些子數組本身先進行排序然后合并。
由于并行排序和串行排序的底層比較復雜，且篇幅有限，想要詳細了解底層實現的話，可以移步到串行排序和并行排序
3.6 toString方法
基本用法:
|
1
2
3
4
5
|
@Testpublic void toStringTest(){ int[] array = {1,3,2,5}; System.out.println(Arrays.toString(array));} |
結果：
[1, 3, 2, 5]
源碼分析如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static String toString(int[] a) { // 1.判斷數組的大小 if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; // 2.使用StringBuilder進行追加 StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); }} |
具體的實現，已在源碼的注釋中進行了說明。這個方法對于基本數據類型來說，很方便的遍歷數組。
追本溯源，方能闊步前行。
javaSE的官方問檔。
到此這篇關于java中的Arrays這個工具類你真的會用嗎(一文秒懂)的文章就介紹到這了,更多相關java中Arrays工具類內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://www.cnblogs.com/chentang/p/13210127.html
