Collection & Collections Part 2/2: Collections

概述

java.util.collections 這個類的成員方法全是靜态的，都是對 Collection 的操作。并且這個類還提供了 “Wrapper” 的功能，就是把一種 Collection 轉換成另一種 Collection。

這個類也提供了很多常用的算法，比如折半查找 (binarySearch) 和排序算法。同時它也提供了很多的對常用資料結構的操作方法，比如交換，反轉，旋轉等操作，是以 Collections 這個工具類需要好好研究一下的，對于資料結構和算法的了解都有很大的好處。

如果傳遞給這個類的方法的 collection 是 null 的，那麼所有方法都會抛出 NullPointerException。

Collections 類是 Java Collection 架構的成員。

構造方法

/**
 * 構造方法設為 private，不允許建立類的執行個體。
 */
private Collections() {}

成員變量

/**
 * 這些都是 優化參數。
 * 基本上很多 List 的算法都有兩種實作：
 * 一種對應 随機通路清單(可以了解為數組)；
 * 另一種對應 順序通路清單(可以了解為連結清單)。
 * 下面的這些成員變量就是決定元素數目達到一定數目時采用什麼算法。 *
 */
private static final int BINARYSEARCH_THRESHOLD   = ;
private static final int REVERSE_THRESHOLD        =   ;
private static final int SHUFFLE_THRESHOLD        =    ;
private static final int FILL_THRESHOLD           =   ;
private static final int ROTATE_THRESHOLD         =  ;
private static final int COPY_THRESHOLD           =   ;
private static final int REPLACEALL_THRESHOLD     =   ;
private static final int INDEXOFSUBLIST_THRESHOLD =   ;

部分成員方法

/**
 * 這裡用的是清單的 sort 方法，進去後會發現是個 歸并排序。
 */
public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

/**
 * 二叉搜尋，折半查找
 */
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

/**
 * 反轉 list 資料元素
 */
public static void reverse(List<?> list) {
    int size = list.size();
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        // 元素數目沒有超過門檻值，或者 list 是 RandomAccess 的執行個體，兩頭元素交換
        for (int i=, mid=size>>, j=size-; i<mid; i++, j--)
            swap(list, i, j);
    } else {
        // 否則，就是連結清單的操作了，同樣從兩頭交換，原理是一樣的。
        ListIterator fwd = list.listIterator();
        ListIterator rev = list.listIterator(size);
        for (int i=, mid=list.size()>>; i<mid; i++) {
            Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }
}

/**
 * 連結清單元素的交換
 * set() 方法會傳回 舊值
 */
public static void swap(List<?> list, int i, int j) {
    final List l = list;
    l.set(i, l.set(j, l.get(i)));
}

/**
 * 數組元素的交換
 */
private static void swap(Object[] arr, int i, int j) {
    Object tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

/**
 * 擷取 Collection 的最小值，還是很好了解的，O(N)
 * max() 方法同理
 */
public static <T extends Object & Comparable<? super T>> T min(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) < )
            candidate = next;
    }
    return candidate;
}

/**
 * 替換 list 中所有值為 oldVal 的元素為 newVal
 */
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
    boolean result = false;
    int size = list.size();
    if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
        if (oldVal==null) { // 如果 oldVal 是 null
            for (int i=; i<size; i++) {
                if (list.get(i)==null) {
                    list.set(i, newVal);
                    result = true;
                }
            }
        } else {
            for (int i=; i<size; i++) { // oldVal 不是 null
                if (oldVal.equals(list.get(i))) { // 可調用 equals 方法了
                    list.set(i, newVal);
                    result = true;
                }
            }
        }
    } else { // 與 if 分支原理相同
        ListIterator<T> itr=list.listIterator();
        if (oldVal==null) {
            for (int i=; i<size; i++) {
                if (itr.next()==null) {
                    itr.set(newVal);
                    result = true;
                }
            }
        } else {
            for (int i=; i<size; i++) {
                if (oldVal.equals(itr.next())) {
                    itr.set(newVal);
                    result = true;
                }
            }
        }
    }
    return result;
}

/**
 * 這個方法把 Collection 包裝為一個 不可修改 的 Collection
 * UnmodifiableCollection 是一個内部類。
 * 隻要修改包裝後的 c，就會抛出 UnsupportedOperationException。
 */
public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
    return new UnmodifiableCollection<>(c);
}

/** 
 * 下面這個方法傳回的是 SynchronizedCollection，把涉及到修改 Collection 的方法
 * 都加上了 Synchronized 關鍵字。還有另外一個重載的方法，可以指定 mutex (鎖對象)。
 */
public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}

/** 
 * 這個方法傳回的是 CheckedCollection，如果往其中插入的元素類型不是 type的
 * 會立刻抛出 ClassCastException。
 */
public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type) {
    return new CheckedCollection<>(c, type);
}

// 傳回一個空的 iterator， EMPTY_ITERATOR = new EmptyIterator<>()
public static <T> Iterator<T> emptyIterator() {
    return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
}

// 傳回一個 Set，隻有一個元素，且無法修改
public static <T> Set<T> singleton(T o) {
    return new SingletonSet<>(o);
}

// 傳回一個 不可修改的 list，内含 n 個 o 的拷貝。
public static <T> List<T> nCopies(int n, T o) {
    if (n < )
        throw new IllegalArgumentException("List length = " + n);
    return new CopiesList<>(n, o);
}

// 可見 枚舉 Enumeration 本質上是 疊代器 Iterator 實作的。
public static <T> Enumeration<T> enumeration(final Collection<T> c) {
    return new Enumeration<T>() {
        private final Iterator<T> i = c.iterator();

        public boolean hasMoreElements() {
            return i.hasNext();
        }

        public T nextElement() {
            return i.next();
        }
    };
}

Summary

基本上了解了 Array, List, Set, Map 這些基本的資料結構之後，Collections 中的方法是很好的了解的。這也是為什麼一名優秀的程式設計設計人員的資料結構一定掌握的很好很紮實。

這些基本資料結構的特點，這篇博文已經做了詳細的說明。

共勉。

轉載于:https://www.cnblogs.com/1202zhyl/p/5726843.html

Collection & Collections Part 2/2: Collections