Java源碼系列三-工具類Arrays

​ 今天分享java的源碼的第三彈，Arrays這個工具類的源碼。因為近期在復(fù)習數(shù)據(jù)結(jié)構(gòu)，了解到Arrays里面的排序算法和二分查找等的實現(xiàn)，收益匪淺，決定研讀一下Arrays這個類的源碼。不足之處，歡迎在評論區(qū)交流和指正。

1.認識Arrays這個類：

​ 首先它在java的utils包下，屬于Java Collections Framework中的一員。它的初衷就是一個工具類，封裝了操縱數(shù)組的各種方法，比如排序，二分查找，數(shù)組的拷貝等等。滿足了我們?nèi)粘?shù)組操做的基本需求，了解它的底層實現(xiàn)，不僅能幫助我們更好的使用它，而且還能培養(yǎng)我們更好的代碼的思維。

2.構(gòu)造方法

​ 因為是一個工具類，所以它的構(gòu)造方法定義為私有的，且所有的實現(xiàn)方法都是靜態(tài)方法。也就是說這個類不能被實例化，通俗的講，就是不能new。只能通過類名來直接調(diào)用方法(反射除外)。這樣做的目的是強化該類不可實列化的能力，突出該類作為工具類的根本職能。源碼如下：

// Suppresses default constructor, ensuring non-instantiability. private Arrays() {}

3.常用方法的解析

3.1快速插入集合元素的方法asList(T... a)：

基本使用:

/** * 數(shù)組轉(zhuǎn)化為集合 */ @Test public void toArrayTest(){ List<Integer> list = Arrays.asList(2,4,5,6,6); for (Integer integer : list) { System.out.print(integer+' '); } }

輸出結(jié)果：

2 4 5 6 6

看一下源碼：

@SafeVarargs @SuppressWarnings('varargs') public static <T> List<T> asList(T... a) { return new ArrayList<>(a); }// ArrayList的構(gòu)造方法和屬性 private final E[] a; ArrayList(E[] array) { a = Objects.requireNonNull(array); }

​ 這個方法的實現(xiàn)比較簡單，就是調(diào)用ArrayList的構(gòu)造方法，并且參數(shù)是一個數(shù)組，也就是將我們要構(gòu)造的數(shù)傳入到ArrayList的構(gòu)造方法中去，進行實例化。

3.2.二分查找的方法

Arrays類中的二分查找八種基本類型都有涉及，但都是方法的重載。其實現(xiàn)原理都是一樣，這里以int類型為例，進行說明。

基本使用：

@Test public void binarySearchTest(){ int[] arrays = {1,4,6,7,9,3}; // 查找元素為7的下標值 int result = Arrays.binarySearch(arrays,7); System.out.println(result); }

結(jié)果：

3

這個方法主要涉及的一下三個方法：

// 我們常用的方法public static int binarySearch(int[] a, int key) { return binarySearch0(a, 0, a.length, key); }/* 參數(shù)說明如下： a 待查找的數(shù)組 fromIndex 查找的開始位置 toIndex 查找的結(jié)束位置 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. }

當然實現(xiàn)的核心方法還是上述私有方法binarySearch0()這個方法，實現(xiàn)的邏輯也不復(fù)雜。

第一步就是聲明兩個變量存儲查找區(qū)域的開始和結(jié)束。

第二步 循環(huán)，比較，不斷的縮小比較的范圍，直到找到數(shù)組中的值和目標值相同，返回下標，如果沒有找到就返回一個負數(shù)也就是下面的這l兩行代碼：

return mid; // key foundreturn -(low + 1); // key not found.

我認為：這個二分法實現(xiàn)的亮點就在于求中間值的移位運算：

int mid = (low + high) >>> 1;

有人就納悶了，為什么還要使用移位運算，除法不行嗎？主要還是為了性能考量。因為移位運算占兩個機器周期，而乘除法占四個運算周期，所以移位運算的速度肯定比乘除法的運算速度快很多，計算量小了可能區(qū)別不大，但是計算量很大，就區(qū)別很明顯了。

3.3 數(shù)組的拷貝

@Test public void testCopyArrange(){ // 原數(shù)組 int [] srcArray = {11,2,244,5,6,54}; // 拷貝原數(shù)組長度為3的部分 int[] descArray = Arrays.copyOf(srcArray,3); System.out.println(Arrays.toString(descArray)); }

輸出結(jié)果：

[11, 2, 244]

源碼分析：

/* 參數(shù)說明： original 原數(shù)組 newLength 拷貝的數(shù)組長度 */public static int[] copyOf(int[] original, int newLength) { // 聲明一個新數(shù)組的長度，存儲拷貝后的數(shù)組 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);

分析： 主要還是調(diào)用了本地的方法arraycopy完成數(shù)組的指定長度拷貝，可以看到源碼并沒有對數(shù)組的長度進行檢查，主要是arraycopy()這個方法時使了Math.min()方法，保證了你聲明的長度在一個安全的范圍之內(nèi)，如果你拷貝的長度超出了數(shù)組的長度，就默認拷貝整個數(shù)組。至于native修飾的方法的使用，可以看看這里。

System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));

當然如果需要拷貝數(shù)組指定的區(qū)間 ，可以使用Arrays的copyOfRange(int[] original, int from, int to) 實現(xiàn)原理和arraycopy()方法的原理類似：

@Test public void testCopy(){ int [] srcArray = {11,2,244,5,6,54}; // 拷貝指定范圍的數(shù)組 int[] descArray = Arrays.copyOfRange(srcArray,0,3); System.out.println(Arrays.toString(descArray)); }

輸出結(jié)果：

[11, 2, 244]

注： copyOfRange(int[] original, int from, int to)中的參數(shù)to是不包含在拷貝的結(jié)果中的，上述的例子，就只能拷貝到索引為2的元素，不包含索引為3的元素，這點需要注意。

3.4 equals方法

主要重寫了Object類的equals方法，用來比較兩個數(shù)組內(nèi)容是否相等，也就是他們中的元素是否相等。

基本用法：

@Test public 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); }

