九十一、Java标准库－容器(Collection)

10_standard_library_01_collection

第八十九章 Java标准库－容器(Collection)

1 简介

为了帮助开发人员更快、更高效地完成Java程序开发，Java的设计者们在发布Java开发环境时，同时也发布了Java标准库(Java Standard Library)，提供了在软件开发过程中的一些常用功能。Java标准库包括：java.lang包、java.io包、java.util包等。本篇将介绍与容器相关的一些概念和使用方法。

2 Java Collections Framework

Java标准库包含了一个容器设计框架(Collections Framework)。设计这个容器框架的目的是为了向开发人员提供通用的、多样的容器功能，并且提供较好的性能，增加代码重用率。在容器框架中包含了许多功能，例如，容器框架提供了：

各种类型容器的接口。它们包括链表(List)，集合(Set)，映射(Map)等常用的数据结构接口。
各种常用的数据结构的实现。例如，在链表接口下，容器框架实现了LinkedList和ArrayList。
各种并发容器。这些容器支持安全的并发操作，降低了开发并发程序的难度。
各种简化的实现(Convenience Implementation)。有些容器的实现是非常复杂的。容器框架仅提供了一个高性能的、简化的实现版本，供开发人员使用。与此同时，这些简化的实现版本也为开发人员提供了一个实现指南或者参考，帮助开发人员实现更复杂的逻辑。
抽象实现(Abstract Implementation)。有些容器的实现依赖于具体的业务逻辑。在这种情况下，框架仅实现了通用部分的逻辑，而将依赖于业务逻辑的部分留给开发人员实现。
通用算法。容器框架实现了一些可应用于容器之上的通用算法，例如查找和排序算法。
工具类(Utility)。帮助开发人员更方便的使用各种容器。容器框架提供了方便的函数，实现数组与容器相互转换。

Java Collections Framework包含的常用接口如下图所示。

图一 Java Collections Framework常用接口结构图

3 容器接口与实现

3.1 容器分类

从功能和概念上看，容器还可以再细分为以下几个类别。

通用容器(General-Purpose Collections)是我们最为常见的容器。它包含多个元素，开发人员能够在容器上使用常见的增、删、查、更新操作。

不可变更容器(Unmodifiable Collections)是一种"只读"的容器。当开发人员尝试修改容器时(例如：添加元素或者删除元素)，该容器会抛出UnsupportedOperationException异常。但是，这种"不可变更"是指在容器上不可变更；容器中的元素还是可能可以变更的。这依赖于具体的实现。

视图容器(View Collections)是指那些只实现了容器的接口，但并不真正包含元素的容器。视图容器往往"依附"于另一个容器之上，使用另一个容器存放元素，而自身仅提供相应的数据访问。例如，List类中的subList()方法返回的往往是一个视图容器。

那么，将上述两种属性结合在一起，就形成了不可变更的视图容器(Unmodifiable View Collections)。一般的，Collections.unmodifiableCollection()和Collections.unmodifiableList()返回的是不可变更的视图容器。

容器序列化是一个很重要的特性。在容器框架中，容器的接口并未继承Serializable接口，但是，具体容器的实现继承了Serializable接口。这样的设计是为了将容器的接口与序列化接口分离开，毕竟，容器和序列化是两个相互独立的功能。当容器实现类继承了Serializable接口之后，这个容器就具备了序列化的能力。但是，值得注意的是，这并不能保证容器是可序列化的，因为容器中的元素可能不能序列化。所以，这种情况被称为容器是"conditionally serializable(有条件的可序列化)"。只有当容器中所有元素都是可序列化的，并且容器继承了Serializable接口时，该容器才是可序列化的。

3.2 接口分类

在Java容器框架中，容器类的接口大致可分为两组。第一组是Collection家庭。在这一组中，接口都继承自java.util.Collection接口。这组接口有：

java.util.Set
java.util.SortedSet
java.util.NavigableSet
java.util.Queue
java.util.concurrent.BlockingQueue
java.util.concurrent.TransferQueue
java.util.Deque
java.util.concurrent.BlockingDeque

另一组接口都继承自java.util.Map。这些接口包括：

java.util.SortedMap
java.util.NavigableMap
java.util.concurrent.ConcurrentMap
java.util.concurrent.COncurrentNavigableMap

3.3 实现分类

