集合相關的常用工具類
- 2020 年 3 月 11 日
- 筆記
1. 簡介
Java中的集合類既可以當做放其他數據的容器，又可以當做常見的數據結構使用。Java中提供了很多好用的工具類來操作這些集合類。本篇博客就來介紹下常用的集合工具類。集合常用的工具類大體可以分為3類：
- JDK本身提供的工具類；
- Guava提供的工具類；
- Apache common-Collection提供的工具類
2. JDK提供的工具類
主要由下面三個：
- Arrays
- Collections
- Objects
Arrays是操作數組對象的工具類，Collections是操作集合對象的工具類。Objects是操作引用數據類型對象的工具類。
Arrays的常用方法：
普通排序：
Arrays.sort(int[] a) Arrays.sort(int[] a, int fromIndex, int toIndex)其他非boolean基礎數據類型的數組對象以及實現Comparable接口的類的數組對象均有此方法。
並行排序：JDK1.8新增。
Arrays.parallelSort(int[] a) Arrays.parallelSort(int[] a, int fromIndex, int toIndex)其他非boolean基礎數據類型的數組對象以及實現Comparable接口的類的數組對象均有此方法。
並行計算：JDK1.8新增，支持函數式編程，根據傳入的方法進行一次計算。
Arrays.parallelPrefix(int[] array, IntBinaryOperator op) Arrays.parallelPrefix(int[] array, int fromIndex, int toIndex, IntBinaryOperator op)其他非boolean基礎數據類型的數組對象以及實現Comparable接口的類的數組對象均有此方法。
二分法查找：前提是該數組已經進行了排序
Arrays.binarySearch(int[] a, int key) Arrays.binarySearch(int[] a, int fromIndex, int toIndex, int key)其他非boolean基礎數據類型的數組對象以及實現Comparable接口的類的數組對象均有此方法。
判斷兩個數組是否相等：
Arrays.equals(int[] a, int[] a2)其他基礎數據類型的數組對象以及Object數組對象均有此方法,Object調用的是equels()方法。
對數組進行填充：
Arrays.fill(int[] a, int val) Arrays.fill(int[] a, int fromIndex, int toIndex, int val)其他基礎數據類型的數組對象以及Object數組對象均有此方法。
複製數組：
Arrays.copyOf(int[] original, int newLength)，返回賦值後的數組，數組長度為newLength。 Arrays.copyOfRange(int[] original, int from, int to)其他基礎數據類型的數組對象以及Object數組對象均有此方法。Object數組為淺複製，即複製的是引用。
toString: 將元素用","隔開，包裹在"[ ]"內。
Arrays.toString(int[] a)其他基礎數據類型的數組對象以及Object數組對象均有此方法。Object數組為引用地址。
Arrays.deepToString(Object[] a)方法內部調用了a.toString()。
更改元素值：JDK1.8新增，支持函數式編程
setAll(int[] array, IntUnaryOperator generator) setAll(long[] array, IntToLongFunction generator) setAll(double[] array, IntToDoubleFunction generator) setAll(T[] array, IntFunction<? extends T> generator)該類方法支持這四種類型。每種類型均有對應的並行設置方法parallelSetAll()
數組轉集合：
Arrays.asList(T... a) 返回List<T>如果是Object數組對象，該方法生成的集合對象持有的是數組對象對應元素的引用。
生成並行遍歷的Spliterator，JDK1.8新增
Arrays.spliterator(int[] array) Arrays.spliterator(int[] array, int startInclusive, int endExclusive)int、long、double和實現了Spliterator接口的類具有該類型方法。
生成Stream類，JDK1.8新增
Arrays.stream(int[] a) Arrays.stream(int[] array, int startInclusive, int endExclusive)int、long、double和實現了Stream接口的類具有該類型方法。
JDK1.8新增的方法基本都是與函數式變成或多核並行操作相關。
接下來看看Arrays常用方法的源碼。
1，Arrays.asList()的源碼實現分析：
public static <T> List<T> asList(T... a) { return new ArrayList<>(a); // 為什麼JDK的設計者不直接使用ava.util.ArrayList呢？ }這個ArrayList是數組的內部實現類，不是經常是用的java.util.ArrayList。這個內部類ArrayList是一個固定大小的list，不支持list.add()和list.remove()，這裡一定要注意。
2，Arrays.sort()的源碼實現分析：
public static void sort(int[] a) { DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); }這裡用到了DualPivotQuicksort.sort()。DualPivotQuicksort是java.util包下的final類，專門用來對基礎數據類型的數據進行排序的。DualPivotQuicksort.sort()源碼分析：
static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) { // 對於數組長度小的情況採用快速排序 if (right - left < QUICKSORT_THRESHOLD) { // QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; } // 歸併+快排 （引入了TimSort的run的概念） ...省略算法源碼 }快排算法sort()的源碼分析：
private static void sort(int[] a, int left, int right, boolean leftmost) { int length = right - left + 1; // 對於數組長度很小的情況採用插入排序 if (length < INSERTION_SORT_THRESHOLD) { // INSERTION_SORT_THRESHOLD) = 47 // 插入排序 insertion sort ...省略算法源碼 } // 雙軸快排 dual-pivot quicksort ...省略算法源碼（遞歸插入排序） }具體的算法實現源碼不做深究，以後有機會的話寫一些關於算法拾遺。這裡主要是一些閥值要注意。
3，Arrays.sort(Object[] a)的源碼實現分析：
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) // 如果用戶強制要求使用傳統的排序方法。 // -Djava.util.Arrays.useLegacyMergeSort=true // 或者System.setProperty("java.util.Arrays.useLegacyMergeSort", "true"); legacyMergeSort(a); // 使用傳統方法排序 else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); // 使用TimSort算法排序 }傳統的排序算法legacyMergeSort()源碼：
private static void legacyMergeSort(Object[] a, int fromIndex, int toIndex) { Object[] aux = copyOfRange(a, fromIndex, toIndex); mergeSort(aux, a, fromIndex, toIndex, -fromIndex); } private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; // 如果數組長度很小，採用插入排序 Insertion sort if (length < INSERTIONSORT_THRESHOLD) { // INSERTIONSORT_THRESHOLD = 7 for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // 將數組分為兩個子數組，分別使用遞歸排序Recursively sort，再進行合併排序 ...省略算法源碼 }JDK1.8開始支持TimSort算法，源於Python中的TimSort（結合了merge sort 和 insertion sort）。
ComparableTimSort.sort()源碼：
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { assert a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // 數組長度為0或1時無需排序 // 如果數組長度小，採用無合併形式的"mini-TimSort"排序 if (nRemaining < MIN_MERGE) { // MIN_MERGE = 32 int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); // 二分插入排序 return; } // 1，遍歷一遍數組，找到已經自然排序好順序的序列；3，這個序列入棧（臨時數組，排序後的數組就放在這裡）； // 2，如果這個序列的長度 < minRun 則通過binarySort得到長度為minRun的序列。這個minRun的計算跟數組本身長度有關； // 4，同樣的方法尋找下一個分段併入另外一個棧； // 5，合併排序兩個棧中的序列； // 6，重複4和5； ...省略算法源碼 }4，Arrays.parallelSort()的源碼實現分析:
public static void parallelSort(byte[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1) else new ArraysParallelSortHelpers.FJByte.Sorter (null, a, new byte[n], 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); }Arrays.parallelSort()採用的是cilk排序算法。
cilk排序算法基本思想：
- 將數組分為兩部分；
- 針對每一部分：a，再分為2部分（相當於1/4）；b，針對每1/4部分進行排序；c，排序併合並這兩個1/4；
- 將分別排序好的這兩部分進行排序合併。
如果當前數組的長度a.length < MIN_ARRAY_SORT_GRAN = 8192，或者當前機器不支持並行排序，則採取普通的sort()。
ForkJoinPool.getCommonPoolParallelism()獲取當前ForkJoin線程池的並行度，跟機器的處理器核數有關，可以通過-Djava.util.concurrent.ForkJoinPool.common.parallelism=8或者System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism","8")來指定，如果=1則表示不支持並行執行。
parallelSort()的基本實現思想：
- 將需要被排序的數組分為parallelism個子數組交由ForkJoin框架的每個並行線程執行；
- 每個並行線程將分配到的子數組又分為4個子數組按照cilk算法進行排序，沒個1/4子數組都會按照DualPivotQuicksort.sort()排序；
- 最後將parallelism個子數組進行排序合併。
==================================華麗的分割線==================================
Collections的常用方法：
排序：
Collections.sort(List
public static <T> void sort(List<T> list, Comparator<? super T> c) { list.sort(c); }List.sort()的源碼：
default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); // 調用Arrays.sort()來進行排序 ListIterator<E> i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } }Collections.sort()最終調用的是Arrays.sort()進行排序。
查到索引
Collections.binarySearch(List<? extends Comparable<? super T>> list, T key) Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
順序反轉
Collections.reverse(List<?> list)
亂序
Collections.shuffle(List<?> list)
指定元素互換
Collections.swap(List<?> list, int i, int j)
填充
Collections.fill(List<? super T> list, T obj)
複製
Collections.copy(List<? super T> dest, List<? extends T> src)
求極值
Collections.min(Collection<? extends T> coll)
Collections.min(Collection<? extends T> coll, Comparator<? super T> comp)
Collections.max(Collection<? extends T> coll)
Collections.max(Collection<? extends T> coll, Comparator<? super T> comp)
轉動元素
Collections.rotate(List<?> list, int distance)
distance可以接受負數 將list元素整體向後移動distance的距離，原來最後的distance個元素放到最前面（有點類似與一個圓圈轉動）
替換元素
Collections.replaceAll(List
子集合索引
Collections.indexOfSubList(List<?> source, List<?> target)
Collections.lastIndexOfSubList(List<?> source, List<?> target)
如果不是子集合，返回-1
轉換為不可變集合
Collections.unmodifiableCollection(Collection<? extends T> c)
將集合轉換為不可變集合read-only。裝飾者模式，使用final修飾iterator，增刪元素的方法throw new UnsupportedOperationException()
Collections.unmodifiableSet(Set<? extends T> s)
Collections.unmodifiableList(List<? extends T> list)
Collections.unmodifiableMap(Map<? extends K, ? extends V> m)
轉換為同步集合
Collections.synchronizedCollection(Collection
Collections.synchronizedCollection(Collection
Collections.synchronizedSet(Set
Collections.Collections.synchronizedSet(Set
Collections.synchronizedList(List
Collections.synchronizedList(List
Collections.synchronizedMap(Map<K, V>)
元素受限制集合
Collections.checkedCollection(Collection
由於JDK1.5引入了泛型，採用該方法，保證運行期集合中增加的元素只能是指定的類型。同樣是裝飾着模式。
Collections.checkedQueue(Queue
Collections.checkedSet(Set
Collections.checkedList(List
Collections.checkedMap(Map<K, V>, Class
生成空的不可變集合
Collections.emptyIterator()
Collections.emptyListIterator()
Collections.emptyEnumeration()
Collections.emptySet()
Collections.emptyList()
Collections.emptyMap()
只有1個元素的不可變集合
Collections.singleton(T)
Collections.singletonList(T)
Collections.singletonMap(K, V)
擁有n個相同元素的不可變集合
Collections.nCopies(int, T)
反序比較器
Collections.reverseOrder(Comparator
轉換為枚舉類型的API
Collections.enumeration(Collection
將Enumeration
Collections.list(Enumeration
元素在集合中的個數
Collections.frequency(Collection<?>, Object) 返回int
兩個元素是否有交集
Collections.disjoint(Collection<?>, Collection<?>) 返回boolean
增加元素
addAll(Collection<? super T> c, T… elements)
由於List接口擁有listItegertor()方法，與List相關的大部分操作內部會判斷閥值，超過閥值則採用listIterator遍歷，小於閥值則採用for循環索引遍歷。不同的方法閥值不同。
==================================華麗的分割線==================================
Objects類最主要就一個方法 Objects.equals(Object a, Object b)
public static boolean equals(Object a, Object b) { return a == b || (a != null && a.equals(b)); }其餘的一些比如Obejcts.isNull(Object obj)、Objects.nonNull(Ojbect obj)主要是用來在Stream流式API操作的時候使用。
3. Guava工具類
任何對JDK集合框架有經驗的程序員都熟悉和喜歡java.util.Collections包含的工具方法。Guava沿着這些路線提供了更多的工具方法：適用於所有集合的靜態方法。這是Guava最流行和成熟的部分之一。
我們用相對直觀的方式把工具類與特定集合接口的對應關係歸納如下：
| 集合接口 | 屬於JDK還是**Guava** | 對應的Guava工具類 |
|---|---|---|
| Collection | JDK | Collections2：不要和java.util.Collections混淆 |
| List | JDK | Lists |
| Set | JDK | Sets |
| SortedSet | JDK | Sets |
| Map | JDK | Maps |
| SortedMap | JDK | Maps |
| Queue | JDK | Queues |
| Multiset | Guava | Multisets |
| Multimap | Guava | Multimaps |
| BiMap | Guava | Maps |
| Table | Guava | Tables |
在找類似轉化、過濾的方法？請看第四章，函數式風格。
詳細的介紹可以參考這個文章
4. Apache提供的Collection
Apache提供的集合工具類功能也非常強大。另外還提供了集合的求交集、並集和差集等功能。
具體可以參考官網
