Lesson: Implementations

实现是用于存储集合的数据对象，这些对象实现了interface部分中描述的interface。本课描述了以下几种实现：

• 通用实现 是最常用的实现，专为日常使用而设计。它们概括在标题为“通用实现”的表中。

• 特殊用途的实现 设计用于特殊情况，并显示非标准的性能 Feature，使用限制或行为。

• 并发实现 旨在支持高并发性，通常以单线程性能为代价。这些实现是java.util.concurrent程序包的一部分。

• 包装器实现**与其他类型的实现(通常是通用的实现)结合使用，以提供附加功能或受限制的功能。

• 便利实现 是微型实现，通常通过静态工厂方法提供，这些微型实现为特殊集合(例如单例集)的通用实现提供了方便，有效的替代方案。

• 抽象实现 是有助于实现自定义实现的骨架实现，稍后在自定义集合实现部分中进行介绍。这是一个高级主题，并不是特别困难，但是很少有人需要这样做。

下表总结了通用实现。

General-purpose Implementations

Interfaces	哈希表实现	可调整大小的数组实现	Tree Implementations	链表实现	哈希表链接列表实现
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Queue
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap

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

每个通用实现都提供其interface中包含的所有可选操作。所有都允许null个元素，键和值。没有一个被同步(线程安全)。所有这些都具有* fail-fast 迭代器*，这些迭代器可以在迭代过程中检测到非法的并发修改，并且可以快速，干净地失败，而不会在 Future 的不确定时间冒着任意，不确定的行为的风险。都是Serializable，并且都支持公共clone方法。

这些实现不同步的事实表示与过去的突破：遗留集合Vector和Hashtable已同步。之所以采用本方法，是因为在同步没有好处时经常使用集合。这样的用途包括单线程用途，只读用途，以及用作进行自己的同步的较大数据对象的一部分。通常，最好的 API 设计做法是不让用户为不使用的功能付费。此外，在某些情况下，不必要的同步可能导致死锁。

如果需要线程安全的集合，则在Wrapper Implementations部分中描述的同步包装器允许将* any *集合转换为同步集合。因此，同步对于通用实现是可选的，而对于传统实现则是必需的。此外，java.util.concurrent包提供BlockingQueueinterface(扩展Queue)和ConcurrentMapinterface(扩展Map)的并发实现。这些实现比单纯的同步实现提供更高的并发性。

通常，您应该考虑的是interface，而不是实现。这就是为什么本节中没有编程示例的原因。在大多数情况下，实现的选择仅影响性能。如Interfaces部分中所述，首选样式是在创建Collection时选择一种实现，并立即将新集合分配给相应interface类型的变量(或将集合传递给期望参数的方法)。interface类型)。这样，程序就不会依赖于给定实现中添加的任何方法，从而使程序员可以在性能或行为细节得到保证的任何时候自由地更改实现。

以下各节简要讨论了实现。使用诸如* constant-time ， log ， linear ， n log(n)和 quadratic *之类的词来描述实现的性能，以指代时间上的渐近上限执行操作。所有这一切都令人 mouth 舌，如果您不知道这意味着什么，那也没关系。如果您想了解更多信息，请参阅任何优秀的算法教科书。要记住的一件事是，这种性能 Metrics 有其局限性。有时，名义上较慢的实现可能会更快。如有疑问，请评估性能！