容器框架中提供了一些具体的实现。我们可以从下表中清晰的看到这些实现的特点特性。

接口	Linked List	Resizable Array	Hash Table	Balanced Tree	Hash Table + Linked List
Set			HashSet	TreeSet	LinkedHashSet
List	LinkedList	ArrayList
Deque	LinkedList	ArrayDeque
Map			HashMap	TreeMap	LinkedHashMap

3.4 并发接口与实现

容器框架中的并发接口提供了可用于并发控制的容器功能。这些接口包括：BlockingQueue、TransferQueue、BlockingDeque、ConcurrentMap和ConcurrentNavigableMap。

容器框架还提供了相关的实现。这些实现包括：LinkedBlockingQueue、ArrayBlockingQueue、PriorityBlockingQueue、DelayQueue、SynchronousQueue、LinkedBlockingDeque、LinkedTransferQueue、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentSkipListSet、ConcurrentHashMap和ConcurrentSKipListMap。

4 java.util.Collection接口

java.util.Collection接口提供了容器的基本操作接口。我们将这些接口分为以下几类。

4.1 增、删、查操作

Collection提供了增加元素、删除元素和查找元素的基本操作。add()和addAll()用于向容器添加元素。它们的区别是add()方法一次添加一个元素，而addAll()方法一次可以将另一个容器中的所有元素添加入当前的容器之中。当有元素添加成功时，方法返回true。否则返回false。

boolean add(E e);
boolean addAll(Collection<? extends E> c);

remove()、removeAll()和removeIf()用于从容器中删除元素。remove()方法一次删除一个元素；removeAll()则一次删除多个元素。removeIf()则删除满足给定条件的元素。remove()和removeAll()方法使用Objects.equals()来判断当前元素是否为待删除的元素。当有元素删除时，方法返回true。否则返回false。clear()方法则删除容器中所有的元素。

boolean remove(Object o);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter);
void clear();

contains()和containsAll()方法则判断容器中是否包含指定的元素。contains()判断是否包含某一个元素；containsAll()则判断是否包含所有元素。它们使用Objects.equals()方法判断元素是否相同。isEmpty()方法则判断容器是否为空。size()则返回容器中元素的个数。

boolean contains(Object o);
boolean containsAll(Collection<?> c);
boolean isEmpty();
int size();

4.2 遍历

iterator()方法返回一个Iterator对象，用于依次遍历容器中的所有元素。stream()方法返回一个Stream对象，方便开发人员进一步处理容器中的元素(特别适合使用函数式编程的方式依次处理容器中的所有元素)。

Iterator<E> iterator();
default Stream<E> stream();
default Stream<E> parallelStream();

4.3 转换成数组

有时，容器对象需要转换成数组对象。此时，开发人员可以使用toArray()方法。

Object[] toArray();
default <T> T[] toArray(IntFunction<T[]> generator);
<T> T[] toArray(T[] a);

5 java.util.Collections类

java.util.Collections类提供了一些与容器相关的工具方法，方便开发人员使用容器，实现一些常用的逻辑。

5.1 创建一个空的容器对象

Collections类提供了创建多种类型的空容器的方法。这些空容器都是不可变更容器对象。开发人员不能向其添加或者删除元素。但是，这些空对象非常有用，特别是使用函数式编程时，用于处理默认场景或者异常场景。例如，emptyList()创建一个空的List类对象。

static <T> Enumeration<T> emptyEnumeration();
static <T> List<T> emptyList();
static <K, V> Map<K, V> emptyMap();
static <K, V> NavigableMap<K, V> emptyNavigableMap();
static <E> NavigableSet<E> emptyNavigableSet();
static <T> Set<T> emptySet();
static <K, V> SortedMap<K, V> emptySortedMap();
static <E> SortedSet<E> emptySortedSet();

在实现方面，Collections类内部定义了EmptyList、EmptySet等类，并创建了共享对象。上述的方法调用直接返回这些共享的对象。这与享元模式的思想类似，所有的emptyList()方法调用返回同一个对象EMPTY_LIST。下面的源代码摘自OpenJDK 15版本的实现。

// OpenJDK 15
package java.util.Collections;

public class Collections {
    ...
    public static final List EMPTY_LIST = new EmptyList<>();

