JAVA collections framework

JAVA collections framework

原文：Collections Framework Overview (oracle.com)

有一些内容是我自己加的，比如常见数据结构的用法

Introduction 介绍

Java 平台包括一个集合框架。集合是表示一组对象的对象（例如经典的 Vector 类）。集合框架是一个统一的架构，用于表示和操作集合，使集合能够独立于实现细节进行操作。

集合框架的主要优点是：

• 通过提供数据结构和算法来减少编程工作量，这样您就不必自己编写它们。

• 通过提供高性能的数据结构和算法实现来提高性能。由于每个接口的各种实现是可互换的，因此可以通过切换实现来调整程序。

• 通过建立公共语言来传递集合，提供不相关 API 之间的互操作性。

• 通过要求您学习多个特设集合 API 来减少学习 API 所需的工作量。

• 通过不要求您生成特设集合 API 来减少设计和实现 API 所需的工作量。

• 通过为集合和操作它们的算法提供标准接口来促进软件重用。

java collections framework包含了以下:

• Collection interfaces： 表示不同类型的集合，如集合、列表和映射。这些接口构成了框架的基础。

• General-purpose implementations： 集合接口的主要实现。

• Legacy implementations： 早期版本中的集合类Vector和Hashtable经过了改造，实现了集合接口。

• Special-purpose implementations： 设计用于特殊情况的实现。这些实现显示了非标准的性能特征、使用限制或行为。

• Concurrent implementations： 为高并发使用而设计的实现。

• Wrapper implementations： 向其他实现添加功能，例如synchronization。

• Convenience implementations： 集合接口的高性能“迷你实现”。

• Abstract implementations： 集合接口的部分实现，以方便自定义实现。

• Algorithms： 静态方法，在集合上执行一些有用的功能，如列表排序。

• Infrastructure： 为集合接口提供基本支持的接口。

• Array Utilities： 基本类型数组和引用对象的实用函数。严格来说，这个功能不是collections framework的一部分，它是与集合框架同时添加到Java平台上的，依赖于相同的基础设施。

Collection Interfaces 集合接口

collection Interfaces被分为了两部分, 最基础的接口是java.util.Collection，它有如下子接口：

• java.util.Set 集合接口，它定义了一组不包含重复元素的集合。HashSet 是它的一个实现类。

• java.util.SortedSet 可排序的集合接口，它是 Set 的子接口，定义了一个有序集合，其中元素按照自然顺序或者指定的比较器排序。

• java.util.NavigableSet 可导航集合接口，它是 SortedSet 的子接口，提供了一些额外的方法来导航集合中的元素，例如 lower()、floor()、higher() 和 ceiling() 等方法。TreeSet 是它的一个实现类。

• java.util.Queue 队列接口，它定义了一组先进先出（FIFO）的队列。

• java.util.concurrent.BlockingQueue 阻塞队列接口，它是 Queue 的子接口，提供了两种额外的功能：当队列为空时，从 BlockingQueue 中获取元素的操作会被阻塞；当队列达到最大容量时，插入 BlockingQueue 的操作会被阻塞。

• java.util.concurrent.TransferQueue 传输队列接口，它是 BlockingQueue 的子接口，提供了一个 transfer 方法，生产者可以调用这个方法来等待消费者调用 take 或者 poll 方法从队列中获取数据。它还提供了非阻塞和超时版本的 tryTransfer 方法。

• java.util.Deque 双端队列接口，它定义了一个双端队列，可以从两端插入和删除元素。

• java.util.concurrent.BlockingDeque 阻塞双端队列接口，它是 Deque 的子接口，提供了两种额外的功能：当队列为空时，从 BlockingDeque 中获取元素的操作会被阻塞；当队列达到最大容量时，插入 BlockingDeque 的操作会被阻塞。

其他集合接口基于java.util.Map，它们都不是真正的集合。不过，这些接口包含了集合视图操作，因此可以将它们作为集合进行操作。Map有以下子接口:

