Collections以靜態(tài)方法的方式提供了很多通用算法和功能，這些功能大概可以分為以下兩類。

一類是對容器接口對象進行操作，包括查找、排序、添加和修改。

另一類返回一個容器接口對象，適配器：將其他類型的數(shù)據(jù)轉(zhuǎn)換為容器接口對象+裝飾器：修飾一個給定容器接口對象，增加某種性質(zhì)。

操作容器

查找

Arrays類有針對數(shù)組對象的二分查找方法，而Collections提供了針對List接口的二分查找，如下所示：

public static <T> int binarySearch(
       List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list,
       T key, Comparator<? super T> c)

從方法參數(shù)角度而言，一個要求List的每個元素實現(xiàn)Comparable接口，另一個不需要，但要求提供Comparator。二分查找假定List中的元素是從小到大排序的。List的二分查找的基本思路與Arrays中的是一樣的，數(shù)組可以根據(jù)索引直接定位任意元素，實現(xiàn)效率很高，但List就不一定了，具體分為兩種情況，如果List可以隨機訪問（如數(shù)組），即實現(xiàn)了RandomAccess接口，或者元素個數(shù)比較少，則實現(xiàn)思路與Arrays一樣，根據(jù)索引直接訪問中間元素進行比較，否則使用選代器的方式移動到中間元素進行比較。從效率角度，如果List支持隨機訪問，效率O(log2(N)),如果通過選代器，那么比較的次數(shù)為O(log2(N)),但遍歷移動的次數(shù)為O(N),N為列表長度。

此外Collections提供了如下查找最大值/最小值的方法，實現(xiàn)思路也很簡單，就是通過迭代器進行比較：

public static <T extends Object & Comparable<? super T>> T max(
       Collection<? extends T> coll) {
       Iterator<? extends T> i = coll.iterator();
       T candidate = i.next();
       while(i.hasNext()) {
           T next = i.next();
           if(next.compareTo(candidate) > 0)
               candidate = next;
       }
       return candidate;
}

還可以查找元素出現(xiàn)次數(shù)，返回元素o在容器c中出現(xiàn)的次數(shù)，o可以為null，實現(xiàn)思路就是通過迭代器進行比較計數(shù)。

public static int frequency(Collection<?> c, Object o)

Collections還提供了查找元素位置的方法，在List中查找target的位置：

public static int indexOfSubList(List<?> source, List<?> target)
public static int lastIndexOfSubList(List<?> source, List<?> target)

indexOfSubList從開頭找，lastIndexOfSubList從結(jié)尾找，沒找到返回-1，找到返回第一個匹配元素的索引位置。這兩個方法的實現(xiàn)都是屬于“暴力破解”型的，將target列表與source從第一個元素開始的列表逐個元素進行比較，如果不匹配，則與source從第二個元素開始的列表比較，再不匹配，與source從第三個元素開始的列表比較，以此類推。

排序

針對List接口對象，Collections除了提供基礎(chǔ)的排序，還提供了若干調(diào)整順序的方法，包括交換元素位置、翻轉(zhuǎn)列表順序、隨機化重排、循環(huán)移位等。

Arrays類有針對數(shù)組對象的排序方法，Collections提供了針對List接口的排序方法，如下所示：

public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list, Comparator<? super T> c)

內(nèi)部是通過Arrays.sort實現(xiàn)的，先將List元素復(fù)制到一個數(shù)組中，然后使用Arrays.sort,排序后，再復(fù)制回List。代碼如下所示：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
       Object[] a = list.toArray();
       Arrays.sort(a);
       ListIterator<T> i = list.listIterator();
       for(int j=0; j<a.length; j++) {
           i.next();
           i.set((T)a[j]);
       }
}

交換元素位置的方法為：

public static void swap(List<?> list, int i, int j)

交換List中第i個和第j個元素的內(nèi)容。實現(xiàn)代碼為：

