Lesson: Custom Collection Implementations课程：自定义集合实现

Many programmers will never need to implement their own Collections classes. 许多程序员永远不需要实现自己的Collection类。You can go pretty far using the implementations described in the preceding sections of this chapter. 使用本章前面几节中描述的实现，您可以走得更远。However, someday you might want to write your own implementation. 然而，有一天您可能会想编写自己的实现。It is fairly easy to do this with the aid of the abstract implementations provided by the Java platform. 借助Java平台提供的抽象实现，实现这一点相当容易。Before we discuss how to write an implementation, let's discuss why you might want to write one.在讨论如何编写实现之前，让我们先讨论一下为什么要编写一个实现。

Reasons to Write an Implementation编写实现的原因

The following list illustrates the sort of custom Collections you might want to implement. 下面的列表说明了您可能想要实现的自定义Collection的种类。It is not intended to be exhaustive:其目的并非详尽无遗：

• Persistent持久的: All of the built-in Collection implementations reside in main memory and vanish when the program exits. ：所有内置的Collection实现都驻留在主内存中，并在程序退出时消失。If you want a collection that will still be present the next time the program starts, you can implement it by building a veneer over an external database. 如果希望在下次程序启动时仍然存在一个集合，可以通过在外部数据库上构建一个面板来实现它。Such a collection might be concurrently accessible by multiple programs.这样的集合可以由多个程序同时访问。
• Application-specific特定于应用程序: This is a very broad category. ：这是一个非常广泛的类别。One example is an unmodifiable Map containing real-time telemetry data. 一个例子是包含实时遥测数据的不可修改Map。The keys could represent locations, and the values could be read from sensors at these locations in response to the get operation.这些键可以代表位置，可以从这些位置的传感器读取值，以响应get操作。
• High-performance, special-purpose高性能、特殊用途: Many data structures take advantage of restricted usage to offer better performance than is possible with general-purpose implementations. ：许多数据结构利用受限使用提供比通用实现更好的性能。For instance, consider a List containing long runs of identical element values. 例如，考虑一个包含相同元素值的长行程的List。Such lists, which occur frequently in text processing, can be run-length encoded — runs can be represented as a single object containing the repeated element and the number of consecutive repetitions. 这种列表在文本处理中经常出现，可以进行游程编码#151;运行可以表示为包含重复元素和连续重复次数的单个对象。This example is interesting because it trades off two aspects of performance: It requires less space but more time than an ArrayList.这个例子很有趣，因为它权衡了性能的两个方面：它比ArrayList需要更少的空间，但需要更多的时间。
• High-performance, general-purpose高性能、通用型: The Java Collections Framework's designers tried to provide the best general-purpose implementations for each interface, but many, many data structures could have been used, and new ones are invented every day. ：Java集合框架的设计者试图为每个接口提供最好的通用实现，但可能已经使用了很多很多数据结构，而且每天都会发明新的数据结构。Maybe you can come up with something faster!也许你能想出更快的办法！
• Enhanced functionality增强的功能: Suppose you need an efficient bag implementation (also known as a multiset): a Collection that offers constant-time containment checks while allowing duplicate elements. ：假设您需要一个高效的bag实现（也称为multiset）：一个集合，提供恒定时间的安全壳检查，同时允许重复元素。It's reasonably straightforward to implement such a collection atop a HashMap.在HashMap上实现这样一个集合相当简单。
• Convenience方便: You may want additional implementations that offer conveniences beyond those offered by the Java platform. ：除了Java平台提供的方便之外，您可能还需要其他实现。For instance, you may frequently need List instances representing a contiguous range of Integers.例如，您可能经常需要表示连续Integer范围的List实例。
• Adapter适配器: Suppose you are using a legacy API that has its own ad hoc collections' API. ：假设您使用的是一个旧API，它有自己的特殊集合API。You can write an adapter implementation that permits these collections to operate in the Java Collections Framework. 您可以编写一个适配器实现，允许这些集合在Java集合框架中运行。An adapter implementation is a thin veneer that wraps objects of one type and makes them behave like objects of another type by translating operations on the latter type into operations on the former.适配器实现是一种薄饰板，它包裹一种类型的对象，并通过将后一种类型的操作转换为前一种类型的操作，使它们的行为类似于另一种类型的对象。

How to Write a Custom Implementation如何编写自定义实现