結(jié)果：

truefalse

看源碼之前，有必要講一下重寫了equals方法之后，兩個對象比較的是值，也就是他們的內(nèi)容，這點非常的重要。重寫equals方法的注意事項可以移步這里。

源碼如下：

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; }

源碼說明如下：

源碼判斷了四次，分別是首地址比較，是否為空，以及長度的比較，最后對于數(shù)組的各個元素進行比較。

有必要說明下第一個判斷，也就是首地址的比較。當我們聲明一個數(shù)組變量時，這個變量就代表數(shù)組的首地址，看下面這個代碼：

@Test public void equalTest(){ int[] array ={1,2,3,4}; System.out.println(array); }

結(jié)果：

[I@4f2410ac // [代表數(shù)組 I代表整數(shù) @分隔符 后邊內(nèi)存地址十六進制

​ 這表示的是一個地址。還是因為在聲明一個數(shù)組時，會在堆里面創(chuàng)建一塊內(nèi)存區(qū)域，但是這塊內(nèi)存區(qū)域相對于堆來說可能很小，不好找。為了方便查找，所以將數(shù)組內(nèi)存中的首地址表示出來。虛擬機將地址傳給變量名array。這也是引用類型，傳的是地址，也就是理解成array指向內(nèi)存地址（類似于家庭的地址），每次運行可能地址都不一樣，因為虛擬機開辟的內(nèi)存空間可能不一樣。

理解了這個，那么a==a2就好理解了，如果兩個數(shù)組內(nèi)存地址都相同，那么兩個數(shù)組的肯定是相等的。

還有我認為程序?qū)懙谋容^好的地方就是源碼中對數(shù)組每個元素的比較，也就是下面這段代碼；

for (int i=0; i<length; i++) if (a[i] != a2[i]) return false; return true;

使用a[i] != a2[i] 作為判斷條件，就可以減少比較次數(shù)，提高了性能。試想一下如果這里是相等的比較，那每次都要遍歷整個數(shù)組，如果數(shù)據(jù)量大了，無疑在性能上會慢很多。又一次感嘆到源碼的魅力。

3.5 排序相關(guān)的方法sort()和parallelSort()

Arrays 這個類中主要涉及了兩種類型的排序方法串行 sort()和并行parallelSort()這兩個方法，當然對象的排序和基本類型的排序也不太一樣。這里還是以int[]類型的為例。進行說明。

首先比較兩個方法的性能：

public final int UPPER_LIMIT = 0xffffff; final int ROUNDS = 10; final int INCREMENT = 5; final int INIT_SIZE = 1000; @Test public void sortAndParallelSortTest(){ // 構(gòu)造不同容量的集合 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); } // 輸出結(jié)果 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(); }

部分的測試的結(jié)果：

=======================測試排序的時間=========Capacity1000ParallelSort6.284099999999999E-4Sort5.599599999999999E-4比較快的排序是：Sort=======================測試排序的時間=========Capacity5000ParallelSort0.00163599Sort0.0018313699999999995比較快的排序是：ParallelSort

可以看到在數(shù)據(jù)量比較小的情況下，使用sort()方法更快，一旦過了一個閾值，就是ParallelSort()這個方法性能好。這個閾值是多少呢。

我們先看一下parallelSort的源碼:

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(); }

可以看到當數(shù)組的長度小于MIN_ARRAY_SORT_GRAN或者p = ForkJoinPool.getCommonPoolParallelism()) == 1 (在單線程下)的時候，調(diào)用sort()排序的底層實現(xiàn)的DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);Arrays的開頭定義的常量如下：

private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; // 這個值是8192

對比兩者，也就是在數(shù)組的長度比較大或者是多線程的情況下，優(yōu)先考慮并行排序，否則使用串行排序。

兩個排序的核心思想：

sort()方法的核心還是快排和優(yōu)化后的歸并排序, 快速排序主要是對哪些基本類型數(shù)據(jù)（int,short,long等）排序， 而合并排序用于對對象類型進行排序。 parallelSort()它使用并行排序-合并排序算法。它將數(shù)組分成子數(shù)組，這些子數(shù)組本身先進行排序然后合并。

由于并行排序和串行排序的底層比較復(fù)雜，且篇幅有限，想要詳細了解底層實現(xiàn)的話，可以移步到串行排序和并行排序

3.6 toString方法

基本用法:

@Test public void toStringTest(){ int[] array = {1,3,2,5}; System.out.println(Arrays.toString(array)); }

結(jié)果：

[1, 3, 2, 5]

源碼分析如下：

public static String toString(int[] a) { // 1.判斷數(shù)組的大小 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(', '); } }

具體的實現(xiàn)，已在源碼的注釋中進行了說明。這個方法對于基本數(shù)據(jù)類型來說，很方便的遍歷數(shù)組。

追本溯源，方能闊步前行。

參考資料

https://www.jb51.net/article/180770.htmhttps://www.jb51.net/article/116323.htm

javaSE的官方問檔。

到此這篇關(guān)于java中的Arrays這個工具類你真的會用嗎(一文秒懂)的文章就介紹到這了,更多相關(guān)java中Arrays工具類內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！