路径：集合

课程：自定义集合实现

许多程序员永远不需要实现自己的Collection类。使用本章前面描述的实现可以走得相当远。然而，总有一天你可能想要编写自己的实现。在Java平台提供的抽象实现的帮助下，这相当容易。在讨论如何编写实现之前，让我们先讨论为什么可能想要编写一个实现。

编写实现的原因

以下列表列举了您可能想要实现的自定义Collection的类型。这不是详尽无遗的列表：

持久化：所有内置的Collection实现都存储在主内存中，并在程序退出时消失。如果您希望集合在下次程序启动时仍然存在，可以通过在外部数据库上构建一个薄层来实现。这样的集合可能被多个程序同时访问。
应用程序特定：这是一个非常广泛的类别。一个例子是一个包含实时遥测数据的不可修改的Map。键可以表示位置，值可以通过get操作从这些位置的传感器中读取。
高性能，专用：许多数据结构利用受限使用来提供比通用实现更好的性能。例如，考虑一个包含长时间运行相同元素值的List。这种列表在文本处理中经常出现，可以进行运行长度编码 - 运行可以表示为一个包含重复元素和连续重复次数的单个对象。这个例子很有趣，因为它在性能的两个方面进行了权衡：它所需的空间较少，但比ArrayList花费更多的时间。
高性能，通用：Java集合框架的设计者试图为每个接口提供最佳的通用实现，但是还有许多许多数据结构可以使用，而且每天都有新的数据结构被发明出来。也许你可以想出更快的东西！
增强功能：假设您需要一个高效的袋实现（也称为multiset）：一个Collection，在允许重复元素的同时，提供常量时间的包含性检查。在HashMap之上实现这样一个集合相当简单。
便利：您可能需要额外的实现，提供超出Java平台提供的便利。例如，您可能经常需要表示连续范围的Integer的List实例。
适配器：假设您正在使用具有其自己的特定集合API的旧API。您可以编写一个适配器实现，使这些集合能够在Java集合框架中运行。适配器实现是一层薄薄的包装，将一种类型的对象包装成另一种类型的对象，并通过将对后者类型的操作转换为对前者类型的操作来使它们行为一致。

如何编写自定义实现

编写自定义实现非常简单。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 — 一个既不是Set也不是List的Collection。至少需要提供iterator和size方法。
AbstractSet — 一个Set；使用方式与AbstractCollection相同。
AbstractList — 由随机访问数据存储支持的List，例如数组。至少需要提供positional access方法（get，可选的set，remove和add）以及size方法。抽象类会处理listIterator（和iterator）。
AbstractSequentialList — 由顺序访问数据存储支持的List，例如链表。至少需要提供listIterator和size方法。抽象类会处理位置访问方法。（与AbstractList相反）。
AbstractQueue — 至少需要提供offer，peek，poll和size方法以及支持remove的iterator。
AbstractMap — 一个Map。至少需要提供entrySet视图。通常使用AbstractSet类实现。如果Map是可修改的，则还必须提供put方法。

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

从上述列表中选择适当的抽象实现类。
提供类的所有抽象方法的实现。如果要修改自定义集合，则还必须覆盖一个或多个具体方法。抽象实现类的API文档会告诉您应该覆盖哪些方法。
测试并调试实现。现在您拥有一个可工作的自定义集合实现。
如果您关注性能，请阅读继承的所有方法的抽象实现类的API文档。如果有任何方法看起来太慢，请覆盖它们。如果覆盖了任何方法，请务必在覆盖之前和之后测量方法的性能。您在调整性能方面投入的努力应取决于实现的使用程度以及其使用对性能的关键程度。（通常最好省略此步骤。）