Trail: Collections

课程：自定义集合实现

许多程序员永远不需要实现自己的 Collection 类。你可以使用本章前面部分中描述的实现进行相当久的操作。但是，有一天你可能想编写自己的实现。借助 Java 平台提供的抽象实现，这很容易做到这一点。在我们讨论如何编写实现之前，让我们讨论一下为什么要编写一个实现。

编写实现的原因

以下列表说明了你可能希望实现的自定义 Collection 的类型。它并非详尽无遗：

持久：所有内置的 Collection 实现都驻留在主内存中，并在程序退出时消失。如果你希望下次程序启动时仍然存在的集合，你可以通过在外部数据库上构建胶合代码来实现它。这样的集合可以由多个程序同时访问。
特定于应用程序：这是一个非常广泛的类别。一个例子是包含实时遥测数据的不可修改的 Map。键可以表示位置，并且可以响应 get 操作从这些位置处的传感器读取值。
高性能，专用：许多数据结构利用受限制的使用来提供比通用实现更好的性能。例如，考虑一个包含长的连续相同元素的 List。这种在文本处理中经常出现的列表可以是 run-length encoded (游程编码)。run 可以表示为包含重复元素和连续重复次数的单个对象。这个例子很有意思，因为它会影响性能的两个方面：它比 ArrayList 需要更少的空间但更多的时间。
高性能，通用：Java 集合框架的设计人员试图为每个接口提供最佳的通用实现，但是可以使用很多很多数据结构，并且每天都发明新的数据结构。也许你能想出更快的算法！
增强功能：假设你需要一个高效的包实现(也称为 multiset)：即一个 Collection 在允许重复元素的同时提供包含检查的常量时间。在 HashMap 上实现这样的集合是相当简单的。
便利：你可能希望获得除 Java 平台提供的便利之外的其他实现。例如，你可能经常需要 List 实例来表示连续范围的 Integer。
适配器：假设你使用的是具有自己的专用的集合 API 的旧 API。你可以编写一个适配器实现，允许这些集合在 Java 集合框架中运行。adapter implementation (适配器实现) 是一个精简单板，它包装一种类型的对象，并通过将后一种类型的操作转换为前者的操作，使它们的行为类似于另一种类型的对象。

如何编写自定义实现

编写自定义实现非常简单。Java 集合框架提供了明确设计的抽象实现，以方便自定义实现。我们将从以下 Arrays.asList 的实现示例开始。

public static <T> List<T> asList(T[] a) {
    return new MyArrayList<T>(a);
}

private static class MyArrayList<T> extends AbstractList<T> {

    private final T[] a;

    MyArrayList(T[] array) {
        a = array;
    }

    public T get(int index) {
        return a[index];
    }

    public T set(int index, T element) {
        T oldValue = a[index];
        a[index] = element;
        return oldValue;
    }

    public int size() {
        return a.length;
    }
}

信不信由你，这非常接近 java.util.Arrays 中包含的实现。就这么简单！你提供构造函数和 get，set 和 size 方法，AbstractList 完成其余所有操作。你可以免费获得 ListIterator，批量操作，搜索操作，哈希码计算，比较和字符串表示。

假设你希望实现更快一点。抽象实现的 API 文档精确描述了每个方法的实现方式，因此你将知道要覆盖哪些方法以获得所需的性能。前面的实现的性能很好，但可以稍微改进一下。特别是，toArray 方法遍历 List，一次复制一个元素。鉴于内部表示，克隆数组的速度更快，更明智。

public Object[] toArray() {
    return (Object[]) a.clone();
}

通过添加此覆盖以及更多类似覆盖，此实现正是 java.util.Arrays 中的实现。为了完全公开，使用其他抽象实现有点困难，因为你必须编写自己的迭代器，但它仍然不是那么困难。

以下列表总结了抽象实现：

AbstractCollection Collection 既不是 Set 也不是 List。至少，你必须提供 iterator 和 size 方法。
AbstractSet Set; 使用与 AbstractCollection 相同。
AbstractList List 由随机访问数据存储(例如数组)支持。至少，你必须提供 位置访问 方法(get，并且，可选地，set，remove，以及 add)和 size 方法。抽象类负责 listIterator(和 iterator)。
AbstractSequentialList List，由顺序访问数据存储(例如链表)支持。你必须至少提供 listIterator 和 size 方法。抽象类负责位置访问方法。(这与 AbstractList 相反。)
AbstractQueue 至少，你必须提供 offer，peek，poll 和 size 方法以及 iterator 支持 remove。
AbstractMap Map。你至少必须提供 entrySet 视图。这通常使用 AbstractSet 类实现。如果 Map 是可修改的，则还必须提供 put 方法。

编写自定义实现的过程如下：

从前面的列表中选择适当的抽象实现类。
为类的所有抽象方法提供实现。如果你的自定义集合是可修改的，则还必须覆盖一个或多个具体方法。抽象实现类的 API 文档将告诉你要覆盖哪些方法。
测试并在必要时调试实现。你现在有一个可用的自定义集合实现。
如果你担心性能，请阅读你继承其实现的所有方法的抽象实现类的 API 文档。如果有任何看起来太慢，请覆盖它们。如果覆盖任何方法，请确保在覆盖之前和之后测量方法的性能。你在调整性能方面付出的努力应该取决于实现将获得多少使用以及对其使用性能的关键程度。(通常最好省略此步骤。)