实现

　　　　实现是用来存储 对象集 的实际数据对象， 它实现了在前面的章节中所描述的 核心 对象集 接口 。以下章节将描述三种实现:

　　通用实现

　　通用实现是公共类，它提供核心对象集接口的主要实现。

　　包装器实现

　　包装器实现与其它实现（通常为通用实现）一起提供附加功能。

　　便利实现

　　便利实现是小型实现，通常可通过静态方法（static factory methods）获得，它可方便、高效地为特殊 对象集 (象 singleton sets)替代通用实现。

　　另外，根据JDK的abstract implementations，你也可以建立自己的实现。这在一个单独的课程中有所描述，因为它属于高级课程。它不是特别难，但相对来讲，需要它的人很少。

　　通用实现

　　如下表格对通用实现做了小结。该表突出显示了它们的正常命名样式：名称均属于 形式, 这里的 是由类实现的核心对象集接口, 而 表示了在该实现底层的数据结构。

　　JDK 1.2 提供了每个接口的两种实现 (Collection是个例外，它没有直接的实现，但可当作其它 对象集 接口的最小公分母). 在每一个接口中，其中一种实现明显的是主实现: 要使用的那个，其它东西是一样的。主实现是 HashSet, ArrayList 和 HashMap. 注意SortedSet和SortedMap接口在上表中没有列出。它们各自都有一个实现，这些实现(TreeSet 和 TreeMap) 被列在 Set 和 Map 栏里。

　　这些实现不仅具有一致的名称，而且还有一致的行为。它们都实现所有的包含在它们的接口中的选项操作（optional operations），都允许 null 元素、键和值。每一种实现都是不同步的。它们都具有快速失效迭代功能, 这可以在迭代过程中检测非法并发更改，并快速彻底地失效，而不是冒在今后不可预知的时间里发生任意不可确定行为的风险。所有的实现都是可序列化的（Serializable）, 并都支持公共 clone 方法。

　　新实现不同步这一事实代表与过去的一个中断：Vector 和 Hashtable 在 JDK 1.2 以前的版本中是同步的。之所以采用新的做法是因为 对象集 经常以一种同步在其中没有益处的方式所使用。这样的使用包括单线程使用、只读使用以及作为一个较大的数据对象（它有它自己的同步）的一部分而使用。通常，API设计的惯例是不让用户为不必要的性能花钱。再者，不必要的同步在某中情况下可能会导致死锁。

　　如果你需要一个同步的 对象集, synchronization wrappers（同步包装器）（将在 下一节介绍）允许任意 对象集 转换为同步对象集。因此，对新的 对象集 实现来说，当它对旧的 对象集 是强制性的时候，同步是可选的。 作为一个经验法则，你应该考虑的是接口，而不是实现。这就是为什么在这一节中没有编程实例的原因。对大部分情况来讲，实现的选择仅影响性能。首选的风格（就象在 接口课程 中所提到的）是在创建一个 对象集 时选择一个实现，并立即将一个新的 对象集 赋值给相应接口类型的一个变量（或将该 对象集 传递给参数为此接口类型的方法）。这样，程序将不会依赖于在一个给定的实现中任意增加的方法, 并给程序员和维护人员以迅速改变实现的自由（如果有关性能允许这样做的话）。

　　下面将简要讨论通用实现。实现的性能的描述使用词汇如 constant, log, linear, n log(n) 和 quadratic等。这些词汇指执行操作的关于时间复杂性（time complexity）的渐进上限（asymptotic upper bound）。 所有这些可够你消化的了，不过如果你不理解，也没太大关系。有兴趣的话可以阅读任意一本算法教科书，那上面有关于这类内容的解释。有一件事是应该牢记的，那就是：这种性能的度量有它的局限性。有时名义上较慢的实现对于你所实际使用大小的对象集来说可能要快。如果有些怀疑，估量一下该性能。

　　Set

　　两个通用Set实现是HashSet 和TreeSet。要决定用哪一个，那是非常简单明了的。 HashSet 要快得多 (对大多数操作是常数时间之于对数时间（constant time vs. log time）), 但不提供排序保证。如果你需要使用 SortedSet 中的操作，或者按顺序迭代对你来说是重要的，那么请使用 TreeSet。 否则，使用 HashSetf 在大多数时间都不使用 HashSet ，对你来说是个公平的赌博。

