Lesson: Implementations课程：实现

Implementations are the data objects used to store collections, which implement the interfaces described in the Interfaces section. 实现是用于存储集合的数据对象，这些集合实现了接口部分中描述的接口。This lesson describes the following kinds of implementations:本课程介绍了以下几种实现：

• General-purpose implementations are the most commonly used implementations, designed for everyday use. 通用实现是最常用的实现，是为日常使用而设计的。They are summarized in the table titled General-purpose-implementations.在标题为“通用实现”的表格中对它们进行了总结。
• Special-purpose implementations are designed for use in special situations and display nonstandard performance characteristics, usage restrictions, or behavior.特殊用途的实现是为在特殊情况下使用而设计的，并显示非标准的性能特征、使用限制或行为。
• Concurrent implementations are designed to support high concurrency, typically at the expense of single-threaded performance. 并发实现旨在支持高并发性，通常以牺牲单线程性能为代价。These implementations are part of the java.util.concurrent package.这些实现是java.util.concurrent包的一部分。
• Wrapper implementations are used in combination with other types of implementations, often the general-purpose ones, to provide added or restricted functionality.包装器实现与其他类型的实现（通常是通用实现）结合使用，以提供附加的或受限的功能。
• Convenience implementations are mini-implementations, typically made available via static factory methods, that provide convenient, efficient alternatives to general-purpose implementations for special collections (for example, singleton sets).便利实现是小型实现，通常通过静态工厂方法提供，为特殊集合（例如，单例集合）的通用实现提供方便、高效的替代方案。
• Abstract implementations are skeletal implementations that facilitate the construction of custom implementations — described later in the Custom Collection Implementations section. 抽象实现是有助于构建定制实现的框架实现—稍后将在“自定义集合实现”一节中介绍。An advanced topic, it's not particularly difficult, but relatively few people will need to do it.这是一个高级主题，并不特别困难，但需要做的人相对较少。

The general-purpose implementations are summarized in the following table.下表总结了通用实现。

As you can see from the table, the Java Collections Framework provides several general-purpose implementations of the Set, List , and Map interfaces. 从表中可以看出，Java Collections框架提供了Set、List和Map接口的几种通用实现。In each case, one implementation — HashSet, ArrayList, and HashMap — is clearly the one to use for most applications, all other things being equal. 在每种情况下，一个实现—HashSet、ArrayList和HashMap—显然，在所有其他条件相同的情况下，它适用于大多数应用程序。Note that the SortedSet and the SortedMap interfaces do not have rows in the table. 请注意，SortedSet和SortedMap接口在表中没有行。Each of those interfaces has one implementation (TreeSet and TreeMap) and is listed in the Set and the Map rows. 每个接口都有一个实现（(TreeSet和TreeMap），并在集合和映射行中列出。There are two general-purpose Queue implementations — LinkedList, which is also a List implementation, and PriorityQueue, which is omitted from the table. 有两种通用Queue实现—LinkedList也是一个List实现，PriorityQueue则从表中省略。These two implementations provide very different semantics: LinkedList provides FIFO semantics, while PriorityQueue orders its elements according to their values.这两种实现提供了非常不同的语义：LinkedList提供FIFO语义，而PriorityQueue根据元素的值对其元素进行排序。

Each of the general-purpose implementations provides all optional operations contained in its interface. 每个通用实现都提供其接口中包含的所有可选操作。All permit null elements, keys, and values. 所有这些都允许null元素、键和值。None are synchronized (thread-safe). 没有一个是同步的（线程安全的）。All have fail-fast iterators, which detect illegal concurrent modification during iteration and fail quickly and cleanly rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. 它们都有快速失效的迭代器，可以在迭代过程中检测到非法的并发修改，并快速、干净地失效，而不是在未来的不确定时间冒着任意、不确定性行为的风险。All are Serializable and all support a public clone method.它们都是Serializable（可序列化的），都支持公共clone方法。

The fact that these implementations are unsynchronized represents a break with the past: The legacy collections Vector and Hashtable are synchronized. 这些实现是不同步的，这代表着与过去的决裂：遗留集合Vector和Hashtable是同步的。The present approach was taken because collections are frequently used when the synchronization is of no benefit. 之所以采用目前的方法，是因为在同步毫无益处的情况下经常使用集合。Such uses include single-threaded use, read-only use, and use as part of a larger data object that does its own synchronization. 这类使用包括单线程使用、只读使用，以及作为更大的数据对象的一部分使用，该数据对象自行进行同步。In general, it is good API design practice not to make users pay for a feature they don't use. 一般来说，不让用户为他们不使用的功能付费是良好的API设计实践。Furthermore, unnecessary synchronization can result in deadlock under certain circumstances.此外，在某些情况下，不必要的同步可能会导致死锁。

If you need thread-safe collections, the synchronization wrappers, described in the Wrapper Implementations section, allow any collection to be transformed into a synchronized collection. 如果需要线程安全的集合，那么包装器实现部分中描述的同步包装器允许将任何集合转换为同步集合。Thus, synchronization is optional for general-purpose implementations, whereas it is mandatory for legacy implementations. 因此，同步对于通用实现是可选的，而对于遗留实现是强制性的。Moreover, the java.util.concurrent package provides concurrent implementations of the BlockingQueue interface, which extends Queue, and of the ConcurrentMap interface, which extends Map. 此外，java.util.concurrent包提供了BlockingQueue接口和ConcurrentMap接口的并发实现，前者扩展了队列，后者扩展了映射。These implementations offer much higher concurrency than mere synchronized implementations.这些实现比单纯的同步实现提供了更高的并发性。

As a rule, you should be thinking about the interfaces, not the implementations. 通常，您应该考虑接口，而不是实现。That is why there are no programming examples in this section. 这就是为什么本节中没有编程示例的原因。For the most part, the choice of implementation affects only performance. 在大多数情况下，实现的选择只影响性能。The preferred style, as mentioned in the Interfaces section, is to choose an implementation when a Collection is created and to immediately assign the new collection to a variable of the corresponding interface type (or to pass the collection to a method expecting an argument of the interface type). 如接口部分所述，首选的样式是在创建Collection时选择一个实现，并立即将新集合分配给相应接口类型的变量（或将集合传递给需要接口类型参数的方法）。In this way, the program does not become dependent on any added methods in a given implementation, leaving the programmer free to change implementations anytime that it is warranted by performance concerns or behavioral details.通过这种方式，程序不会依赖于给定实现中添加的任何方法，让程序员可以随时根据性能问题或行为细节更改实现。

The sections that follow briefly discuss the implementations. 接下来的几节将简要讨论这些实现。The performance of the implementations is described using words such as constant-time, log, linear, n log(n), and quadratic to refer to the asymptotic upper-bound on the time complexity of performing the operation. 使用诸如常数时间、对数、线性、n log(n)和二次等词来描述实现的性能，以表示执行操作的时间复杂度的渐近上界。All this is quite a mouthful, and it doesn't matter much if you don't know what it means. 所有这些都是满嘴的，如果你不知道这意味着什么，那也没什么大不了的。If you're interested in knowing more, refer to any good algorithms textbook. One thing to keep in mind is that this sort of performance metric has its limitations. Sometimes, the nominally slower implementation may be faster. 如果你想了解更多，可以参考任何好的算法教科书。需要记住的一点是，这种性能指标有其局限性。有时，名义上较慢的实现可能更快。When in doubt, measure the performance!如果有疑问，请衡量绩效！