    public static final <T> List<T> emptyList() {
        return (List<T>) EMPTY_LIST;
    }
    ...
    private static class EmptyList<E> extends AbstractList<E> implements RandomAccess, Serializable {
        public int size() {return 0;}

        public E get(int index) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
        ...
    }
}

5.2 创建线程安全的容器对象

如果开发人员已经获得了一个容器对象，并且希望在此基础上创建一个线程安全(thread-safe)的容器对象的话，可以使用如下方法。

static <T> Collection<T> synchronizedCollection(Collection<T> c);
static <T> List<T> synchronizedList<List<T> list>;
static <K, V> Map<K, V> synchronizedMap(Map<K, V> m);
static <K, V> NavigableMap<K, V> synchronizedNavigableMap(NavigableMap<K, V> m);
static <T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s);
static <T> Set<T> synchronizedSet(Set<T> s);
static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> m);
static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s);

实际上，Collections类定义了一个内部类SynchronizedCollection。这个类会使用关键字synchronized为每个函数调用上锁，以提供线程安全。OpenJDK 15的实现代码如下所示。

// OpenJDK 15
package java.util.Collections;

public class Collections {
    ...
    static <T> Collection<T> synchronizedCollection(Collection<T> c) {
        return new SynchronizedCollection<>(c);
    }
    ...
    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; // 会在this对象上锁
        }
        ...

        public boolean add(E e) {
            synchronized (mutex) {return c.add(e);}
        }
        public boolean remove(Object o) {
            synchronized (mutex) {return c.remove(o);}
        }
        ...
    }
}

类似的，Collections类还定义了内部类SynchronizedList、SynchronizedSet、SynchronizedMap等用于实现不同类型的线程安全容器。

5.3 创建不可变更的容器对象

当开发人员已获得一个容器对象后，并且希望在此基础之上创建一个不可变更的容器对象时，可使用如下方法。实际上，下面的方法会创建一个不可变更的视图容器(Unmodifiable View Collections)。

static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c);
static <T> List<T> unmodifiableList(List<? extends T> list);
static <K, V> Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m);
static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m);
static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s);
static <T> Set<T> unmodifiableSet(Set<? extends T> s);
static <K, V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m);
static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s);

实际上，Collections类定义了一个内部类UnmodifiableCollection。这个类仅仅是一个容器类的包装。当调用add()或者remove()这些可改变容器对象的方法时，直接抛出UnsupportedOperationException异常。OpenJDK 15的实现代码如下所示。

// OpenJDK 15
package java.util.Collections;

public class Collections {
    ...
    public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
        return new UnmodifiableCollection<>(c); // 返回一个内部类UnmodifiableCollection对象
    }
    ...
    static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
        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 add(E e) {
            throw new UnsupportedOperationException();
        }
        public boolean remove(Object o) {
            throw new UnsupportedOperationException();
        }
        ...
    }
}

类似的，Collections类还定义了内部类UnmodifiableList、UnmodifiableSortedSet、UnmodifiableMap等用于实现不同类型的不可变更容器。

5.4 创建类型安全的视图容器对象

当开发人员已获得一个容器对象后，并且希望在此基础之上创建一个类型安全的容器对象时，可使用如下方法。在使用时，开发人员需要指定期望的类型type。

static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type);
static <E> List<E> checkedList(List<E> list, Class<E> type);
static <K, V> Map<K, V> checkedMap(Map<K, V>m, Class<K> keyType, Class<V> valueType);
static <K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K,V> m, Class<K> keyType, Class<V> valueType);
static <E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s, Class<E> type);
static <E> Queue<E>	checkedQueue(Queue<E> queue, Class<E> type);
static <E> Set<E> checkedSet(Set<E> s, Class<E> type);
static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m, Class<K> keyType, Class<V> valueType);
static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, Class<E> type);

实际上，Collections类定义了一个内部类CheckedCollection。这个类仅仅是一个容器类的包装。当调用add()或者remove()时，CheckedCollection类会进行元素类型的检查。如果类型不匹配的话，直接抛出ClassCastException异常。OpenJDK 15的实现代码如下所示。

// OpenJDK 15
package java.util.Collections;

