课程: 实现

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

• 通用实现是最常用的实现，设计用于日常使用。在标题为“通用实现”的表中进行了总结。
• 特殊实现设计用于特殊情况，并显示非标准的性能特征、使用限制或行为。
• 并发实现设计为支持高并发性能，通常以牺牲单线程性能为代价。这些实现是java.util.concurrent包的一部分。
• 包装实现与其他类型的实现（通常是通用实现）结合使用，以提供额外的或受限的功能。
• 便利实现是迷你实现，通常通过静态工厂方法提供方便、高效的替代通用实现，用于特殊集合（例如，单例集）。
• 抽象实现是骨架实现，用于方便构建自定义实现，后面在自定义集合实现部分进行描述。这是一个高级话题，虽然不是特别困难，但相对而言只有少数人会需要。

通用实现在下表中进行了总结。

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

每个通用的实现都提供其接口中包含的所有可选操作。所有都允许 null 元素、键和值。没有进行同步（线程安全）。所有都具有快速失败的迭代器，在迭代过程中检测到非法并发修改时会快速、干净地失败，而不会冒着在未来的某个不确定的时间出现任意、非确定性行为的风险。所有都是可序列化的，并且都支持公共的 clone 方法。

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

如果您需要线程安全的集合，可以使用在包装器实现部分中介绍的同步包装器将任何集合转换为同步集合。因此，对于通用实现，同步是可选的，而对于旧实现则是强制的。此外，java.util.concurrent包提供了BlockingQueue接口的并发实现，该接口扩展了Queue，以及ConcurrentMap接口的并发实现，该接口扩展了Map。这些实现比纯粹的同步实现提供了更高的并发性。

通常情况下，您应该考虑接口，而不是实现。这就是为什么本节中没有编程示例的原因。在大多数情况下，实现的选择只影响性能。如接口部分所述，首选的风格是在创建Collection时选择一个实现，并将新的集合立即分配给相应接口类型的变量（或将集合传递给期望接口类型参数的方法）。通过这种方式，程序不会依赖于给定实现中的任何新增方法，使程序员可以自由地根据性能问题或行为细节的需要随时更改实现。

接下来的章节简要讨论了这些实现。对于实现的性能，使用常数时间、对数、线性、n log(n)和平方等词来描述操作的渐近上限时间复杂度。这些内容可能有些晦涩，如果您不了解它的含义也没关系。如果您对此有兴趣，可以参考任何一本优秀的算法教材。需要记住的一点是，这种性能指标有其局限性。有时，名义上更慢的实现可能更快。如果有疑问，可以测量性能！