Collections(八)Collections工具类

[Sayi]

Collections工具类方便集合的操作。

不可修改包装Unmodifiable Wrappers

public static <T> Collection <T> unmodifiableCollection（Collection <？extends T> c）;
public static <T> Set <T> unmodifiableSet（Set <？extends T> s）;
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> SortedSet <T> unmodifiableSortedSet（SortedSet <？extends T> s）;
public static <K，V> SortedMap <K，V> unmodifiableSortedMap（SortedMap <K，？extends V> m）;

当持有返回集合的引用时，程序是无法对集合进行修改尝试修改会抛出UnsupportedOperationException异常。

以unmodifiableCollection方法为例，它的实现原理返回一个新的内部类对象return new UnmodifiableCollection<>(c)，而UnmodifiableCollection遵循了转换构造函数的设计，在改变结构的方法体中(add\remove\removeIf\addAll\removeAll\clear\retainAll等)，抛出异常。

这里要注意的是，如果我们继续维护参c的集合引用，任何修改c的操作都将导致不可修改的集合内部元素的变更，那么这种不可变的集合也是可变的。

同步包装Synch Wrappers

public static <T> Collection <T> synchronizedCollection（Collection <T> c）;
public static <T> Set <T> synchronizedSet（Set <T> s）;
public static <T> List <T> synchronizedList（List <T> list）;
public static <K，V> Map <K，V> synchronizedMap（Map <K，V> m）;
public static <T> SortedSet <T> synchronizedSortedSet（SortedSet <T> s）;
public static <K，V> SortedMap <K，V> synchronizedSortedMap（SortedMap <K，V> m）;

通过前面的文章已经知道，并发包提供了一些并发性能优异的集合，如果不考虑性能，想快速的获得一个同步集合的话，可以使用这些方法。

实现原很简单，返回一个内部类对象SynchronizedCollection，在该类的所有方法中，通过关键词synchronized实现同步操作。

static class SynchronizedCollection<E> implements Collection<E>, Serializable {

    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize

    SynchronizedCollection(Collection<E> c) {
        this.c = Objects.requireNonNull(c);
        mutex = this;
    }

    public int size() {
        synchronized (mutex) {return c.size();}
    }
    public boolean isEmpty() {
        synchronized (mutex) {return c.isEmpty();}
    }
    public boolean contains(Object o) {
        synchronized (mutex) {return c.contains(o);}
    }

    public Iterator<E> iterator() {
        return c.iterator(); // Must be manually synched by user!
    }
    // 略
}

注意到iterator方法并没有加synchronized关键词，注释也表明了当我们迭代集合时，必须自己手动同步，因为迭代不是一个原子操作，需要一步一步来完成。

Collection<Type> c = Collections.synchronizedCollection（myCollection）;
synchronized（c）{
    for（Type e：c）
        FOO（E）;
}

动态类型安全包装Dynamically typesafe collection wrappers

提供了Collections.checkedXXX方法来确保是类型安全的集合，虽然泛型可以在编译期静态类型检查就确保类型安全，但是这些方法消除了没有用好泛型的顾虑。

空集合Empty collections

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

当这个集合不需要提供任何元素时，可以使用这些方法。注意，它返回的同样是个内部类的对象，元素个数只能为0，不能修改这个集合。

单个元素集合Singleton collections

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);

当你需要 一个元素的不可变集合时，可以使用这些方法，尤其这些方法可以用在removeAll的参数集合上：集合中删除所有某个元素。

算法Algorithms

集合是一系列数据的集，通常会这这些数据集进行相关操作，我们称之为集合算法，其中算法操作绝大多数是操作在List上的，少部分操作在Collection上

sort：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);

排序的实现是基于java.util.Arrays.sort(T[], Comparator<? super T>)方法实现的，Arrays提供了一系列操作数组的方法，包括sort方法，对于任何可比较的原生类型，采用 双轴快速排序算法：

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

对于任何对象类型的数组，采用 合并排序算法，时间复杂度为O(n*logn)：

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

具体算法实现参见DualPivotQuicksort和TimSort类。

binarySearch：list集合中二分查找某个元素key

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);

注意: list必须是一个已经升序排序的列表。* 二分查找算法的核心代码如下：

<T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);
        int cmp = midVal.compareTo(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
}

注意到(low + high) >>> 1这行代码，装逼程序员的深藏功与名。

shuffle：list洗牌

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

重新随机打算list的顺序，核心算法是当前位置与后面的位置随机交换值。

for (int i=size; i>1; i--)
    swap(list, i-1, rnd.nextInt(i));

frequency：元素在collection中的出现频率

public static int frequency(Collection<?> c, Object o) {
    int result = 0;
    if (o == null) {
        for (Object e : c)
            if (e == null)
                result++;
    } else {
        for (Object e : c)
            if (o.equals(e))
                result++;
    }
    return result;
}

disjoint：两个集不相交返回true

针对Collection的操作。

常规操作

• reverse- 颠倒a中元素的顺序List。
• fill- List用指定的值覆盖a中的每个元素。
• copy- 接受两个参数，一个目标List和一个源List，并将源的元素复制到目标中，覆盖其内容。
• swap- 将元素交换到a中的指定位置List。
• min- 最小值
• max- 最大值

总结

在我们为Collection提供操作的时候，同时可以考虑将Collection转化为数组，然后通过Arrays的静态方法来操作。

Google的Guava为集合提供了一系列扩展，除增加新的集合类型外，还提供了一个有用的工具类，如Lists、Maps等，将在下篇文章中详述。