Writing a custom implementation is surprisingly easy. 编写自定义实现非常简单。The Java Collections Framework provides abstract implementations designed expressly to facilitate custom implementations. Java 集合框架提供了抽象实现，这些抽象实现是专门为方便定制实现而设计的。We'll start with the following example of an implementation of Arrays.asList.我们将从以下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;
    }
}

Believe it or not, this is very close to the implementation that is contained in java.util.Arrays. 信不信由你，这与java.util.Arrays中包含的实现非常接近。It's that simple! 就这么简单！You provide a constructor and the get, set, and size methods, and AbstractList does all the rest. 您提供了一个构造函数以及get、set和size方法，而AbstractList完成了所有其余的工作。You get the ListIterator, bulk operations, search operations, hash code computation, comparison, and string representation for free.您可以免费获得ListIterator、批量操作、搜索操作、哈希代码计算、比较和字符串表示。

Suppose you want to make the implementation a bit faster. 假设您想让实现更快一点。The API documentation for abstract implementations describes precisely how each method is implemented, so you'll know which methods to override to get the performance you want. 抽象实现的API文档精确地描述了每个方法的实现方式，因此您将知道要覆盖哪些方法以获得所需的性能。The preceding implementation's performance is fine, but it can be improved a bit. 前面的实现的性能很好，但可以稍微改进一下。In particular, the toArray method iterates over the List, copying one element at a time. 特别是，toArray方法在List上迭代，一次复制一个元素。Given the internal representation, it's a lot faster and more sensible just to clone the array.考虑到内部表示，仅克隆阵列就更快、更合理。

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

With the addition of this override and a few more like it, this implementation is exactly the one found in java.util.Arrays. 加上这个覆盖和其他一些类似的功能，这个实现就是java.util.Arrays中的实现。In the interest of full disclosure, it's a bit tougher to use the other abstract implementations because you will have to write your own iterator, but it's still not that difficult.为了充分公开，使用其他抽象实现有点困难，因为您必须编写自己的迭代器，但仍然没有那么困难。

The following list summarizes the abstract implementations:以下列表总结了抽象实现：

• AbstractCollection — a Collection that is neither a Set nor a List. At a minimum, you must provide the iterator and the size methods.
• AbstractSet — a Set; use is identical to AbstractCollection.
• AbstractList — a List backed up by a random-access data store, such as an array. At a minimum, you must provide the positional access methods (get and, optionally, set, remove, and add) and the size method. The abstract class takes care of listIterator (and iterator).
• AbstractSequentialList — a List backed up by a sequential-access data store, such as a linked list. At a minimum, you must provide the listIterator and size methods. The abstract class takes care of the positional access methods. (This is the opposite of AbstractList.)
• AbstractQueue — at a minimum, you must provide the offer, peek, poll, and size methods and an iterator supporting remove.
• AbstractMap — a Map. At a minimum you must provide the entrySet view. This is typically implemented with the AbstractSet class. If the Map is modifiable, you must also provide the put method.

The process of writing a custom implementation follows:编写自定义实现的过程如下所示：

1. Choose the appropriate abstract implementation class from the preceding list.从前面的列表中选择适当的抽象实现类。
2. Provide implementations for all the abstract methods of the class. If your custom collection is to be modifiable, you will have to override one or more of the concrete methods as well. 为类的所有抽象方法提供实现。如果要修改自定义集合，还必须重写一个或多个具体方法。The API documentation for the abstract implementation class will tell you which methods to override.抽象实现类的API文档将告诉您要覆盖哪些方法。
3. Test and, if necessary, debug the implementation. 测试并在必要时调试实现。You now have a working custom collection implementation.现在，您有了一个工作的自定义集合实现。
4. If you are concerned about performance, read the API documentation of the abstract implementation class for all the methods whose implementations you're inheriting. 如果您关心性能，请阅读抽象实现类的API文档，了解您要继承其实现的所有方法。If any seem too slow, override them. 如果其中任何一个看起来太慢，请覆盖它们。If you override any methods, be sure to measure the performance of the method before and after the override. 如果重写任何方法，请确保在重写之前和之后测量该方法的性能。How much effort you put into tweaking performance should be a function of how much use the implementation will get and how critical to performance its use is. 您在调整性能方面投入了多少精力，应该取决于实现将得到多少使用，以及使用它对性能的重要性。(Often this step is best omitted.)（通常这一步最好省略。）