12.2 Collections

发表于 更新于 分类于 ， ， Waline： 本文字数： 21k 阅读时长 ≈ 19 分钟

12.2 Collections

类Collections以静态方法的方式提供了很多通用算法和功能，这些功能大概可以分为两类。
1）对容器接口对象进行操作。
2）返回一个容器接口对象。

对于第1类，操作大概可以分为三组。

  • 查找和替换。
  • 排序和调整顺序。
  • 添加和修改。

对于第2类，大概可以分为两组。

  • 适配器：将其他类型的数据转换为容器接口对象。
  • 装饰器：修饰一个给定容器接口对象，增加某种性质。

它们都是围绕容器接口对象的，第1类是针对容器接口的通用操作，这是面向接口编程的一种体现，是接口的典型用法；第2类是为了使更多类型的数据更为方便和安全地参与到容器类协作体系中。下面我们分别介绍这两类操作及其实现原理，代码分析基于Java 7。

12.2.1 查找和替换

查找和替换包含多组方法。查找包括二分查找、查找最大值/最小值、查找元素出现次数、查找子List、查看两个集合是否有交集等，下面具体介绍。

1．二分查找

我们在介绍Arrays类的时候介绍过二分查找，Arrays类有针对数组对象的二分查找方法，Collections提供了针对List接口的二分查找，如下所示：

1
2
3
4
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的每个元素实现Comparable接口，另一个不需要，但要求提供Comparator。二分查找假定List中的元素是从小到大排序的。如果是从大到小排序的，需要传递一个逆序Comparator对象，Collections提供了返回逆序Comparator的方法，之前我们也用过：

1
2
public static <T> Comparator<T> reverseOrder()
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)

比如，可以这么用：

1
2
3
4
5
List<Integer> list = new ArrayList<>(Arrays.asList(new Integer[]{
        35, 24, 13, 12, 8, 7, 1
}));
System.out.println(Collections.binarySearch(list, 7,
    Collections.reverseOrder()));

输出为：5。List的二分查找的基本思路与Arrays中的是一样的，数组可以根据索引直接定位任意元素，实现效率很高，但List就不一定了，具体分为两种情况，如果List可以随机访问（如数组），即实现了RandomAccess接口，或者元素个数比较少，则实现思路与Arrays一样，根据索引直接访问中间元素进行比较，否则使用迭代器的方式移动到中间元素进行比较。从效率角度，如果List支持随机访问，效率为O(log2(N))，如果通过迭代器，那么比较的次数为O(log2(N))，但遍历移动的次数为O(N), N为列表长度。

2．查找最大值/最小值

Collections提供了如下查找最大值/最小值的方法（省略了修饰符publicstatic）：

1
2
3
4
<T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
<T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
<T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
<T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

含义和用法都很直接，实现思路也很简单，就是通过迭代器进行比较，比如：

1
2
3
4
5
6
7
8
9
10
11
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;
}

3．其他方法

查找元素出现次数，方法为：

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

返回元素o在容器c中出现的次数，o可以为null。含义很简单，实现思路也很简单，就是通过迭代器进行比较计数。

Collections提供了如下方法，在source List中查找target List的位置：

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

indexOfSubList从开头找，lastIndexOfSubList从结尾找，没找到返回-1，找到返回第一个匹配元素的索引位置。这两个方法的实现都是属于“暴力破解”型的，将target列表与source从第一个元素开始的列表逐个元素进行比较，如果不匹配，则与source从第二个元素开始的列表比较，再不匹配，与source从第三个元素开始的列表比较，以此类推。

查看两个集合是否有交集，方法为：

1
public static boolean disjoint(Collection<? > c1, Collection<? > c2)

如果c1和c2有交集，返回值为false；没有交集，返回值为true。实现原理也很简单，遍历其中一个容器，对每个元素，在另一个容器里通过contains方法检查是否包含该元素，如果包含，返回false，如果最后不包含任何元素返回true。这个方法的代码会根据容器是否为Set以及集合大小进行性能优化，即选择哪个容器进行遍历，哪个容器进行检查，以减少总的比较次数，具体我们就不介绍了。

替换方法为：

1
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)

将List中的所有oldVal替换为newVal，如果发生了替换，返回值为true，否则为false。用法和实现都比较简单，就不赘述了。

12.2.2 排序和调整顺序

针对List接口对象，Collections除了提供基础的排序，还提供了若干调整顺序的方法，包括交换元素位置、翻转列表顺序、随机化重排、循环移位等，下面具体介绍。

