Главная » Java » Создание реализаций коллекций

0

 

 Принимаясь за новый проект, вы наверняка сможете отыскать хотя бы одну реализацию коллекций, которая способна удовлетворить условиям текущей за-Дачи. Если же ни один из существующих классов по каким-либо причинам вас е Устраивает, можно реализовать подходящий интерфейс самостоятельно.

1 отовые эскизные реализации коллекций предлагаются стандартными абст-Рактньши    классами    AbstractedСollection, AbstractSet, AbstractList, AbstractSequentialList и AbstractMap. При необходимости создания новых лассов коллекций зачастую проще и удобнее в качестве базового типа выбрать абстрактный класс, нежели интерфейс.

     Абстрактные классы коллекций спроектированы таким образом, чтобы служить удобной базой для наследования при реализации конкретных типов. Впрочем, от вас никто не требует обязательного расширения абстрактных классов — вы вольны строить новый класс на основе подходящего интерфейса, и в некоторых ситуациях подобное решение может оказаться вполне оправданным и работоспособным.

   В составе каждого абстрактного класса определено несколько абстрактных методов, которые используются в реализациях других методов того же класса, предлагаемых по умолчанию. Например, объявление класса AbstractList содержит два абстрактных метода, size и get, и с их использованием реализованы все другие методы-запросы класса AbstractList, включая и те, которые связаны с итерацией. Методы, не помеченные как abstract, нуждаются в пересмотре реализации только в тех случаях, когда необходимо повысить эффективность их работы либо обеспечить выполнение таких действий, которые не предусмотрены в реализации, предлагаемой по умолчанию. Если, например, новый класс, расширяющий AbstractList, должен поддерживать средства изменения содержимого элементов списка, следует переопределить метод set, который по умолчанию просто выбрасывает исключение типа UnsupportedOperationException.

   В    основе    иерархии    абстрактных    типов     коллекций    находится    класс AbstractCollection. Если вам необходима некая коллекция, которая не является ни множеством (set), ни списком (list) и ни набором соответствий (тар)» вполне резонно взять за основу класс AbstractCollection и попытаться расширить его непосредственно. В противном случае, вероятно, более эффективн окажется решение, построенное на базе одного из частных абстрактных клаесо коллекций.

   Если создаваемый класс Collection отвечает коллекции, не поддерживают операций внесения изменений (т.е. методы, связанные с операциями модификаД обязаны выбрасывать исключение типа UnsupportedOperationException), класс, производный от AbstractCollection, должен всего лишь обеспечить реализацию методов size и iterator. Если же коллекция допускает модификацию, придется, помимо того, переопределить исходную реализацию метода add (тот по умолчанию также выбрасывает исключение UnsupportedOperationException) и учесть, что итератор должен поддерживать операцию remove.

  Класс AbstractSet является производным от AbstractCollection, и состав методов AbstractSet, которые подлежат обязательной реализации или могут быть переопределены при необходимости, тот же, что и в AbstractCollection, с дополнительным ограничением — класс, производный от AbstractSet, должен удовлетворять контракту интерфейса Set.

  При создании нового класса, наследующего AbstractList, для поддержки списка, не позволяющего выполнять операции модификации, достаточно реализовать только методы size и get(int). Если подвергнуть переопределению и метод set(int, Object), можно получить список, содержимое которого (но не размер) допускает изменение. Наконец, чтобы обеспечить возможность изменения размера списка, следует переопределить методы add(int,   Object) и remove  (int).

  В качестве примера рассмотрим задачу построения класса, способного обеспечить представление набора массивов в виде единого списка. Для ее решения можно воспользоваться одной из существующих реализаций интерфейса List, но ценой, которую придется заплатить, послужат вычислительные расходы, связанные с копированием данных из массивов в новую коллекцию. Иной подход, предусматривающий расширение класса AbstractList, позволит достичь цели без затрат на копирование:

 

import Java.util.*;

public class ArrayBunchList extends AbstractList {

      private Object[][]  arrays;