public static void swap(List<?> list, int i, int j) {
       final List l = list;
       l.set(i, l.set(j, l.get(i)));
}

翻轉(zhuǎn)列表順序的方法為：

public static void reverse(List<?> list)

將List中的元素順序翻轉(zhuǎn)過來。實現(xiàn)思路就是將第一個和最后一個交換，第二個和倒數(shù)第二個交換，以此類推，直到中間兩個元素交換完畢。如果List實現(xiàn)了RandomAccess接口或列表比較小，根據(jù)索引位置，使用上面的swap方法進行交換，否則，由于直接根據(jù)索引位置定位元素效率比較低，使用一前一后兩個listIterator定位待交換的元素，具體代碼為：

public static void reverse(List<?> list) {
       int size = list.size();
       if(size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
           for(int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
               swap(list, i, j);
       } else {
           ListIterator fwd = list.listIterator();
           ListIterator rev = list.listIterator(size);
           for(int i=0, mid=list.size()>>1; i<mid; i++) {
               Object tmp = fwd.next();
               fwd.set(rev.previous());
               rev.set(tmp);
           }
       }
}

Collections還直接提供了對List元素洗牌的方法：

public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd)

實現(xiàn)思路為：從后往前遍歷列表，逐個給每個位置重新賦值，值從前面的未重新賦值的元素中隨機挑選。如果列表實現(xiàn)了RandomAccess接口，或者列表比較小，直接使用前面swap方法進行交換，否則，先將列表內(nèi)容復(fù)制到一個數(shù)組中，洗牌，再復(fù)制回列表。代碼為：

public static <T> void shuffle(List<T> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i = size; i > 1; i--) {
                int swapIndex = rnd.nextInt(i);
                Collections.swap(list, i - 1, swapIndex);
            }
        } else {
            Object[] arr = list.toArray();
            for (int i = size; i > 1; i--) {
                int swapIndex = rnd.nextInt(i);
                Object temp = arr[i - 1];
                arr[i - 1] = arr[swapIndex];
                arr[swapIndex] = temp;
            }
            ListIterator<T> it = list.listIterator();
            for (int i = 0; i < arr.length; i++) {
                it.next();
                it.set((T) arr[i]);
            }
        }
    }

添加和修改

Collections也提供了幾個批量添加和修改的方法

批量添加，方法為：

public static <T> boolean addAll(Collection<? super T> c, T... elements)

批量填充固定值，方法為：

public static <T> void fill(List<? super T> list, T obj)

這個方法與Arrays類中的fill方法是類似的，給每個元素設(shè)置相同的值。

批量復(fù)制，方法為：

public static <T> void copy(List<? super T> dest, List<? extends T> src)

將列表src中的每個元素復(fù)制到列表dest的對應(yīng)位置處，覆蓋dest中原來的值，dest的列表長度不能小于src,dest中超過src長度部分的元素不受影響。

返回容器

適配器

適配器，就是將一種類型的接口轉(zhuǎn)換成另一種接口，類似于電子設(shè)備中的各種USB轉(zhuǎn)接頭，一端
連接某種特殊類型的接口，一段連接標(biāo)準(zhǔn)的USB接口。Collections類提供了幾組類似于適配器的方法：
·空容器方法：類似于將null或“空”轉(zhuǎn)換為一個標(biāo)準(zhǔn)的容器接口對象。
·單一對象方法：將一個單獨的對象轉(zhuǎn)換為一個標(biāo)準(zhǔn)的容器接口對象。
·其他適配方法：將Map轉(zhuǎn)換為Set等。

空容器方法返回一個不包含任何元素的容器接口對象，分別返回一個空的List、Set、Map和Iterator對象。實際使用中，空容器對象經(jīng)常用作方法返回值。

public static final <T> List<T> emptyList()
public static final <T> Set<T> emptySet()
public static final <K,V> Map<K,V> emptyMap()
public static <T> Iterator<T> emptyIterator()

