Java 进阶 -- 集合（三）

4、实现

实现是用于存储集合的数据对象，它实现了接口部分中描述的接口。本课描述了以下类型的实现:

• 通用实现是最常用的实现，是为日常使用而设计的。它们在标题为“通用实现”的表格中进行了总结。
• 特殊目的实现是为在特殊情况下使用而设计的，并显示非标准的性能特征、使用限制或行为。
• 并发实现旨在支持高并发性，通常以牺牲单线程性能为代价。这些实现是java.util.concurrent包的一部分。
• Wrapper 实现：与其他类型的实现(通常是通用实现)结合使用，以提供添加的或受限制的功能。
• 便利实现是小型实现，通常通过静态工厂方法提供，它为特殊集合(例如，单例sets)提供方便、高效的通用实现替代方案。
• 抽象实现是便于构建自定义实现的骨架实现——稍后将在自定义集合实现部分进行描述。这是一个高级的话题，不是特别难，但相对来说很少有人需要做。

下表总结了通用实现。

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

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

这些实现是不同步的，这代表了与过去的决裂:遗留集合Vector和Hashtable是同步的。之所以采用目前的方法，是因为在同步没有好处的情况下经常使用集合。这些用途包括单线程使用、只读使用以及作为自己进行同步的较大数据对象的一部分使用。一般来说，不让用户为他们不使用的功能付费是良好的API设计实践。此外，在某些情况下，不必要的同步可能导致死锁。

如果需要线程安全的集合，那么在包装器实现一节中描述的同步包装器允许将任何集合转换为同步集合。因此，同步对于通用实现是可选的，而对于遗留实现是强制的。此外，java.util.concurrent包提供了扩展Queue的BlockingQueue接口和扩展Map的ConcurrentMap接口的并发实现。这些实现比单纯的同步实现提供更高的并发性。

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

接下来的小节将简要讨论这些实现。实现的性能使用诸如常数时间(constant-time)、对数(log)、线性(linear)、nlog(n)和二次(quadratic)等词来描述，以表示执行操作的时间复杂度的渐近上界。所有这些都很拗口，如果你不知道它的意思也没关系。如果你有兴趣了解更多，可以参考任何好的算法教科书。需要记住的一点是，这种性能指标有其局限性。有时，名义上较慢的实现可能更快。当有疑问时，衡量性能!

4.6 Wrapper 实现

包装器（Wrapper）实现将其所有实际工作委托给指定的集合，但在该集合提供的功能之上添加额外的功能。对于设计模式爱好者来说，这是装饰器(decorator)模式的一个示例。虽然这看起来有点奇怪，但实际上非常简单。

这些实现是匿名的;该库不是提供一个公共类，而是提供一个静态工厂方法。所有这些实现都可以在Collections类中找到，该类仅由静态方法组成。

4.6.1 同步包装器

同步包装器向任意集合添加自动同步(线程安全)。六个核心集合接口(Collection、Set、List、Map、SortedSet和SortedMap)中的每一个都有一个静态工厂方法。

// 返回由指定集合支持的同步(线程安全)集合。为了保证串行访问，
// 对backing集合的所有访问都必须通过返回的集合来完成，这一点至关重要。
// 当通过Iterator、Spliterator或Stream遍历返回的集合时，用
// 户必须手动同步返回的集合:Collection c = Collections.synchronizedCollection(myCollection);...synchronized (c) {Iterator i = c.iterator(); // Must be in the synchronized blockwhile (i.hasNext())foo(i.next());}// 不遵循此建议可能会导致不确定的行为。
// 返回的集合不将hashCode和equals操作传递给backing集合，而是依
// 赖于Object的equals和hashCode方法。在backing集合是set或list
// 的情况下，这对于保留这些操作的契约是必要的。
// 如果指定的集合是可序列化的，则返回的集合将是可序列化的。
public static <T> Collection<T> synchronizedCollection(Collection<T> c);
public static <T> Set<T> synchronizedSet(Set<T> s);
public static <T> List<T> synchronizedList(List<T> list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s);
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);

这些方法中的每一个都返回由指定集合的同步(线程安全)Collection 。为了保证串行访问，所有对后备集合的访问都必须通过返回的集合来完成**。保证这一点的简单方法是不保留对后备集合的引用**。使用以下技巧创建同步集合。

List<Type> list = Collections.synchronizedList(new ArrayList<Type>());

以这种方式创建的集合与通常同步的集合(如Vector)一样，都是线程安全的。

面对并发访问，当迭代返回的集合时，用户必须手动同步返回的集合。原因是迭代是通过对集合的多个调用来完成的，这些调用必须组合成单个原子操作。下面是迭代包装器同步集合的习惯用法。

Collection<Type> c = Collections.synchronizedCollection(myCollection);
synchronized(c) {for (Type e : c)foo(e);
}

