集合 - 自定义集合实现 - 《Java™教程（中文）》

编写实现的原因
如何编写自定义实现

许多程序员永远不需要实现自己Collection的类。您可以使用本章前面各节中描述的实现进行深入研究。但是，有一天您可能想编写自己的实现。借助于Java平台提供的抽象实现，这样做非常容易。在讨论如何编写实现之前，让我们讨论为什么要编写实现。

编写实现的原因

以下列表说明了您可能要实现的自定义Collection种类。它并非旨在详尽无遗：

持久性：所有内置Collection实现都驻留在主内存中，并且在程序退出时消失。如果您希望在下次程序启动时仍然存在一个集合，则可以通过在外部数据库上构建单板来实现它。这样的集合可以被多个程序同时访问。
特定于应用程序：这是一个非常广泛的类别。一个示例是不可修改的Map包含实时遥测数据。键可以代表位置，并且可以响应于get操作从这些位置处的传感器读取值。
高性能，专用：许多数据结构利用受限的使用来提供比通用实现更好的性能。例如，考虑List包含长期运行的相同元素值。这样的列表（在文本处理中经常出现）可以进行游程长度编码 - 游程可以表示为包含重复元素和连续重复次数的单个对象。这个示例很有趣，因为它需要权衡两个方面的性能：与ArrayList相比，它需要更少的空间，但需要更多的时间。
高性能，通用：Java Collections Framework的设计人员试图为每个接口提供最佳的通用实现，但是可以使用很多很多数据结构，并且每天都在发明新的数据结构。也许您可以更快地提出一些建议！
增强的功能：假设您需要一种有效的bag实施方式（也称为multiset）：Collection它提供了恒定时间的容纳检查，同时允许重复的元素。在HashMap上面实现这样的集合是相当直接的。
便利性：您可能需要其他实现，这些实现除了Java平台提供的便利之外，还提供其他便利。例如，您可能经常需要代表连续范围Integers的List实例。
适配器：假设您使用的是具有自己专用集合API的旧版API。您可以编写适配器实现，以允许这些集合在Java Collections Framework中运行。一个适配器实现是很薄的木皮，它包装一个类型的对象，使他们通过在后一种类型转换操作到对前操作的行为像其他类型的对象。
如何编写自定义实现
编写自定义实现非常容易。Java Collections Framework提供了专门设计用于促进自定义实现的抽象实现。我们将从以下实现Arrays.asList的示例开始。 ```java public static List asList(T[] a) { return new MyArrayList(a); }

private static class MyArrayList extends AbstractList {

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`，批量操作，搜索操作，哈希码计算，比较和字符串表示。<br />假设您想使实现更快一些。抽象实现的API文档精确描述了每种方法的实现方式，因此您将知道要重写哪些方法才能获得所需的性能。前面的实现的性能很好，但是可以改进一点。特别地，`toArray`方法遍历`List`，一次复制一个元素。有了内部表示形式，仅克隆数组就会更快，更明智。
```java
public Object[] toArray() {
    return (Object[]) a.clone();
}

加上此替代项和其他类似的替代项，此实现恰恰是java.util.Arrays中的实现。为了完全公开，使用其他抽象实现会有些困难，因为您将不得不编写自己的迭代器，但是仍然没有那么困难。
以下列表总结了抽象的实现：

AbstractCollection— Collection既不是Set也不是List。至少必须提供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方法以及iterator支持remove。
AbstractMap—一个Map。至少您必须提供entrySet视图。通常使用AbstractSet类来实现。如果Map可以修改，则还必须提供put方法。

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

从前面的列表中选择适当的抽象实现类。
提供该类的所有抽象方法的实现。如果您的自定义集合是可修改的，则您还必须重写一种或多种具体方法。抽象实现类的API文档将告诉您要重写哪些方法。
测试并在必要时调试实现。您现在有了一个有效的自定义集合实现。
如果您担心性能，请阅读抽象实现类的API文档，以了解要继承其实现的所有方法。如果看似太慢，则重写它们。如果重写任何方法，请确保在重写前后测量该方法的性能。您需要花多少精力来调整性能，这取决于实现将获得多少使用以及其使用对性能的重要性。（通常最好省略此步骤。）

自定义集合实现

编写实现的原因

如何编写自定义实现