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