Java 集合框架系列（一）框架总结

发表于 更新于

集合（collection）表示一组对象。Java SE 提供了集合框架（collections framework），是一个用于表示和操作集合的统一框架，使集合可以独立于实现细节进行操作。集合框架的主要优点如下：

  • 通过提供数据结构和算法实现，使用户无需自行编写，减少编程工作。
  • 通过提供数据结构和算法的高性能实现来提高性能。由于每个接口的各种实现是可互换的，因此可以通过切换实现来调整和优化程序。
  • 通过提供一套标准接口来促进软件重用。
  • 通过建立一种通用语言，为无关联的集合 API 之间提供互操作性。
  • 减少学习成本，只须学习一些特设的集合 API。

集合框架的整体组成如下：

overview

下面分别来看下各组成部分。

集合接口

集合接口分为下面两组，这些接口构成了集合框架的基础：

  • java.util.Collection，表示一组对象集合

    A collection represents a group of objects, known as its elements.

    • Some collections allow duplicate elements and others do not.

    • Some are ordered and others unordered.

    The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List.

    This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

  • java.util.Map，用于存储键值对

    An object that maps keys to values.

    • A map cannot contain duplicate keys;

    • each key can map to at most one value.

Collection

Collection

最基础的集合接口 java.util.Collection 及其子接口如下：

Collection

其中，常用的五个重点接口的方法及使用要点如下：

methods_of_collection

Map

Map

其它集合接口基于 java.util.Map，不是真正的集合。但是，这些接口包含集合视图（collection-view）操作，使得它们可以作为集合进行操作。

Map

java.util.Map 接口的方法如下:

Map methods

集合实现类

抽象类实现

下列抽象类为核心集合接口提供了基本功能实现，以最小化用户自定义实现的成本。这些抽象类的 API 文档精确地描述了各个方法的实现方式，实现者能够参阅并了解哪些方法需要覆盖：

Collection_abstract_class

通用实现

java.util.Collection 的通用实现如下：

collection_impl

java.util.Map 的通用实现如下：

map_impl

集合接口的主要实现，命名通常形如 <*Implementation-style*><*Interface*>。通用实现类汇总如下（左列为接口，表头为数据结构）：

Resizable Array Linked List Hash Table Hash Table + Linked List Balanced Tree Heap
List ArrayList LinkedList
Queue ArrayBlockingQueue LinkedList
LinkedBlockingQueue
LinkedTransferQueue
ConcurrentLinkedQueue		 PriorityBlockingQueue
PriorityQueue
Deque ArrayDeque LinkedList
LinkedBlockingDeque
ConcurrentLinkedDeque
Set HashSet LinkedHashSet TreeSet
Map HashMap LinkedHashMap TreeMap

通用实现的特性如下：

  • 通用实现类支持集合接口中的所有可选操作，并且对包含的元素没有限制。
  • 都是非线程同步的。Collections 工具类提供了称为同步包装器（synchronization wrappers）的静态工厂方法可用于添加同步行为。
  • 所有集合实现都具有快速失败的迭代器（fail-fast iterators），可以检测到无效的并发修改，然后快速失败，而不是表现异常。

遗留实现

早期版本的集合类，已被改进以实现新的集合接口：

  • java.util.Vector - List 接口的可变长数组实现，线程同步，包含其它遗留方法。
  • java.util.Hashtable - Map 接口的散列表实现，线程同步，键和值都不允许为 null，包含其它遗留方法。继承自抽象类 java.util.Dictionary。

并发实现

为高并发使用而设计的实现。详见另一篇《并发实现总结》。

特殊实现

用于特殊情况的实现：

  • CopyOnWriteArrayList 写时复制列表
  • CopyOnWriteArraySet 写时复制列表
  • WeakHashMap
  • IdentityHashMap
  • EnumSet
  • EnumMap

适配器实现（Adaptor）

将某个集合接口适配成另一个：

  • 根据 Map 的通用实现创建一个 Set 的通用实现：

    1
    Collections.newSetFromMap(Map)

  • 以后进先出（Lifo）队列的形式返回 Deque 的视图：

    1
    Collections.asLifoQueue(Deque)

  • 将数组转换为 List 集合：

    1
    Arrays.asList(...)

包装器实现（Wrapper）

用于其它集合实现的功能增强：

  • 返回指定集合的不可修改视图（unmodifiable view），如果尝试修改，则会抛出 UnsupportedOperationException：

    1
    2
    3
    4
    5
    6
    7
    8
    Collections.unmodifiableCollection
    Collections.unmodifiableSet
    Collections.unmodifiableSortedSet
    Collections.unmodifiableNavigableSet
    Collections.unmodifiableList
    Collections.unmodifiableMap
    Collections.unmodifiableSortedMap
    Collections.unmodifiableNavigableMap

  • 返回由指定集合支持的 synchronized 线程同步集合：

    1
    2
    3
    4
    5
    6
    7
    8
    Collections.synchronizedCollection
    Collections.synchronizedSet
    Collections.synchronizedSortedSet
    Collections.synchronizedNavigableSet
    Collections.synchronizedList
    Collections.synchronizedMap
    Collections.synchronizedSortedMap
    Collections.synchronizedNavigableMap

  • 返回指定集合的动态类型安全视图（dynamically type-safe view），如果尝试添加错误类型的元素，则会抛出 ClassCastException。泛型机制虽然提供了编译期类型检查，但可以绕过此机制。动态类型安全试图消除了这种可能性：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Collections.checkedCollection
    Collections.checkedQueue
    Collections.checkedSet
    Collections.checkedSortedSet
    Collections.checkedNavigableSet
    Collections.checkedList
    Collections.checkedMap
    Collections.checkedSortedMap
    Collections.checkedNavigableMap

便利实现

集合接口的高性能版“迷你实现”：

  • 返回一个不可变集合（immutable），不包含任何元素：

    1
    2
    3
    4
    5
    6
    7
    Collections.emptySet
    Collections.emptySortedSet
    Collections.emptyNavigableSet
    Collections.emptyList
    Collections.emptyMap
    Collections.emptySortedMap
    Collections.emptyNavigableMap

  • 返回一个不可变集合（immutable），仅包含一个元素：

    1
    2
    3
    Collections.singleton
    Collections.singletonList
    Collections.singletonMap

  • 返回一个不可变集合（immutable），包含指定元素的 N 个拷贝：

    1
    Collections.nCopies

  • 返回一个由指定数组支持的定长集合（fixed-size）：

    1
    Arrays.asList

基础设施

为集合接口提供必要支持的接口。例如：

  • 迭代器 Iterator、ListIterator
  • 排序接口 Comparable、Comparator
  • 运行时异常 UnsupportedOperationException、ConcurrentModificationException
  • 标记接口 RandomAccess

算法和工具实现

算法实现。由工具类 Collections 提供，用于集合，提供了很多静态方法例如 sort 排序、binarySearch 查找、replaceAll 替换等。这些算法体现了多态性，因为相同的方法可以在相似的接口上有着不同的实现。

数组工具。由工具类 Arrays 提供，用于基本类型和引用类型数组，提供了很多静态方法例如 sort 排序、binarySearch 查找等。严格来说，这些工具不是集合框架的一部分，此功能在集合框架引入的同时被添加到 Java 平台，并依赖于一些相同的基础设施。

参考

https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html

Why Java Collection Framework doesn’t contain Tree and Graph ?

https://www.baeldung.com/category/java/