public class Collections {
    ...
    public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type) {
        return new CheckedCollection<>(c, type);
    }
    ...
    static class CheckedCollection<E> implements Collection<E>, Serializable {
        final Collection<E> c;
        final Class<E> type;
        ...
        CheckedCollection(Collection<E> c, Class<E> type) {
            this.c = Objects.requireNonNull(c, "c");
            this.type = Objects.requireNonNull(type, "type");
        }
        ...
        E typeCheck(Object o) {
            if (o != null && !type.isInstance(o))
                throw new ClassCastException(badElementMsg(o));
            return (E) o;
        }
        
        public boolean add(E e)          { return c.add(typeCheck(e)); }
        ...
    }
}

类似的，Collections类还定义了内部类CheckedList、CheckedSet、CheckedMap等用于实现不同类型的不可变更容器。

5.5 创建包含单个元素的容器对象

如下方法可用于创建只包含指定元素的容器。这些容器是不可变更的、只包含一个元素。

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

Collections类也定义了内部的单元素容器类，如下所示。

// OpenJDK 15
package java.util.Collections;

public class Collections {
    ...
    public static <T> List<T> singletonList(T o) {
        return new SingletonList<>(o);
    }

    private static class SingletonList<E> extends AbstractList<E> implements RandomAccess, Serializable {
        private final E element;

        SingletonList(E obj) {element = obj;}

        ...
        public int size() {return 1;}

        public boolean contains(Object obj) {return eq(obj, element);}

        public E get(int index) {
            if (index != 0)
              throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
            return element;
        }
        ...
    }
}

5.6 二分查找

binarySearch()方法能在已排序的List对象上进行二分查找。Comparator参数用于在查找过程中比较两个对象的大小。

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

5.7 排序

sort()方法能将给定的List对象按照指定的大小排序。Comparator用于比较两个对象之间的大小。

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

5.8 最大元素和最小元素

Collections类中的min()和max()方法用于查找容器中的最大元素和最小元素。Comparator对象用于比较两个元素之间的大小。

static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll);
static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp);
static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll);
static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp);

5.9 逆向Comparator

从上面的接口中可以看出，Comparator是一个重要的参数。它能够控制元素比较的结果，改变容器中元素的排列顺序。Collections类中的reverseOrder()方法能够根据给定的Comparator对象，创建出一个逆向的Comparator对象。

static <T> Comparator<T> reverseOrder();
static <T> Comparator<T> reverseOrder(COmparator<T> cmp);

其时，逆向Comparator的实现非常简单。就是把比较的两个对象的比较顺序交换即可。当然，Collections类做了一些优化，以便于程序能够共享比较器对象。

// OpenJDK 15
package java.util.Collections;

public class Collections {
    ...
    public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
        if (cmp == null) {
            return (Comparator<T>) ReverseComparator.REVERSE_ORDER;  // 使用共用的共享对象
        } else if (cmp == ReverseComparator.REVERSE_ORDER) {
            return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;　// 使用共用的共享对象
        } else if (cmp == Comparators.NaturalOrderComparator.INSTANCE) {
            return (Comparator<T>) ReverseComparator.REVERSE_ORDER;　// 使用共用的共享对象
        } else if (cmp instanceof ReverseComparator2) {
            return ((ReverseComparator2<T>) cmp).cmp;　// 如果需要逆向比较器的逆向比较器，则使用原始对象即可
        } else {
            return new ReverseComparator2<>(cmp);
        }
    }

    private static class ReverseComparator2<T> implements Comparator<T>, Serializable {
        final Comparator<T> cmp;

        ReverseComparator2(Comparator<T> cmp) {
            assert cmp != null;
            this.cmp = cmp;
        }

        public int compare(T t1, T t2) {
            return cmp.compare(t2, t1); // 交换比较的顺序
        }

        @Override
        public Comparator<T> reversed() {
            return cmp;
        }
        ...
    }
}

Collections类中还提供了更多的接口。因为这些接口仅应用于某一种容器，因此，我们将在介绍这些容器的时候再介绍这些接口方法。例如： rotate()方法和shuffle()方法都应用于List容器对象。因此，我们将在介绍List容器时再介绍它们。

6 小结

本章介绍了Java标准库中的容器框架以及几种容器分类。并且在此基础之上，介绍了java.util.Collection接口和java.util.Collections类。Collection接口代表了一大类的容器接口，它表示包含多个元素的容器。Collections则为容器提供了许多方便的方法，帮助开发人员更高效的使用容器类。

注册用户登陆后可留言