Java集合框架概览

1 介绍

Java平台提供一个集合框架(Collections Framework)。例如，A集合是代表一组对象（例如,经典的Vector类）。集合框架是用于表示和操作集合的统一体系结构，使集合可以独立于具体实现而进行操作。

1.1 集合框架的主要优点是：

• 减少编程成本(Reduces programming effort)，通过提供数据结构和算法减少编程工作，无需自己实现
• 提高性能(Increases performance)，通过提供高性能的数据结构和算法实现来提高性能，由于每个接口的各种实现是可互换的，因此可以通过切换实现来调整程序
• 提供API间的互操作性(Provides interoperability between unrelated APIs)，通过建立通用语言实现来回传递集合，提供不相关API之间的互操作性
• 降低学习API接口的学习成本(Reduces the effort required to learn APIs)，只需学习集合框架提供的API
• 降低设计和实现相关API的难度(Reduces the effort required to design and implement APIs)，无需自己实现相关集合接口
• 提高软件复用性(Fosters software reuse)，通过为集合和算法提供标准接口来促进软件重用，以便对其进行操作

1.2 集合框架的组成

• 集合接口(Collection interfaces)，代表不同类型的集合，如sets、lists和maps。这些接口构成框架的基础
• 通用实现(General-purpose implementations)，集合接口的主要实现
• 遗留实现(Legacy implementations)，早期版本的集合类，如Vector和Hashtable被改进以实现集合接口
• 特殊用途实现(Special-purpose implementations)，专为在特殊情况下使用而设计的实现，这些实现表现出非标准性能特征，使用或行为会受到限制
• 并发实现(Concurrent implementations)，为高度并发使用而设计的实现
• 包装器实现(Wrapper implementations)，向其他实现添加功能，诸如同步之类的功能
• 便利实现(Convenience implementations)，集合接口的高性能“迷你实现”
• 抽象实现(Abstract implementations)，实现集合的部分接口，有助于自定义实现
• 算法(Algorithms)，使用静态方法在集合上提供实用功能，例如对列表进行排序
• 基础设施(Infrastructure)，为集合接口提供必要支持的接口
• 数组工具(Array Utilities)，用于基本类型和引用对象数组的操作工具函数，严格来说，不是集合框架的一部分，此功能与集合框架同时添加到Java平台，并依赖于某些相同的基础结构

2 集合接口

集合接口大体分为两组：

2.1 java.util.Collection组

• java.util.List
• 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

2.2 java.util.Map组

严格说，这不是真正的集合，但是这类接口有这类集合的操作接口，这使它们可以类似集合进行操作，主要由以下接口：

• java.util.SortedMap
• java.util.NavigableMap
• java.util.concurrent.ConcurrentMap
• java.util.concurrent.ConcurrentNavigableMap

2.3 集合接口说明

集合接口中的许多修改方法都标记为可选的。允许实现不执行这些操作中的一个或多个，如果企图调用它们则抛出运行时异常（UnsupportedOperationException）；每个实现的文档必须指定支持哪些可选操作。引入了几个术语来帮助本规范：

• Collections that do not support modification operations (such as add, remove and clear) are referred to as unmodifiable. Collections that are not unmodifiable are modifiable.
• Collections that additionally guarantee that no change in the Collection object will be visible are referred to as immutable. Collections that are not immutable are mutable.
• Lists that guarantee that their size remains constant even though the elements can change are referred to as fixed-size. Lists that are not fixed-size are referred to as variable-size.
• Lists that support fast (generally constant time) indexed element access are known as random access lists. Lists that do not support fast indexed element access are known as sequential access lists. The RandomAccess marker interface enables lists to advertise the fact that they support random access. This enables generic algorithms to change their behavior to provide good performance when applied to either random or sequential access lists.

大致意思如下：

• 如果集合不支持修改操作（例如添加，删除和清除）则称为不可修改的(unmodifiable)，如果集合不是不可修改的则成为可修改的(modifiable)
• 如果集合额外保证Collection对象中没有可见变化的称为不可变(immutable)，如果集合不是不可变的称为可变的(mutable)
• 即使元素可以更改，保证其大小保持不变的Lists也称为固定大小(fixed-size)，非固定大小的Lists称为可变大小(variable-size)
• 如果Lists支持快速（通常是恒定时间）索引元素访问称为随机访问列表(random access lists)，不支持快速索引元素访问的列表称为 顺序访问列表(sequential access lists)；java.util.RandomAccess接口标记列表标识它们支持随机访问，这使得通用算法能够在应用于随机或顺序访问列表时更改其行为以提供良好的性能