　　关于 HashSet，有一件事应该牢记，即就条目数和容量之和来讲，迭代是线性的。因此，如果迭代性能很重要，那就应该慎重选择一个适当的初始容量。容量选得太大，既浪费空间，也浪费时间。 默认的初试容量是101, 一般来讲，它比你所需要的要多。可以使用 int 构造函数来指定初始容量。要分配 HashSet 的初始容量为17:

　　Set s= new HashSet(17);

　　HashSets 另有一个称作 装载因数（load factor） 的"调整参数（tuning parameter）" 。如果你非常在乎你的 HashSet 的空间的使用，请阅读 HashSet 文本以获取详细信息。否则，就使用默认值吧。如果你接受默认装载因数，但你确实又想指定初始容量，那么，选一个大约是你期望你的 Set 将增长到的容量的两倍的数。如果你的猜测不着边，它也可以增长，或只是浪费一点空间。但都没有大问题。如果你知道有关正确尺寸的一个最佳值，用它吧；如果不知道，那就使用一个旧的值，或使用一个偶数值。它真的不是非常重要。这些事情只能使 HashSet 稍稍变好一点点。

　　TreeSet 没有调整参数。除 clone 之外，HashSet 和 TreeSet 都仅有那些由它们各自的接口所要求的操作 (Set 和 TreeSet)，而没有任何别的操作。

　　List

　　两个通用List实现是ArrayList和LinkedList。 大部分情况下，你可能使用 ArrayList。 它提供常数时间定位存取，并且非常快。因为它不必为 List 中的每个元素分配一个节点对象，并且当它必须立即移动多个元素时，它可以利用本地方法 System.arraycopy 。 你可将 ArrayList 当作没有同步系统开销的 Vector 。

　　如果你经常添加元素至 List 的开始处，或在 List 上迭代以从其内部删除元素，你可能会考虑使用 LinkedList。这些操作在 LinkedList 中是常数时间，而在 ArrayList 中是线性时间。 但是你付出了很大的代价! 定位存取在 LinkedList 中是线性时间 ，而在 ArrayList 中是常数时间。 进一步讲，LinkedList 的常数因数是非常糟糕的。如果你想要使用一个 LinkedList, 用 LinkedList 和 ArrayList 二者去估量它的性能吧，你可能会有意外的收获。

　　ArrayList 有一个调整参数，即初始容量（initial capacity）. 它是指 ArrayList 在增长前可容纳的元素的数量。关于这一点，没有许多要讲的。List 所不需要的仅有的 ArrayList 操作是 ensureCapacity 和 trimToSize (它改变了过剩的容量), 和 clone。

　　LinkedList 没有调整参数, 但有7个选项操作，其中一个就是clone， 另外6个是 addFirst, getFirst, removeFirst, addLast, getLast, 和 removeLast。 对于它们，我的感觉是复杂的。它们使得将 LinkedList 作为一个队列或一个双端队列(dequeue)来使用这件工作变得简单, 但是它们也使你在发现 ArrayList 更快时很难转换你的表达方法。

　　如果你需要同步，Vector 将稍微快于用Collections.synchronizedList 同步的 ArrayList 。但是 Vector 有早期操作的负担。因此需格外小心，并总是用 List 接口来操纵 Vector ，否则，你会被它缠住的。

　　如果你的 List 的大小是固定的 (也就是说，你不会使用 remove, add 或任何其它出 containsAll 以外的批量操作)，那么你有第三个选择，那肯定是值得考虑的。请看 便利实现(convenience implementations) 一节中的 Arrays.asList。

　　Map

　　两个通用Map实现是HashMap 和TreeMap . Map 的情况与 Set 完全对等。如果你需要 SortedMap 操作或顺序 Collection视图迭代，去找 TreeMap 吧，或者去找 HashMap。 在 Set 章节 中的其它一切都适用于 Map，所以去重新阅读它们吧。

　　完整性要求我们提一下Hashtable。 象 Vector 和 ArrayList 一样，如果你需要同步，Hashtable 将稍微快于用Collections.synchronizedMap 同步的 HashMap 。再有， Hashtable 也有早期操作的负担。 因此需格外小心，并总是用 Map 接口来操纵它， 否则，你会被它缠住的。