## 04 Arrays、Collections、Objects 常用方法源碼解析 ### 引導語 我們在工作中都會寫工具類，但如何才能使寫出來的工具類更好用，也是有一些技巧的。本章內容以三種平時工作中經常使用的工具類為例，從使用案例出發，再看看底層源碼的實現，看看能否學習到一些工具類的技巧，以及三種工具類的實際使用場景。 下方是本專欄 GitHub 地址： 源碼解析：https://github.com/luanqiu/java8 文章 demo：https://github.com/luanqiu/java8_demo ### 1 工具類通用的特征 再看細節之前，我們先總結一下好的工具類都有哪些通用的特征寫法： 1. 構造器必須是私有的。這樣的話，工具類就無法被 new 出來，因為工具類在使用的時候，無需初始化，直接使用即可，所以不會開放出構造器出來。 2. 工具類的工具方法必須被 static、final 關鍵字修飾。這樣的話就可以保證方法不可變，并且可以直接使用，非常方便。 我們需要注意的是，盡量不在工具方法中，對共享變量有做修改的操作訪問（如果必須要做的話，必須加鎖），因為會有線程安全的問題。除此之外，工具類方法本身是沒有線程安全問題的，可以放心使用。 ### 2 Arrays Arrays 主要對數組提供了一些高效的操作，比如說排序、查找、填充、拷貝、相等判斷等等。我們選擇其中兩三看下，對其余操作感興趣的同學可以到 GitHub 上查看源碼解析。 #### 2.1 排序 Arrays.sort 方法主要用于排序，入參支持 int、long、double 等各種基本類型的數組，也支持自定義類的數組，下面我們寫個 demo 來演示一下自定義類數組的排序： **ArraysDemo.java** ``` package demo.two; import com.alibaba.fastjson.JSON; import com.google.common.collect.ImmutableList; import org.junit.Test; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.List; import lombok.Data; import lombok.extern.slf4j.Slf4j; /** * ArraysDemo *author wenhe *date 2019/8/3 */ @Slf4j public class ArraysDemo { @Test public void testSort(){ List<SortDTO> list = ImmutableList.of( new SortDTO("300"), new SortDTO("50"), new SortDTO("200"), new SortDTO("220") ); // 我們先把數組的大小初始化成 list 的大小 SortDTO[] array = new SortDTO[list.size()]; list.toArray(array); log.info("排序之前：{}", JSON.toJSONString(array)); Arrays.sort(array, Comparator.comparing(SortDTO::getSortTarget)); log.info("排序之后：{}", JSON.toJSONString(array)); } @Test public void testBinarySearch(){ List<SortDTO> list = ImmutableList.of( new SortDTO("300"), new SortDTO("50"), new SortDTO("200"), new SortDTO("220") ); SortDTO[] array = new SortDTO[list.size()]; list.toArray(array); log.info("搜索之前：{}", JSON.toJSONString(array)); Arrays.sort(array, Comparator.comparing(SortDTO::getSortTarget)); log.info("先排序，結果為：{}", JSON.toJSONString(array)); int index = Arrays.binarySearch(array, new SortDTO("200"), Comparator.comparing(SortDTO::getSortTarget)); if(index<0){ throw new RuntimeException("沒有找到 200"); } log.info("搜索結果：{}", JSON.toJSONString(array[index])); } @Data class SortDTO { private String sortTarget; public SortDTO(String sortTarget) { this.sortTarget = sortTarget; } } class SortDTO1 implements Comparable<SortDTO1> { private String sortTarget; public SortDTO1(String sortTarget) { this.sortTarget = sortTarget; } @Override public int compareTo(SortDTO1 o) { return o.sortTarget.compareTo(sortTarget); } } @Test public void testMax() { Collection<SortDTO1> list = ImmutableList.of( new SortDTO1("300"), new SortDTO1("50"), new SortDTO1("200"), new SortDTO1("220") ); Collections.max(list); } @Test public void testSearch(){ //0~10 System.out.println("(0 + 10-1) >>> 1:"+((0 + 10-1) >>> 1)); System.out.println("(0 + 11-1) >>> 1:"+((0 + 11-1) >>> 1)); System.out.println("(1 + 11-1) >>> 1:"+((1 + 11-1) >>> 1)); System.out.println("(1 + 10-1) >>> 1:"+((1 + 10-1) >>> 1)); } } ``` ``` @Data//自定義類 class SortDTO { private String sortTarget; public SortDTO(String sortTarget) { this.sortTarget = sortTarget; } } @Test public void testSort(){ List<SortDTO> list = ImmutableList.of( new SortDTO("300"), new SortDTO("50"), new SortDTO("200"), new SortDTO("220") ); // 我們先把數組的大小初始化成 list 的大小 SortDTO[] array = new SortDTO[list.size()]; list.toArray(array); log.info("排序之前：{}", JSON.toJSONString(array)); Arrays.sort(array, Comparator.comparing(SortDTO::getSortTarget)); log.info("排序之后：{}", JSON.toJSONString(array)); } ``` 輸出結果為： 排序之前： ``` [{"sortTarget":"300"},{"sortTarget":"50"},{"sortTarget":"200"},{"sortTarget":"220"}] ``` 排序之后： ``` [{"sortTarget":"200"},{"sortTarget":"220"},{"sortTarget":"300"},{"sortTarget":"50"}] ``` 從輸出的結果中可以看到，排序之后的數組已經是有順序的了，也可以看到 sort 方法支持兩個入參：要排序的數組和外部排序器。 大家都說 sort 方法排序的性能較高，主要原因是 sort 使用了雙軸快速排序算法，具體算法就不細說了。 #### 2.1 二分查找法 Arrays.binarySearch 方法主要用于快速從數組中查找出對應的值。其支持的入參類型非常多，如 byte、int、long 各種類型的數組。返回參數是查找到的對應數組下標的值，如果查詢不到，則返回負數。  我們寫了一個 demo 如下： ``` @Test public void testBinarySearch(){ List<SortDTO> list = ImmutableList.of( new SortDTO("300"), new SortDTO("50"), new SortDTO("200"), new SortDTO("220") ); SortDTO[] array = new SortDTO[list.size()]; list.toArray(array); log.info("搜索之前：{}", JSON.toJSONString(array)); Arrays.sort(array, Comparator.comparing(SortDTO::getSortTarget)); log.info("先排序，結果為：{}", JSON.toJSONString(array)); int index = Arrays.binarySearch(array, new SortDTO("200"), Comparator.comparing(SortDTO::getSortTarget)); if(index<0){ throw new RuntimeException("沒有找到 200"); } log.info("搜索結果：{}", JSON.toJSONString(array[index])); } ``` 輸出的結果為： 搜索之前： ``` [{"sortTarget":"300"},{"sortTarget":"50"},{"sortTarget":"200"},{"sortTarget":"220"}] ``` 先排序，結果為： ``` [{"sortTarget":"200"},{"sortTarget":"220"},{"sortTarget":"300"},{"sortTarget":"50"}] ``` 搜索結果： ``` {"sortTarget":"200"} ``` 從上述代碼中我們需要注意兩點： 1. 如果被搜索的數組是無序的，一定要先排序，否則二分搜索很有可能搜索不到，我們 demo 里面也先對數組進行了排序； 2. 搜索方法返回的是數組的下標值。如果搜索不到，返回的下標值就會是負數，這時我們需要判斷一下正負。如果是負數，還從數組中獲取數據的話，會報數組越界的錯誤。demo 中對這種情況進行了判斷，如果是負數，會提前拋出明確的異常。 接下來，我們來看下二分法底層代碼的實現： ``` // a：我們要搜索的數組，fromIndex：從那里開始搜索，默認是0； toIndex：搜索到何時停止，默認是數組大小 // key：我們需要搜索的值 c：外部比較器 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) { // 如果比較器 c 是空的，直接使用 key 的 Comparable.compareTo 方法進行排序 // 假設 key 類型是 String 類型，String 默認實現了 Comparable 接口，就可以直接使用 compareTo 方法進行排序 if (c == null) { // 這是另外一個方法，使用內部排序器進行比較的方法 return binarySearch0(a, fromIndex, toIndex, key); } int low = fromIndex; int high = toIndex - 1; // 開始位置小于結束位置，就會一直循環搜索 while (low <= high) { // 假設 low =0，high =10，那么 mid 就是 5，所以說二分的意思主要在這里，每次都是計算索引的中間值 int mid = (low + high) >>> 1; T midVal = a[mid]; // 比較數組中間值和給定的值的大小關系 int cmp = c.compare(midVal, key); // 如果數組中間值小于給定的值，說明我們要找的值在中間值的右邊 if (cmp < 0) low = mid + 1; // 我們要找的值在中間值的左邊 else if (cmp > 0) high = mid - 1; else // 找到了 return mid; // key found } // 返回的值是負數，表示沒有找到 return -(low + 1); // key not found. } ``` 二分的主要意思是每次查找之前，都找到中間值，然后拿我們要比較的值和中間值比較，根據結果修改比較的上限或者下限，通過循環最終找到相等的位置索引，以上代碼實現比較簡潔，大家可以在自己理解的基礎上，自己復寫一遍。 #### 2.2 拷貝 數組拷貝我們經常遇到，有時需要拷貝整個數組，有時需要拷貝部分，比如 ArrayList 在 add（擴容） 或 remove（刪除元素不是最后一個） 操作時，會進行一些拷貝。拷貝整個數組我們可以使用 copyOf 方法，拷貝部分我們可以使用 copyOfRange 方法，以 copyOfRange 為例，看下底層源碼的實現： ``` // original 原始數組數據 // from 拷貝起點 // to 拷貝終點 public static char[] copyOfRange(char[] original, int from, int to) { // 需要拷貝的長度 int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); // 初始化新數組 char[] copy = new char[newLength]; // 調用 native 方法進行拷貝，參數的意思分別是： // 被拷貝的數組、從數組那里開始、目標數組、從目的數組那里開始拷貝、拷貝的長度 System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } ``` 從源碼中，我們發現，Arrays 的拷貝方法，實際上底層調用的是 System.arraycopy 這個 native 方法，如果你自己對底層拷貝方法比較熟悉的話，也可以直接使用。 ### 3 Collections Collections 是為了方便使用集合而產生的工具類，Arrays 方便數組使用，Collections 是方便集合使用。 Collections 也提供了 sort 和 binarySearch 方法，sort 底層使用的就是 Arrays.sort 方法，binarySearch 底層是自己重寫了二分查找算法，實現的邏輯和 Arrays 的二分查找算法完全一致，這兩個方法上 Collections 和 Arrays 的內部實現很類似，接下來我們來看下 Collections 獨有的特性。 #### 3.1 求集合中最大、小值 提供了 max 方法來取得集合中的最大值，min 方法來取得集合中的最小值，max 和 min 方法很相似的，我們以 max 方法為例來說明一下，max 提供了兩種類型的方法，一個需要傳外部排序器，一個不需要傳排序器，但需要集合中的元素強制實現 Comparable 接口，后者的泛型定義很 有意思，我們來看下（從右往左看）：  從這段源碼中，我們可以學習到兩點： 1. max 方法泛型 T 定義得非常巧妙，意思是泛型必須繼承 Object 并且實現 Comparable 的接口。一般讓我們來定義的話，我們可以會在方法里面去判斷有無實現 Comparable 的接口，這種是在運行時才能知道結果。而這里泛型直接定義了必須實現 Comparable 接口，在編譯的時候就可告訴使用者，當前類沒有實現 Comparable 接口，使用起來很友好； 2. 給我們提供了實現兩種排序機制的好示例：自定義類實現 Comparable 接口和傳入外部排序器。兩種排序實現原理類似，但實現有所差別，我們在工作中如果需要些排序的工具類時，可以效仿。 #### 3.2 多種類型的集合 Collections 對原始集合類進行了封裝，提供了更好的集合類給我們，一種是線程安全的集合，一種是不可變的集合，針對 List、Map、Set 都有提供，我們先來看下線程安全的集合： #### 3.2.1 線程安全的集合 線程安全的集合方法都是 synchronized 打頭的，如下：  從方法命名我們都可以看出來，底層是通過 synchronized 輕量鎖來實現的，我們以 synchronizedList 為例來說明 下底層的實現：  可以看到 List 的所有操作方法都被加上了 synchronized 鎖，所以多線程對集合同時進行操作，是線程安全的。 #### 3.2.1 不可變的集合 得到不可變集合的方法都是以 unmodifiable 開頭的。這類方法的意思是，我們會從原集合中，得到一個不可變的新集合，新集合只能訪問，無法修改；一旦修改，就會拋出異常。這主要是因 為只開放了查詢方法，其余任何修改操作都會拋出異常，我們以unmodifiableList 為例來看下底層實現機制：  #### 3.2.2 小結 以上兩種 List 其實解決了工作中的一些困惑，比如說 ArrayList 是線程不安全的，然后其內部數組很容易被修改，有的時候，我們希望 List 一旦生成后，就不能被修改，Collections 對 List 重新進行了封裝，提供了兩種類型的集合封裝形式，從而解決了工作中的一些煩惱，如果你平時使用 List 時有一些煩惱，也可以學習此種方式，自己對原始集合進行封裝，來解決 List 使用過程中的不方便。 ### 4 Objects 對于 Objects，我們經常使用的就是兩個場景，相等判斷和判空。 #### 4.1 相等判斷 Objects 有提供 equals 和 deepEquals 兩個方法來進行相等判斷，前者是判斷基本類型和自定義類的，后者是用來判斷數組的，我們來看下底層的源碼實現：  從源碼中，可以看出 Objects 對基本類型和復雜類型的對象，都有著比較細粒度的判斷，可以放心使用。 #### 4.2 為空判斷  Objects 提供了各種關于空的一些判斷，isNull 和 nonNull 對于對象是否為空返回 Boolean 值，requireNonNull 方法更加嚴格，如果一旦為空，會直接拋出異常，我們需要根據生活的場景選擇使用。 ### 5 面試題 #### 5.1 工作中有沒有遇到特別好用的工具類，如何寫好一個工具類 答：有的，像 Arrays 的排序、二分查找、Collections 的不可變、線程安全集合類、Objects 的判空相等判斷等等工具類，好的工具類肯定很好用，比如說使用 static final 關鍵字對方法進行修飾，工具類構造器必須是私有等等手段來寫好工具類。 #### 5.2 寫一個二分查找算法的實現 答：可以參考 Arrays 的 binarySearch 方法的源碼實現。 #### 5.3 如果我希望 ArrayList 初始化之后，不能被修改，該怎么辦 答：可以使用 Collections 的 unmodifiableList 的方法，該方法會返回一個不能被修改的內部類集合，這些集合類只開放查詢的方法，對于調用修改集合的方法會直接拋出異常。 ### 總結 從三大工具類中，我們不僅學習到了如何寫好一個工具類，還熟悉了三大工具類的具體使用姿勢，甚至了解了其底層的源碼實現，有興趣的話，可以自己也可以仿照寫個好用的工具類加深學習。