Урок: Пользовательские Реализации Набора

Много программистов никогда не должны будут реализовывать свое собственное Collections классы. Можно пойти довольно далекое использование реализаций, описанных в предыдущих разделах этой главы. Однако, когда-нибудь Вы могли бы хотеть записать свою собственную реализацию. Довольно легко сделать это при помощи абстрактных реализаций, обеспеченных платформой Java. Прежде, чем мы обсудим, как записать реализацию, давайте обсуждать, почему Вы могли бы хотеть записать тот.

Причины Записать Реализацию

Следующий список иллюстрирует вид пользовательских Collections Вы мог бы хотеть реализовать. Это не предназначается, чтобы быть исчерпывающим:

• Персистентный: Все встроенные Collection реализации находятся в оперативной памяти и исчезают, когда программа выходит. Если Вы хотите набор, который будет все еще присутствовать в следующий раз, когда программа запускается, можно реализовать ее, создавая фанеру по внешней базе данных. Такой набор мог бы быть одновременно доступным многократными программами.
• Специализированный: Это - очень широкая категория. Одним примером является неподдающееся изменению Map содержа телеметрические данные в реальном времени. Ключи могли представить расположения, и значения могли быть считаны из датчиков в этих расположениях в ответ на get работа.
• Высокоэффективный, специального назначения: Много структур данных используют в своих интересах ограниченное использование, чтобы предложить лучшую производительность, чем возможно с реализациями общего назначения. Например, рассмотрите a List содержа долгие выполнения идентичных значений элемента. Такие списки, которые часто происходят в обработке текста, могут быть длиной до выполнения закодированный — выполнения могут быть представлены как единственный объект, содержащий повторный элемент и число последовательных повторений. Этот пример интересен, потому что он балансирует между двумя аспектами производительности: требуется меньше пространства, но больше времени чем ArrayList.
• Высокоэффективный, общего назначения: разработчики Платформы Наборов Java попытались обеспечить лучшие реализации общего назначения для каждого интерфейса, но многие, много структур данных, возможно, использовались, и новые изобретаются каждый день. Возможно можно придумать что-то быстрее!
• Улучшенная функциональность: Предположите, что Вы нуждаетесь в эффективной реализации сумки (также известный как мультимножество): a Collection это предлагает постоянно-разовые проверки включения, позволяя двойные элементы. Это разумно прямо, чтобы реализовать такой набор на a HashMap.
• Удобство: можно хотеть дополнительные реализации, которые предлагают удобства вне предлагаемых платформой Java. Например, Вам, возможно, часто понадобится List экземпляры, представляющие непрерывный диапазон Integers.
• Адаптер: Предположите, что Вы используете 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. В интересах полного раскрытия немного более трудно использовать другие абстрактные реализации, потому что необходимо записать свой собственный iterator, но это все еще не настолько трудно.

Следующий список суммирует абстрактные реализации:

• AbstractCollection — a Collection это ни один не a Set ни a List. Как минимум следует обеспечить iterator и size методы.
• AbstractSet — a Set; использование идентично AbstractCollection.
• AbstractList — a List поддержанный хранилищем данных произвольного доступа, таким как массив. Как минимум следует обеспечить positional access методы (get и, дополнительно, set, remove, и add) и size метод. Абстрактный class заботится о listIterator (и iterator).
• AbstractSequentialList — a List поддержанный с последовательным доступом хранилищем данных, таким как связанный список. Как минимум следует обеспечить listIterator и size методы. Абстрактный class заботится о позиционных методах доступа. (Это - противоположность AbstractList.)
• AbstractQueue — как минимум следует обеспечить offer, peek, poll, и size методы и iterator поддержка remove.
• AbstractMap — a Map. Как минимум следует обеспечить entrySet представление. Это обычно реализуется с AbstractSet class. Если Map является поддающимся изменению, следует также обеспечить put метод.

Процесс записи пользовательской реализации следует:

1. Выберите соответствующую абстрактную реализацию class из предыдущего списка.
2. Обеспечьте реализации для всех абстрактных методов class. Если Ваш пользовательский набор должен быть поддающимся изменению, необходимо переопределить один или больше конкретных методов также. Документация API для абстрактной реализации class скажет Вам который методы переопределить.
3. Тест и, в случае необходимости, отлаживает реализацию. У Вас теперь есть рабочая пользовательская реализация набора.
4. Если Вы обеспокоены производительностью, считайте документацию API абстрактной реализации class для всех методов, реализации которых Вы наследовали. Если кто-либо кажется слишком медленным, переопределяет их. Если Вы переопределяете какие-либо методы, убедитесь, что определили эксплуатационные качества метода прежде и после переопределения. То, сколько усилий Вы прикладываете к тонкой настройке производительности, должно быть функцией того, сколько использования реализация доберется и насколько критический к производительности ее использование. (Часто этот шаг лучше всего опускается.)