1．排序、交换位置与翻转

Arrays类有针对数组对象的排序方法，Collections提供了针对List接口的排序方法，如下所示：

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

使用很简单，就不举例了，内部它是通过Arrays.sort实现的，先将List元素复制到一个数组中，然后使用Arrays.sort，排序后，再复制回List。代码如下所示：

1
2
3
4
5
6
7
8
9
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]);
    }
}

交换元素位置的方法为：

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

交换list中第i个和第j个元素的内容。实现代码为：

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

翻转列表顺序的方法为：

1
public static void reverse(List<? > list)

将list中的元素顺序翻转过来。实现思路就是将第一个和最后一个交换，第二个和倒数第二个交换，以此类推，直到中间两个元素交换完毕。如果list实现了RandomAccess接口或列表比较小，根据索引位置，使用上面的swap方法进行交换，否则，由于直接根据索引位置定位元素效率比较低，使用一前一后两个listIterator定位待交换的元素，具体代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
        }
    }
}

2．随机化重排

我们在随机一节介绍过洗牌算法，Collections直接提供了对List元素洗牌的方法：

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

实现思路与随机一节介绍的是一样的：从后往前遍历列表，逐个给每个位置重新赋值，值从前面的未重新赋值的元素中随机挑选。如果列表实现了RandomAccess接口，或者列表比较小，直接使用前面swap方法进行交换，否则，先将列表内容复制到一个数组中，洗牌，再复制回列表。代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void shuffle(List<? > list, Random rnd) {
    int size = list.size();
    if(size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for(int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();
        //对数组进行洗牌
        for(int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));
        //将数组中洗牌后的结果保存回list
        ListIterator it = list.listIterator();
        for(int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

3．循环移位

我们解释下循环移位的概念，比如列表为：

1
[8, 5, 3, 6, 2]

循环右移2位，会变为：

1
[6, 2, 8, 5, 3]

如果是循环左移2位，会变为：

1
[3, 6, 2, 8, 5]

因为列表长度为5，循环左移3位和循环右移2位的效果是一样的。

循环移位的方法是：

1
public static void rotate(List<? > list, int distance)

distance表示循环移位个数，一般正数表示向右移，负数表示向左移，比如：

1
2
3
4
5
6
7
8
9
10
List<Integer> list1 = Arrays.asList(new Integer[]{
        8, 5, 3, 6, 2
});
Collections.rotate(list1, 2);
System.out.println(list1);
List<Integer> list2 = Arrays.asList(new Integer[]{
        8, 5, 3, 6, 2
});
Collections.rotate(list2, -2);
System.out.println(list2);

输出为：

1
2
[6, 2, 8, 5, 3]
[3, 6, 2, 8, 5]

这个方法很有用的一点是：它也可以用于子列表，可以调整子列表内的顺序而不改变其他元素的位置。比如，将第j个元素向前移动到k（k>j），可以这么写：

1
Collections.rotate(list.subList(j, k+1), -1);

再举个例子：

1
2
3
4
5
List<Integer> list = Arrays.asList(new Integer[]{
        8, 5, 3, 6, 2, 19, 21
});
Collections.rotate(list.subList(1, 5), 2);
System.out.println(list);

输出为：

1
[8, 6, 2, 5, 3, 19, 21]

这个类似于列表内的“剪切”和“粘贴”，将子列表[5, 3]“剪切”, “粘贴”到2后面。如果需要实现类似“剪切”和“粘贴”的功能，可以使用rotate()方法。

循环移位的内部实现比较巧妙，根据列表大小和是否实现了RandomAccess接口，有两个算法，都比较巧妙，两个算法在《编程珠玑》这本书的2.3节有描述。

限于篇幅，我们只解释下其中的第二个算法，它将循环移位看作列表的两个子列表进行顺序交换。再来看上面的例子，循环左移2位：

1
[8, 5, 3, 6, 2] -> [3, 6, 2, 8, 5]

就是将[8, 5]和[3, 6, 2]两个子列表的顺序进行交换。循环右移两位：

1
[8, 5, 3, 6, 2] -> [6, 2, 8, 5, 3]

就是将[8, 5, 3]和[6, 2]两个子列表的顺序进行交换。

根据列表长度size和移位个数distance，可以计算出两个子列表的分隔点，有了两个子列表后，两个子列表的顺序交换可以通过三次翻转实现。比如，有A和B两个子列表，A有m个元素，B有n个元素：a1a2…amb1b2…bn，要变为b1b2…bna1a2…am，可经过三次翻转实现：

（1）翻转子列表A
$$
a_1a_2 … a_mb_1b_2 … b_n → a_m … a_2 a_1b_1b_2 … b_n
$$
（2）翻转子列表B
$$
a_m … a_2 a_1 b_1 b_2 … b_n → a_m … a_2 a_1 b_n … b_2 b_1
$$
（3）翻转整个列表
$$
a_m … a_2 a_1 b_n … b_2 b_1 → b_1 b_2 … b_n a_1 a_2 … a_m
$$

这个算法的整体实现代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
private static void rotate2(List<? > list, int distance) {
    int size = list.size();
    if(size == 0)
        return;
    int mid =   -distance % size;
    if(mid < 0)
        mid += size;
    if(mid == 0)
        return;
    reverse(list.subList(0, mid));
    reverse(list.subList(mid, size));
    reverse(list);
}

mid为两个子列表的分割点，调用了三次reverse方法以实现子列表顺序交换。

12.2.3 添加和修改

Collections也提供了几个批量添加和修改的方法，逻辑都比较简单，我们看下。批量添加，方法为：

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

elements为可变参数，将所有元素添加到容器c中。这个方法很方便，比如：

1
2
3
4
5
List<String> list = new ArrayList<String>();
String[] arr = new String[]{"深入", "浅出"};
Collections.addAll(list, "hello", "world", "老马", "编程");
Collections.addAll(list, arr);
System.out.println(list);

输出为：

1
[hello, world, 老马， 编程， 深入， 浅出]

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

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

这个方法与Arrays类中的fill方法是类似的，给每个元素设置相同的值。

批量复制，方法为：

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

将列表src中的每个元素复制到列表dest的对应位置处，覆盖dest中原来的值，dest的列表长度不能小于src, dest中超过src长度部分的元素不受影响。

12.2.4 适配器

所谓适配器，就是将一种类型的接口转换成另一种接口，类似于电子设备中的各种USB转接头，一端连接某种特殊类型的接口，一段连接标准的USB接口。Collections类提供了几组类似于适配器的方法：

  • 空容器方法：类似于将null或“空”转换为一个标准的容器接口对象。
  • 单一对象方法：将一个单独的对象转换为一个标准的容器接口对象。
  • 其他适配方法：将Map转换为Set等。

它们接受其他类型的数据，转换为一个容器接口，目的是使其他类型的数据更为方便地参与到容器类协作体系中，下面，我们分别来看下。

1．空容器方法

Collections中有一组方法，返回一个不包含任何元素的容器接口对象，如下所示：

1
2
3
4
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()

分别返回一个空的List、Set、Map和Iterator对象。比如，可以这么用：

1
2
3
List<String> list = Collections.emptyList();
Map<String, Integer> map = Collections.emptyMap();
Set<Integer> set = Collections.emptySet();

一个空容器对象有什么用呢？空容器对象经常用作方法返回值。比如，有一个方法，可以将可变长度的整数转换为一个List，方法声明为：

1
public static List<Integer> asList(int... elements)

在参数为空时，这个方法应该返回null还是一个空的List呢？如果返回null，方法调用者必须进行检查，然后分别处理，代码结构大概如下所示：

1
2
3
4
5
6
7
int[] arr = …; //从别的地方获取到的arr
List<Integer> list = asList(arr);
if(list==null){
    //…
}else{
    //…
}

这段代码比较烦琐，而且如果不小心忘记检查，则有可能会抛出空指针异常，所以推荐做法是返回一个空的List，以便调用者安全地进行统一处理，比如，asList可以这样实现：

1
2
3
4
5
6
7
8
9
10
public static List<Integer> asList(int... elements){
    if(elements.length==0){
        return Collections.emptyList();
    }
    List<Integer> list = new ArrayList<>(elements.length);
    for(int e : elements){
        list.add(e);
    }
    return list;
}

返回一个空的List。也可以这样实现：

1
return new ArrayList<Integer>();

这与emptyList方法有什么区别呢？emptyList方法返回的是一个静态不可变对象，它可以节省创建新对象的内存和时间开销。我们来看下emptyList方法的具体定义：

1
2
3
public static final <T> List<T> emptyList() {
    return (List<T>) EMPTY_LIST;
}

EMPTY_LIST的定义为：

1
public static final List EMPTY_LIST = new EmptyList<>();

是一个静态不可变对象，类型为EmptyList，它是一个私有静态内部类，继承自Abstract-List，主要代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private static class EmptyList<E>
    extends AbstractList<E>
    implements RandomAccess {
    public Iterator<E> iterator() {
        return emptyIterator();
    }
    public ListIterator<E> listIterator() {
        return emptyListIterator();
    }
    public int size() {return 0; }
    public boolean isEmpty() {return true; }
    public boolean contains(Object obj) {return false; }
    public boolean containsAll(Collection<? > c) { return c.isEmpty(); }
    public Object[] toArray() { return new Object[0]; }
    public <T> T[] toArray(T[] a) {
        if(a.length > 0)
            a[0] = null;
        return a;
    }
    public E get(int index) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
    public boolean equals(Object o) {
        return (o instanceof List) && ((List<? >)o).isEmpty();
    }
    public int hashCode() { return 1; }
}

emptyIterator和emptyListIterator返回空的迭代器。emptyIterator的代码为：

1
2
3
public static <T> Iterator<T> emptyIterator() {
    return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
}

EmptyIterator是一个静态内部类，代码为：

1
2
3
4
5
6
7
private static class EmptyIterator<E> implements Iterator<E> {
    static final EmptyIterator<Object> EMPTY_ITERATOR
        = new EmptyIterator<>();
    public boolean hasNext() { return false; }
    public E next() { throw new NoSuchElementException(); }
    public void remove() { throw new IllegalStateException(); }
}

以上这些代码都比较简单，就不赘述了。需要注意的是，EmptyList不支持修改操作，比如：

1
Collections.emptyList().add("hello");

会抛出异常UnsupportedOperationException。

如果返回值只是用于读取，可以使用emptyList方法，但如果返回值还用于写入，则需要新建一个对象。其他空容器方法与emptyList方法类似，我们就不赘述了。它们都可以被用于方法返回值，以便调用者统一进行处理，同时节省时间和内存开销，它们的共同限制是返回值不能用于写入。我们将空容器方法看作适配器，是因为它将null或“空”转换为了容器对象。

需要说明的是，在Java 9中，可以使用List、Map和Set不带参数的of方法返回一个空的只读容器对象，也就是说，如下两行代码的效果是相同的：

1
2
1. List list = Collections.emptyList();
2. List list = List.of();

2．单一对象方法

Collections中还有一组方法，可以将一个单独的对象转换为一个标准的容器接口对象，比如：

1
2
3
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)

比如，可以这么用：

1
2
3
4
Collection<String> coll = Collections.singleton("编程");
Set<String> set = Collections.singleton("编程");
List<String> list = Collections.singletonList("老马");
Map<String, String> map = Collections.singletonMap("老马", "编程");

这些方法也经常用于构建方法返回值，相比新建容器对象并添加元素，这些方法更为简洁方便，此外，它们的实现更为高效，它们的实现类都针对单一对象进行了优化。比如， singleton方法的代码：

1
2
3
public static <T> Set<T> singleton(T o) {
    return new SingletonSet<>(o);
}

新建了一个SingletonSet对象，SingletonSet是一个静态内部类，主要代码为：

1
2
3
4
5
6
7
8
9
10
private static class SingletonSet<E>
    extends AbstractSet<E> {
    private final E element;
    SingletonSet(E e) {element = e; }
    public Iterator<E> iterator() {
        return singletonIterator(element);
    }
    public int size() {return 1; }
    public boolean contains(Object o) {return eq(o, element); }
}

singletonIterator是一个内部方法，将单一对象转换为了一个迭代器接口对象，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static <E> Iterator<E> singletonIterator(final E e) {
    return new Iterator<E>() {
        private boolean hasNext = true;
        public boolean hasNext() {
            return hasNext;
        }
        public E next() {
            if(hasNext) {
                hasNext = false;
                return e;
                }
                throw new NoSuchElementException();
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    };
}

eq方法就是比较两个对象是否相同，考虑了null的情况，代码为：

1
2
3
static boolean eq(Object o1, Object o2) {
    return o1==null ? o2==null : o1.equals(o2);
}

需要注意的是，singleton方法返回的也是不可变对象，只能用于读取，写入会抛出UnsupportedOperationException异常。其他singletonXXX方法的实现思路是类似的，返回值也都只能用于读取，不能写入，我们就不赘述了。

除了用于构建返回值，这些方法还可用于构建方法参数。比如，从容器中删除对象， Collection有如下方法：

1
2
boolean remove(Object o);
boolean removeAll(Collection<? > c);

remove方法只会删除第一条匹配的记录，removeAll方法可以删除所有匹配的记录，但需要一个容器接口对象，如果需要从一个List中删除所有匹配的某一对象呢？这时，就可以使用Collections.singleton封装这个要删除的对象。比如，从list中删除所有的”b”，代码如下所示：

1
2
3
4
List<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c", "d", "b");
list.removeAll(Collections.singleton("b"));
System.out.println(list);

需要说明的是，在Java 9中，可以使用List、Map和Set的of方法达到singleton同样的功能，也就是说，如下两行代码的效果是相同的：

1
2
1. Set<String> b = Collections.singleton("b");
2. Set<String> b = Set.of("b");

除了以上两组方法，Collections中还有如下适配器方法，用的相对较少，我们就不详细介绍了。

1
2
3
4
5
6
//将Map接口转换为Set接口
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map)
//将Deque接口转换为后进先出的队列接口
public static <T> Queue<T> asLifoQueue(Deque<T> deque)
//返回包含n个相同对象o的List接口
public static <T> List<T> nCopies(int n, T o)

12.2.5 装饰器

装饰器接受一个接口对象，并返回一个同样接口的对象，不过，新对象可能会扩展一些新的方法或属性，扩展的方法或属性就是所谓的“装饰”，也可能会对原有的接口方法做一些修改，达到一定的“装饰”目的。Collections有三组装饰器方法，它们的返回对象都没有新的方法或属性，但改变了原有接口方法的性质，经过“装饰”后，它们更为安全了，具体分别是写安全、类型安全和线程安全，我们分别来看下。

1．写安全

写安全的主要方法有：

1
2
3
4
5
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方法就是使容器对象变为只读的，写入会抛出UnsupportedOperationException异常。为什么要变为只读的呢？典型场景是：需要传递一个容器对象给一个方法，这个方法可能是第三方提供的，为避免第三方误写，所以在传递前，变为只读的，如下所示：

1
2
3
4
5
6
7
8
public static void thirdMethod(Collection<String> c){
    c.add("bad");
}
public static void mainMethod(){
    List<String> list = new ArrayList<>(Arrays.asList(
            new String[]{"a", "b", "c", "d"}));
    thirdMethod(Collections.unmodifiableCollection(list));
}

这样，调用就会触发异常，从而避免了将错误数据插入。

这些方法是如何实现的呢？每个方法内部都对应一个类，这个类实现了对应的容器接口，它内部是待装饰的对象，只读方法传递给这个内部对象，写方法抛出异常。比如， unmodifiableCollection方法的代码为：

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

UnmodifiableCollection是一个静态内部类，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
static class UnmodifiableCollection<E> implements Collection<E>,
    Serializable {
    private static final long serialVersionUID = 1820017752578914078L;
    final Collection<? extends E> c;
      UnmodifiableCollection(Collection<? extends E> c) {
        if(c==null)
            throw new NullPointerException();
        this.c = c;
    }
    public int size() {return c.size(); }
    public boolean isEmpty() {return c.isEmpty(); }
    public boolean contains(Object o) {return c.contains(o); }
    public Object[] toArray() {return c.toArray(); }
    public <T> T[] toArray(T[] a) {return c.toArray(a); }
    public String toString() {return c.toString(); }
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private final Iterator<? extends E> i = c.iterator();
            public boolean hasNext() {return i.hasNext(); }
            public E next() {return i.next(); }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }
    public boolean containsAll(Collection<? > coll) {
        return c.containsAll(coll);
    }
    public boolean addAll(Collection<? extends E> coll) {
        throw new UnsupportedOperationException();
    }
    public boolean removeAll(Collection<? > coll) {
        throw new UnsupportedOperationException();
    }
    public boolean retainAll(Collection<? > coll) {
        throw new UnsupportedOperationException();
    }
    public void clear() {
        throw new UnsupportedOperationException();
    }
}

代码比较简单，其他unmodifiableXXX方法的实现也都类似，我们就不赘述了。

2．类型安全

所谓类型安全是指确保容器中不会保存错误类型的对象。容器怎么会允许保存错误类型的对象呢？我们看段代码：

1
2
3
List list = new ArrayList<Integer>();
list.add("hello");
System.out.println(list);

我们创建了一个Integer类型的List对象，但添加了字符串类型的对象”hello”，编译没有错误，运行也没有异常，程序输出为”[hello]”。

之所以会出现这种情况，是因为Java是通过擦除来实现泛型的，而且类型参数是可选的。正常情况下，我们会加上类型参数，让泛型机制来保证类型的正确性。但是，由于泛型是Java 5以后才加入的，之前的代码可能没有类型参数，而新的代码可能需要与老的代码互动。

为了避免老的代码用错类型，确保在泛型机制失灵的情况下类型的正确性，可以在传递容器对象给老代码之前，使用类似如下方法“装饰”容器对象：

1
2
3
4
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异常。比如：

1
2
3
List list = new ArrayList<Integer>();
list = Collections.checkedList(list, Integer.class);
list.add("hello");

这次，运行就会抛出异常，从而避免错误类型的数据插入：

1
2
java.lang.ClassCastException:  Attempt  to  insert  class  java.lang.String  element
    into collection with element type class java.lang.Integer

这些checkedXXX方法的实现机制是类似的，每个方法内部都对应一个类，这个类实现了对应的容器接口，它内部是待装饰的对象，大部分方法只是传递给这个内部对象，但对添加和修改方法，会首先进行类型检查，类型不匹配会抛出异常，类型匹配才传递给内部对象。以checkedCollection为例，我们来看下代码：

1
2
3
4
public static <E> Collection<E> checkedCollection(
    Collection<E> c, Class<E> type) {
    return new CheckedCollection<>(c, type);
}

CheckedCollection是一个静态内部类，主要代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
static class CheckedCollection<E> implements Collection<E>, Serializable {
    private static final long serialVersionUID = 1578914078182001775L;
    final Collection<E> c;
    final Class<E> type;
    void typeCheck(Object o) {
        if(o ! = null && ! type.isInstance(o))
                throw new ClassCastException(badElementMsg(o));
        }
        private String badElementMsg(Object o) {
            return "Attempt to insert " + o.getClass() +
                " element into collection with element type " + type;
        }
        CheckedCollection(Collection<E> c, Class<E> type) {
            if(c==null || type == null)
                throw new NullPointerException();
            this.c = c;
            this.type = type;
        }
        public int size()                     { return c.size(); }
        public boolean isEmpty()             { return c.isEmpty(); }
        public boolean contains(Object o) { return c.contains(o); }
        public Object[] toArray()           { return c.toArray(); }
        public <T> T[] toArray(T[] a)      { return c.toArray(a); }
        public String toString()             { return c.toString(); }
        public boolean remove(Object o)    { return c.remove(o); }
        public void clear()                   {          c.clear(); }
        public boolean containsAll(Collection<? > coll) {
            return c.containsAll(coll);
        }
        public boolean removeAll(Collection<? > coll) {
            return c.removeAll(coll);
        }
        public boolean retainAll(Collection<? > coll) {
            return c.retainAll(coll);
        }
        public Iterator<E> iterator() {
            final Iterator<E> it = c.iterator();
            return new Iterator<E>() {
                public boolean hasNext() { return it.hasNext(); }
                public E next()             { return it.next(); }
                public void remove()      {          it.remove(); }};
        }
        public boolean add(E e) {
            typeCheck(e);
            return c.add(e);
        }
    }

代码比较简单，add方法中，会先调用typeCheck进行类型检查。其他checkedXXX方法的实现也都类似，我们就不赘述了。

3．线程安全

关于线程，我们后续章节会详细介绍，这里简要说明下。之前我们介绍的各种容器类基本都不是线程安全的，也就是说，如果多个线程同时读写同一个容器对象，是不安全的。

Collections提供了一组方法，可以将一个容器对象变为线程安全的，比如：

1
2
3
4
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)
public static <T> Set<T> synchronizedSet(Set<T> s)

需要说明的是，这些方法都是通过给所有容器方法加锁来实现的，这种实现并不是最优的。Java提供了很多专门针对并发访问的容器类，我们在第17章介绍。

12.2.6 小结

本节介绍了类Collections中的两类操作。第一类操作是一些通用算法，包括查找、替换、排序、调整顺序、添加、修改等，这些算法操作的都是容器接口对象，这是面向接口编程的一种体现，只要对象实现了这些接口，就可以使用这些算法。第二类操作都返回一个容器接口对象，这些方法代表两种设计模式，一种是适配器，另一种是装饰器，我们介绍了这两种设计模式，以及这些方法的用法、适用场合和实现机制。