Collections中還有一組方法，可以將一個單獨的對象轉(zhuǎn)換為一個標(biāo)準(zhǔn)的容器接口對象，比如：

public static <T> Set<T> singleton(T o)
public static <T> List<T> singletonList(T o)
public static <K,V> Map<K,V> singletonMap(K key, V value)

這些方法也經(jīng)常用于構(gòu)建方法返回值，相比新建容器對象并添加元素，這些方法更為簡潔方便，此外，它們的實現(xiàn)更為高效，它們的實現(xiàn)類都針對單一對象進行了優(yōu)化。

裝飾器

裝飾器接受一個接口對象，并返回一個同樣接口的對象，不過，新對象可能會擴展一些新的方法或?qū)傩?，擴展的方法或?qū)傩跃褪撬^的“裝飾”，也可能會對原有的接口方法做一些修改，達到一定的“裝飾"目的。Collections有三組裝飾器方法，它們的返回對象都沒有新的方法或?qū)傩?，但改變了原有接口方法的性質(zhì)，經(jīng)過“裝飾”后，它們更為安全了，具體分別是寫安全、類型安全和線程安全。

public static <T> Collection<T> unmodifiableCollection(
Collection<? extends T> c)
public static <T> List<T> unmodifiableList(List<? extends T> list)
public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m)
public static <T> Set<T> unmodifiableSet(Set<? extends T> s)

這組unmodifiableXXX方法是使容器對象變?yōu)橹蛔x的，寫入會報UnsupportedOperationException異常。典型場景是：需要傳遞一個容器對象給一個方法，這個方法可能是第三方提供的，為避免第三方誤寫，所以在傳遞前，變?yōu)橹蛔x的。

這些方法是如何實現(xiàn)的呢？每個方法內(nèi)部都對應(yīng)一個類，這個類實現(xiàn)了對應(yīng)的容器接口，它內(nèi)部是待裝飾的對象，只讀方法傳遞給這個內(nèi)部對象，寫方法拋出異常。比如unmodifiableCollection方法的代碼為：

public static <T> Collection<T> unmodifiableCollection(
       Collection<? extends T> c) {
       return new UnmodifiableCollection<>(c);
}

所謂類型安全是指確保容器中不會保存錯誤類型的對象。

如果我們創(chuàng)建了一個Integer類型的List對象，但添加了字符串類型的對象"hello",編譯沒有錯誤，運行也沒有異常，程序輸出為"[hello]"。
之所以會出現(xiàn)這種情況，是因為Java是通過擦除來實現(xiàn)泛型的，而且類型參數(shù)是可選的。正常情況下，我們會加上類型參數(shù)，讓泛型機制來保證類型的正確性。但是，由于泛型是Java5以后才加入的，之前的代碼可能沒有類型參數(shù)，而新的代碼可能需要與老的代碼互動。為了避免老的代碼用錯類型，確保在泛型機制失靈的情況下類型的正確性，可以在傳遞容器對象給老代碼之前，使用類似如下方法“裝飾”容器對象：

public static <E> List<E> checkedList(List<E> list, Class<E> type)
public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
Class<K> keyType, Class<V> valueType)
public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)

使用這組checkedXXX方法，都需要傳遞類型對象，這些方法都會使容器對象的方法在運行時檢查類型的正確性，如果不匹配，會拋出ClassCastException異常。

當(dāng)多個線程同時讀寫同一個容器對象，是不安全的。Collections提供了一組方法，可以將一個容器對象變?yōu)榫€程安全的，比如：

public static <T> Collection<T> synchronizedCollection(Collection<T> c)
public static <T> List<T> synchronizedList(List<T> list)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

這些方法都是通過給所有容器方法加鎖來實現(xiàn)的，這種實現(xiàn)并不是最優(yōu)的。對此，Java提供了很多專門針對并發(fā)訪問的容器類。文章來源地址http://www.zghlxwxcb.cn/news/detail-825687.html

到了這里，關(guān)于Java Collections源碼剖析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！