如果使用显式迭代器，则必须从synchronized 内部调用iterator 方法。不遵循此建议可能会导致不确定性行为。迭代同步Map的Collection视图的习惯用法与此类似。当迭代任何Collection视图时，用户必须在synchronized Map上同步，而不是在Collection视图本身同步，如下面的示例所示。

Map<KeyType, ValType> m = Collections.synchronizedMap(new HashMap<KeyType, ValType>());...
Set<KeyType> s = m.keySet();...
// Synchronizing on m, not s!
synchronized(m) {while (KeyType k : s)foo(k);
}

使用包装器实现的一个小缺点是，您无法执行包装实现的任何非接口(noninterface)操作。因此，例如，在前面的List 示例中，您不能在包装的ArrayList上调用ArrayList's ensureCapacity 操作。

4.6.2 不可变包装器

与同步包装器不同，同步包装器将功能添加到包装的集合中，不可修改的包装器将功能删除。特别是，它们通过拦截所有可能修改集合的操作并抛出UnsupportedOperationException，从而剥夺了修改集合的能力。不可修改的包装有两个主要用途，如下:

• 使集合在构建后不可变。在这种情况下，最好不要维护对后备集合的引用。这绝对保证了不变性。
• 允许某些客户端只读访问您的数据结构。您保留了对backing 集合的引用，但分发了对包装器的引用。通过这种方式，客户端可以查看但不能修改，而您可以保持完全访问权限。

与同步包装器一样，六个核心Collection接口中的每一个都有一个静态工厂方法。

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c);
public static <T> Set<T> unmodifiableSet(Set<? extends T> s);
public static <T> List<T> unmodifiableList(List<? extends T> list);
public static <K,V> Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m);
public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<? extends T> s);
public static <K,V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m);

4.6.3 已检查的接口包装

Collections.checked 接口包装器提供用于泛型集合。这些实现返回指定集合的动态类型安全视图，如果客户端试图添加错误类型的元素，则会抛出ClassCastException。该语言中的泛型机制提供了编译时(静态)类型检查，但也有可能破坏这种机制。动态类型安全视图完全消除了这种可能性。

4.7 便利实现

本节描述几个迷你实现，当您不需要它们的全部功能时，它们比通用实现更方便、更高效。本节中的所有实现都是通过静态工厂方法而不是公共类提供的。

Array的列表视图

Arrays.asList方法返回其数组参数的List 视图。对List的更改贯穿写入数组，反之亦然。集合的大小是数组的大小，不能更改。如果在List上调用add 或remove 方法，则会产生UnsupportedOperationException。

这个实现的正常用途是作为基于数组和基于集合的api之间的桥梁。它允许您将数组传递给期望是Collection或List的方法。然而，这个实现还有另一个用途。如果您需要固定大小的List，那么它比任何通用的List实现都更有效。这就是习语。

List<String> list = Arrays.asList(new String[size]);

注意，不保留对后备数组的引用。

不可变多副本列表

有时，您需要一个由同一元素的多个副本组成的不可变列表。Collections.nCopies方法返回这样一个列表。这个实现有两个主要用途。第一个是初始化新创建的List;例如，假设您想要一个初始包含1,000个null 元素的ArrayList。下面的语句可以达到这个目的。

List<Type> list = new ArrayList<Type>(Collections.nCopies(1000, (Type)null));

当然，每个元素的初始值不必为null。第二个主要用途是增长现有的List。例如，假设您想在List< string >的末尾添加69个字符串“fruit bat”的副本。我不清楚你为什么要做这样的事，但让我们假设你做了。下面是你应该怎么做。

lovablePets.addAll(Collections.nCopies(69, "fruit bat"));

通过使用同时接受索引和Collection的addAll形式，您可以将新元素添加到List的中间而不是末尾。

不可变单例 Set

有时您需要一个不可变的单例 Set(singleton Set)，它由单个指定元素组成。Collections.singleton方法返回这样一个Set。此实现的一个用途是从Collection中删除所有出现的指定元素。

c.removeAll(Collections.singleton(e));

一个相关的习惯用法是从Map中删除映射到指定值的所有元素。例如，假设您有一个Map - job，它将人们映射到他们的工作领域，并且假设您想要消除所有的律师。下面的一行代码将完成这个任务。

job.values().removeAll(Collections.singleton(LAWYER));

此实现的另一个用途是向编写为接受值集合的方法提供单个输入值。

空Set、List和Map 常量

Collections类提供了返回空Set、List和Map的方法——emptySet、emptyList和emptyMap。这些常量的主要用途是作为方法的输入，当您根本不想提供任何值时，这些方法接受值的Collection ，如本例所示。

tourist.declarePurchases(Collections.emptySet());