其中，某些集合实现受限于存储某些元素（或者是Map的key和value），这些限制元素可能是：

• 特定类型
• 不能为空
• 某些任意Predicate

尝试添加违反实现限制的元素会导致运行时异常，通常是ClassCastException，IllegalArgumentException或NullPointerException。尝试删除或测试是否存在违反实现限制的元素可能会导致异常，一些受限制的集合允许这种用法。

3 集合的实现

实现集合接口的类通常有实现风格+集合的命名形式。通用的实现如下：

接口	哈希表	可调整大小的数组	平衡树	链接列表	哈希表+链表
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap

通用实现支持集合接口中的所有可选操作，并且对它们可能包含的元素没有限制。它们是不同步的，但Collections类中有称为同步包装器(synchronization wrappers)的静态工厂方法，可以为非同步的集合添加同步，包装为同步集合。所有新实现都具有快速失败(fail-fast)的迭代器，它可以检测无效的并发修改，并且可以快速地，清晰地（而不是表现不正常）失败。

AbstractCollection，AbstractSet，AbstractList中，AbstractSequentialList和 AbstractMap类提供核心集合接口的基本实现，以最小的成本来实现所需要的功能。这些类的API文档精确地描述了每个方法的实现方式，因此实现者知道在给定特定实现的基本操作的性能的情况下必须覆盖哪些方法。

同步使用非同步集合（以ArrayList为例）：

List list = Collections.synchronizedList(new ArrayList());
...
synchronized (list) {
  Iterator i = list.iterator(); // Must be in synchronized block
  while (i.hasNext())
      foo(i.next());
}

4 并发集合

应用程式当在多线程的情况下使用集合需要非常小心，通常，这称为并发编程。Java平台对并发编程有着大量的支持。有关详细信息，请参阅Java Concurrency Utilities。

集合的使用如此频繁，以至于API中包含了各种并发友好的接口和集合的实现。这些类型超出了前面讨论的同步包装器，以提供并发编程中经常需要的功能。

常见的并发接口：

• BlockingQueue
• TransferQueue
• BlockingDeque
• ConcurrentMap
• ConcurrentNavigableMap

这些常见的并发接口实现，有关这些实现的正确用法，请参阅API文档

• LinkedBlockingQueue
• ArrayBlockingQueue
• PriorityBlockingQueue
• DelayQueue
• SynchronousQueue
• LinkedBlockingDeque
• LinkedTransferQueue
• CopyOnWriteArrayList
• CopyOnWriteArraySet
• ConcurrentSkipListSet
• ConcurrentHashMap
• ConcurrentSkipListMap

设计目标

主要设计目标是API足够轻量，更重要的是“概念为重(conceptual weight)”。至关重要的是，新功能对于目前的Java程序员来说似乎并没有太大的不同，新功能必须拓展新的能力而不是替换它们；同时，新的API必须足够强大，以提供前面描述的所有优点。

为了保持较小的核心接口数量，接口不会尝试对比可变性(mutability)，可修改(modifiability)和可重新定义(resizability)等细微差别。相反，核心接口中的某些调用是可选的，允许实现能够抛出UnsupportedOperationException以表示它们不支持指定的操作。集合实现者必须清楚地说明实现支持哪些可选操作。

为了使每个核心接口中的方法数量保持较小，只有在以下任一情况下，接口才新增该方法：

• 这是一项真正的基本操作：对于其他操作可以合理定义而言这是一个基本操作
• 有一个令人信服的性能原因以至于某个重要的实现会想要覆盖它

最重要的原因是：所有合理的集合表示都能很好地互操作。这包括数组，数组无法在不更改语言的情况下直接实现Collection接口。因此，框架中所包含使集合能够转变为数组的方法，数组被当做集合对待，maps也被视为集合。

参考

• Collections Framework Overview
• Collections API文档