课程：实现

实现是用于存储集合的数据对象，它们实现 the Interfaces section 中描述的接口。本课程描述了以下几种实现：

• General-purpose implementations (通用实现) 是最常用的实现，专为日常使用而设计。它们在标题为通用实现的表中进行了总结。
• Special-purpose implementations (专用实现) 旨在用于特殊情况，并显示非标准性能特征、使用限制或行为。
• Concurrent implementations (并发实现) 旨在支持高并发性，通常以牺牲单线程性能为代价。这些实现是 java.util.concurrent 包的一部分。
• Wrapper implementations (包装实现) 与其他类型的实现(通常是通用实现)结合使用，以提供增加或限制的功能。
• Convenience implementations (便利实现) 是通常通过静态工厂方法提供的迷你实现，为特殊集合(例如，单例集)的通用实现提供方便，有效的替代方案。
• Abstract implementations (抽象实现) 是骨架实现，有助于构建自定义实现 — 稍后将在 Custom Collection Implementations 部分中进行介绍。一个高级主题，并不是特别困难，但相对较少的人需要这样做。

通用实现总结在 下表 中。

从表中可以看出，Java 集合框架提供了一些 Set，List，和 Map 接口的通用实现。在每种情况下，一个实现 — HashSet，ArrayList，HashMap — 显然是大多数应用程序使用的，所有其他条件相同。请注意，SortedSet 和 SortedMap 接口在表中没有行。每个那种接口都有一个实现 (TreeSet 和 TreeMap)并列在 Set 和 Map 行。有两个通用的 Queue 实现 — LinkedList，也是 List 实现，PriorityQueue，从表中省略。这两个实现提供了非常不同的语义：LinkedList 提供 FIFO 语义，而 PriorityQueue 根据其值对其元素进行排序。

每个通用实现都提供其接口中包含的所有可选操作。所有都允许 null 元素，键和值。都不是同步(线程安全)的。所有都具有 fail-fast iterators (快速失败迭代器)，它在迭代期间检测非法并发修改，并且快速而干净地失败，而不是在未来的未确定时间冒任意、不确定行为的风险。所有都是 Serializable，并且都支持公共 clone 方法。

这些实现是不同步的这一事实代表了对过去的突破：传统集合 Vector 和 Hashtable 是同步的。采用本方法是因为当同步没有任何好处时经常使用集合。这些用途包括单线程使用，只读使用，以及用作进行自身同步的大型数据对象的一部分。一般来说，良好的 API 设计实践不会让用户为他们不使用的功能付费。此外，在某些情况下，不必要的同步可能导致死锁。

如果需要线程安全集合，则 Wrapper Implementations 部分中描述的同步包装器允许将 any (任何) 集合转换为同步集合。因此，同步对于通用实现是可选的，而对于遗留实现是必需的。此外，java.util.concurrent 包提供了 BlockingQueue 接口的并发实现，它继承了 Queue ，以及提供 ConcurrentMap 接口，继承 Map。这些实现提供了比仅仅同步实现更高的并发性。

通常，你应该考虑接口，而不是 实现。这就是本节中没有编程示例的原因。在大多数情况下，实现的选择仅影响性能。Interfaces 部分中提到的首选样式是在创建 Collection 时选择实现，并立即将新集合分配给相应接口类型的变量(或将集合传递给期望接口类型的参数的方法)。通过这种方式，程序不会依赖于给定实现中的任何添加方法，只要性能问题或行为细节保证程序员可以随时更改实现。

以下部分简要讨论了实现。使用诸如 constant-time (常量时间)，log，linear (线性)，n log(n) 和 quadratic (二次的) 等词来描述实现的性能，指的是执行操作的时间复杂度的渐近上界。所有这一切都是绕口的，如果你不知道它意味着什么并不重要。如果你有兴趣了解更多信息，请参阅任何优秀的算法教科书。需要记住的一点是，这种性能指标有其局限性。有时，名义上较慢的实现可能会更快。如有疑问，请测量性能！