• java.util.SortedMap 可排序的映射接口，它扩展了 Map 接口，定义了一个有序映射，其中键按照自然顺序或者指定的比较器排序。

• java.util.NavigableMap 可导航映射接口，它扩展了 SortedMap 接口，提供了一些额外的方法来导航映射中的键，例如 lowerKey()、floorKey()、higherKey() 和 ceilingKey() 等方法。

• java.util.concurrent.ConcurrentMap 并发映射接口，它扩展了 Map 接口，定义了一个支持并发访问的映射。

• java.util.concurrent.ConcurrentNavigableMap 并发可导航映射接口，它扩展了 ConcurrentMap 和 NavigableMap 接口，定义了一个支持并发访问和导航的映射。

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

• 不支持修改操作（如 add、remove 和 clear）的集合称为不可修改的。不是不可修改的集合是可修改的。

• 另外保证集合对象中没有任何更改可见的集合称为不可变的。不是不可变的集合是可变的。

• 保证其大小保持恒定，即使元素可以更改也是如此的列表称为固定大小。不是固定大小的列表称为可变大小。

• 支持快速（通常是常数时间）索引元素访问的列表称为随机访问列表。不支持快速索引元素访问的列表称为顺序访问列表。RandomAccess 标记接口使列表能够宣传它们支持随机访问。这使得通用算法在应用于随机访问列表或顺序访问列表时能够改变其行为以提供良好性能

一些实现限制了可以存储的元素（或在 Maps 的情况下，键和值）。可能的限制包括要求元素：

• 属于特定类型。

• 不为空。

• 遵守任意谓词。

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

Collection Implementations 集合实现

实现集合接口的类通常具有 <Implementation-style><Interface> 形式的名称。通用实现在下表中总结：

通用实现支持集合接口中的所有可选操作，并且对它们可能包含的元素没有限制。它们是不同步的，但是 Collections 类包含称为同步包装器的静态工厂，可以用于向许多不同步的集合添加同步。所有新实现都具有快速失败迭代器，它们检测无效的并发修改，并快速且干净地失败（而不是表现不稳定）。

AbstractCollection、AbstractSet、AbstractList、AbstractSequentialList 和 AbstractMap 类提供了核心集合接口的基本实现，以最小化实现它们所需的工作量。这些类的 API 文档准确描述了每个方法如何实现，因此实现者知道哪些方法必须重写，给定特定实现的基本操作的性能。

Concurrent Collections 并发集合

使用多个线程使用集合的应用程序必须谨慎编程。通常，这被称为并发编程。Java 平台包括对并发编程的广泛支持。有关详细信息，请参阅 Java 并发实用程序。

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

这些并发感知（concurrent-aware）接口可用：

• BlockingQueue

• TransferQueue

• BlockingDeque

• ConcurrentMap

• ConcurrentNavigableMap

以下并发感知实现类可用。请参阅 API 文档以了解这些实现的正确用法。

• LinkedBlockingQueue

• ArrayBlockingQueue

• PriorityBlockingQueue

• DelayQueue

• SynchronousQueue

• LinkedBlockingDeque

• LinkedTransferQueue

• CopyOnWriteArrayList

• CopyOnWriteArraySet

• ConcurrentSkipListSet

• ConcurrentHashMap

• ConcurrentSkipListMap

他们的用途：

• LinkedBlockingQueue 和 ArrayBlockingQueue 是 BlockingQueue 接口的实现类，它们提供了一个线程安全的队列，支持阻塞操作。

• PriorityBlockingQueue 是一个支持优先级排序的 BlockingQueue 实现类。

• DelayQueue 是一个 BlockingQueue 实现类，它的元素只有在延迟时间到达后才能从队列中取出。

• SynchronousQueue 是一个特殊的 BlockingQueue 实现类，它没有容量，每个插入操作必须等待另一个线程进行相应的删除操作。