      private int size;

 

public ArrayBunchList(Object[][]  arrays)   {

 this.arrays =  (Object[][])arrays.clone();

 int s = 0;

 for  (int i  =0;   i  < arrays.length;   i++)

   s += arrays[i]-length;

size = s;

 {

public int size() { 

   return size;

}

public Object get(int index)   {

int off =0;       // Смещение от начала коллекции

 for  (int i  = 0;   i   < arrays.length;   i++)   {

 if (index < off + arrays[i].length)

   return arrays[i][index – off];

off += arrays[i].length;

   }

 throw new ArraylndexOutOfBoundsException(index);

}

public object set(int index, object value) {

int off =0;  // Смещение от начала коллекции

 for (int i = 0; i < arrays.length; i++) {

 if (index < off + arrays[i].length) {

Object ret = arrays[i][index – off];

 arrays[i][index – off] = value;

 return ret;

}

    off += arrays[i].length;

}

 throw new ArraylndexOutOfBoundsException(index);

   }

}

В ходе конструирования объекта ArrayBunchList все массивы, образующие единый источник данных, сохраняются в виде поля arrays, а значение общего размера полученной коллекции присваивается полю size. В классе ArrayBunchList реализованы методы size, get и set, но не add или remove. Это значит, что содержимое элементов списка может изменяться, но его размер — нет. Все обращения к элементам "внутренних" массивов осуществляются при посредничестве метода get, а любые действия, направленные на изменение значений элементов списка объекта ArrayBunchList, выполняются с помощью метода set и находят отражение в содержимом соответствующего "внутреннего" массива.

  Класс AbstractList пользуется реализациями итераторов Iterator и Li Stlterator, взаимодействующими с другими методами класса. Поскольку методы объектов-итераторов обращаются и к соответствующим методам класса, производного от AbstractList, последние определенным образом повлияют на поведение тех методов итераторов, которые предполагают внесение изменений.

   Методы итерации, обеспечивающие чтение содержимого объекта AbstractList, обращаются к методу get последнего. Метод get класса ArrayBunchList, например, выполняет довольно большую работу, если запрошенный элемент относится к одному из "дальних" массивов. Можно было бы сделать метод get более "разумным", чтобы помочь ему побыстрее справляться с задачей, но мы поступим иначе, предложив более эффективную реализацию итератора и включив его в состав класса ArrayBunchList:

private class ABLlterator implements  iterator {

    private int off;              // Смещение от начала списка

    private int array;       // номер текущего массива

    private int pos;             // позиция  в текущем массиве

 

ABLiterator()   {

    off = 0;

    array = 0;

     pos = 0;

// пропустить все изначально пустые массивы

for (array = 0; array < arrays.length; array++)

 if (arrays[array].length > 0)

          break;

 }

 public boolean hasNext() {

return off + pos < size();

}

public Object next() {

 if (IhasNext())

    throw new NoSuchElementException();

 Object ret = arrays[array][pos++];

 

// Перейти к следующему элементу while (pos >= arrays[array].length) {

off += arrays[array++].length;

pos = 0;

if (array >= arrays.length)

     break;

}

 return  ret;

}

public void remove() {

     throw new UnsupportedOperationException();

 }

}

Приведенная реализация тесно привязана к структуре данных списка ArrayBunchList и основывается на точном знании того, "откуда" поступает очередной элемент. Она обеспечивает гораздо более высокую эффективность в сравнении с решением, предполагающим обращение к методу get, который имитирует поведение метода next итератора. (Помимо того, в ней корректно обрабатываются ситуации, когда пусты либо некоторые из массивов, либо список ArrayBunchList целиком.)

  Зачастую существенного роста эффективности списка, допускающего расширение, можно достичь, если переопределить предлагаемый классом AbstractList protected-метод removeRange, который в качестве параметров принимает два значения типа int, mi n и max, и удаляет все элементы списка с индексами из интервала от mi n (включительно) до max (кроме элемента на позиции max). Метод clear пользуется методом removeRange для удаления элементов списка в целом, а также его фрагментов. Реализация, предусмотренная по умолчанию, предполагает вызов remove для каждого элемента, подлежащего Удалению, по отдельности. Во многих случаях процесс удаления может быть ускорен, если в реализации метода removeRange учесть особенности конкретной структуры данных.

  Класс AbstractSequentialList расширяет класс AbstractList с целью облегчения реализации списков, которые основаны на модели последовательного доступа (sequential access) к хранимым данным, когда для перемещения от одного элемента к другому требуется проследовать по всем промежуточным элементам. Чтобы обратиться к элементу с произвольным индексом, размещенному в подобном хранилище, требуется проделать немалую работу. К числу структур Данных, поддерживающих схему последовательного доступа, относится двусвязный список (doubly-linked list), реализуемый классом LinkedList. Массивы, в отличие от двусвязных списков,  обеспечивают средства произвольного доступа (random   access).   Вот   почему   класс   ArrayList   наследует   AbstractList,   a LinkedList — AbstractSequentialList.

   В то время как AbstractList реализует итераторы с помощью метода get обеспечивающего средства произвольного доступа, AbstractSequentialList поддерживает аналогичные инструменты при посредничестве итератора, который возвращается реализованным вариантом метода Listlterator. Также подлежит реализации и метод size. Класс, производный от AbstractSequentialList, будет допускать возможность модификации данных списка в той мере, какая предусмотрена методами итератора. Если, например, итератор позволяет выполнять операции set, но запрещает вызывать add или remove, вы получите класс, который допускает модификацию содержимого элементов списка, но не разрешает изменять его размер.

   Чтобы воспользоваться классом AbstractMap, необходимо реализовать метод entrySet, возвращающий неизменяемое множество пар соответствий (тар entry), представленное в виде объекта Set. Чтобы обеспечить возможность изменения коллекции соответствий, следует переопределить метод put, и итератор, возвращаемый объектом Set, должен поддерживать функцию remove.

   В процессе проектирования рассматриваемых абстрактных классов коллекций преследовалась цель облегчить их последующее расширение, но критерий эффективности при таком подходе удовлетворяется отнюдь не всегда. Зачастую можно достичь гораздо более высоких показателей производительности расширенных классов коллекций, если осмысленно и здраво переопределить и другие их методы, как мы показали на примере итератора ABLIterator, объявленного в составе класса ArrayBunchList. Можно привести и другой пример. Метод get класса AbstractMap в редакции, предлагаемой по умолчанию, для отыскания требуемого значения, отвечающего заданному ключу, должен последовательно просматривать множество пар соответствий до тех пор, пока искомый объект не будет найден. Эффективность такой реализации оценивается функцией О(п). Чтобы достичь производительности О(1), класс HashMap переопределяет get и все другие методы, имеющие дело с объектами ключей, таким образом, чтобы воспользоваться преимуществами, предоставляемыми моделью хеш-таблицы. Впрочем, .метод equals в HashMap не переопределен, поскольку без средств итерации в данном случае обойтись нельзя, а реализация метода, предлагаемая классом AbstractMap, и так достаточно эффективна.

 

Источник: Арнолд, Кен, Гослинг, Джеймс, Холмс, Дэвид. Язык программирования Java. 3-е изд .. : Пер. с англ. – М. : Издательский дом «Вильяме», 2001. – 624 с. : ил. – Парал. тит. англ.

По теме:

  • Комментарии