• LinkedBlockingDeque 是 BlockingDeque 接口的实现类，它提供了一个线程安全的双端队列，支持阻塞操作。

• LinkedTransferQueue 是 TransferQueue 接口的实现类，它提供了一个线程安全的队列，支持阻塞操作和传输操作。

• CopyOnWriteArrayList 和 CopyOnWriteArraySet 是线程安全的列表和集合实现类，它们在修改操作时复制底层数组来实现线程安全。

• ConcurrentSkipListSet 和 ConcurrentSkipListMap 是基于跳表数据结构的线程安全集合和映射实现类。

• ConcurrentHashMap 是一个线程安全的哈希映射实现类。

一些可能有用的说明：

1. DelayQueue 是一个实现了 BlockingQueue 接口的无界阻塞队列，它的元素只有在延迟时间到达后才能从队列中取出。这种队列非常适合用于实现定时任务调度。

   例如，假设需要在未来的某个时间执行一些任务，可以创建一个实现了 Delayed 接口的任务类，将任务的延迟时间设置为未来执行时间与当前时间的差值，并将任务添加到 DelayQueue 中。当延迟时间到达时，就可以从队列中取出任务并执行它。

   除了定时任务调度之外，`DelayQueue` 还可以用于实现缓存过期、会话管理等功能。

2. ConcurrentSkipListSet 是一个线程安全的有序集合，它实现了 NavigableSet 接口。它内部使用跳表数据结构来实现，支持快速查找、插入和删除操作。

   与 TreeSet 不同，ConcurrentSkipListSet 是线程安全的，可以在多线程环境中安全地使用。它支持并发访问和修改，提供了一些额外的并发方法，如 addIfAbsent() 和 addAllAbsent() 等。

   ConcurrentSkipListSet 的元素按照自然顺序或者指定的比较器排序。它还支持导航方法，如 lower()、floor()、higher() 和 ceiling() 等。

   总之，ConcurrentSkipListSet 是一个线程安全的有序集合，适用于多线程环境中需要快速查找、插入和删除操作的场景。

3. CopyOnWriteArrayList 是一个线程安全的列表实现类，它实现了 List 接口。它在修改操作（如 add 和 set）时复制底层数组来实现线程安全。这种方法的优点是可以在不需要额外同步的情况下安全地遍历列表，但缺点是修改操作的开销较大。

   由于 CopyOnWriteArrayList 的修改操作开销较大，所以它适用于读操作远多于写操作的场景。例如，事件监听器列表通常在初始化时添加一些监听器，然后在运行时很少修改，但经常遍历以调用监听器。这种场景下使用 CopyOnWriteArrayList 可以获得较好的性能。

   总之，CopyOnWriteArrayList 是一个线程安全的列表实现类，适用于读操作远多于写操作的场景。

Design Goals 设计目标

主要的设计目标是产生一个体积小、更重要的是“概念重量”小的 API。至关重要的是，新功能不能让当前的 Java 程序员感到太不同；它必须增强当前的功能，而不是取代它们。同时，新 API 必须足够强大，能够提供前面描述的所有优点。

为了保持核心接口数量较少，接口不会尝试捕获诸如可变性、可修改性和可调整大小等微妙区别。相反，核心接口中的某些调用是可选的，使实现能够抛出 UnsupportedOperationException 来指示它们不支持指定的可选操作。集合实现者必须清楚地记录实现支持哪些可选操作。

为了保持每个核心接口中的方法数量较少，接口仅包含方法，如果：

• 它是一个真正基础的操作：可以合理地定义其他基础操作，

• 有一个令人信服的性能原因，为什么一个重要的实现会想要覆盖它。

至关重要的是所有合理的集合表示都能很好地互操作。这包括数组，它们不能在不更改语言的情况下直接实现 Collection 接口。因此，框架包括将集合移动到数组、将数组视为集合和将映射视为集合的方法。