49
HashSet, TreeSet и LinkedHashSet относятся к семейству Set. Из выходных данных видно, что в множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов. В HashSet порядок элементов определяется по довольно сложному алгоритму — пока достаточно знать, что этот алгоритм обеспечивает минимальное время выборки элементов, но порядок следования элементов на первый взгляд выглядит хаотично. Если порядок хранения для вас важен, используйте контейнер TreeSet, в котором объекты хранятся отсортированными по возрастанию в порядке сравнения, или LinkedHashSet с хранением элементов в порядке добавления.
Карта (Map) позволяет искать объекты поключу, как несложная база данных. Объект, ассоциированный с ключом, называетсязначением. (Карты также называютассоциативными массивами.)В нашем примере используются три основные разновидности Map: HashMap, TreeMap и LinkedHashMap. Как и HashSet, HashMap обеспечивает максимальную скорость выборки, а порядок хранения его элементов не очевиден. TreeMap хранит ключи отсортированными по возрастанию, a LinkedHashMap хранит ключи в порядке вставки, но обеспечивает скорость поиска HashMap.
List
Контейнеры List гарантируют определенный порядок следования элементов. Интерфейс List дополняет Collection несколькими методами, обеспечивающими вставку и удаление элементов в середине списка. Существует две основные разновидности List:
• Базовый контейнер ArrayList, оптимизированный для произвольного доступа к элементам, но с относительно медленнными операциями вставки (удаления) элементов в середине списка.
• Контейнер LinkedList, оптимизированный для последовательного доступа, с быстрыми операциями вставки (удаления) в середине списка
;
Произвольный доступ к элементам LinkedList выполняется относительно медленно, но по широте возможностей он превосходит ArrayList.
В следующем примере используется библиотека typenfo.pets из главы «Информация о типе». Она содержит иерархию классов домашних животных Pet, а также ряд вспомогательных средств для случайного построения объектов Pet. Пока достаточно знать, что (1) библиотека содержит класс Pet и производные типы, и (2) статический метод Pets.arrayList() возвращает контейнер ArrayList, заполненный случайно выбранными объектами Pet.
//• hoi ding/ListFeatures.java import typeinfo.pets.*; import java.util.*;
import static net mindview util.Print.*:
public class ListFeatures {
public static void main(String[] args) { Random rand = new Random(47); List<Pet> pets = Pets.arrayList(7); printC'l: " + pets); Hamster h = new HamsterO; pets.add(h); // Автоматическое изменение размера print("2: " + pets); print("3: " + pets.contains(h)); pets.remove(h); // Удаление объекта
Pet p = pets.get(2);продолжение &print("4: " + р + " " + pets.indexOf(p));
Pet cymric = new CymricO;
print("5: " + pets.indexOf(cymric));
print("6: " + pets.remove(cymric));
// Точно заданный объект:
print("7: " + pets.remove(p));
print("8: " + pets);
pets.add(3. new MouseO); // Вставка no индексу
print("9: " + pets);
List<Pet> sub = pets.subListd, 4);
printC'subList: " + sub);
print("10: " + pets.containsAll(sub));
Col lections.sort(sub); // Сортировка "на месте"
print("sorted subList: " + sub);
// Для containsAllО порядок неважен:
printC'll: " + pets.containsAll(sub));
Col 1ections.shuffle(sub. rand); // Случайная перестановка
print("shuffled subList: " + sub).
print("12: " + pets.containsAll(sub));
List<Pet> copy = new ArrayList<Pet>(pets);
sub = Arrays.asList(pets.getd). pets.get(4));
printC'sub: " + sub);
copy.retainAll(sub);
print("13: " + copy);
copy = new ArrayList<Pet>(pets); // Получение новой копии copy remove(2); // Удаление по индексу print("14: " + copy);
copy.removeAll(sub); // Удаление заданных элементов print("15: " + copy);
copy.setd, new MouseO); // Замена элемента print("16: " + copy);
copy.addAll(2. sub); // Вставка в середину списка
pri nt("17: " + copy);
print("18: " + pets.isEmptyO);
pets.clearO; // Удаление всех элементов
print("19: " + pets);
print("20: " + pets isEmptyO);
pets.addAll(Pets.arrayList(4));
print("21: " + pets);
Object[] о = pets.toArrayO;
print("22: " + o[3]);
Pet[] pa = pets.toArray(new Pet[0]),
print("23: " + pa[3].id());
}
} /* Output
1: [Rat. Manx. Cymric. Mutt. Pug. Cymric. Pug]
2: [Rat. Manx. Cymric. Mutt. Pug. Cymric. Pug. Hamster]
3: true
4: Cymric 2
5: -1
6: false
7: true
8: [Rat. Manx. Mutt. Pug. Cymric. Pug] 9: [Rat. Manx. Mutt. Mouse. Pug. Cymric. Pug] subList: [Manx. Mutt. Mouse] 10: true
sorted subList: [Manx. Mouse. Mutt] 11: true
shuffled subList: [Mouse, Manx. Mutt] 12: true
sub: [Mouse. Pug] 13: [Mouse, Pug]
14: [Rat. Mouse. Mutt, Pug. Cymric, Pug]
15: [Rat. Mutt. Cymric. Pug]
16: [Rat. Mouse. Cymric. Pug]
17: [Rat. Mouse. Mouse. Pug. Cymric. Pug]
18: false
19: []
20: true
21: [Manx. Cymric. Rat. EgyptianMau] 22: EgyptianMau 23: 14 *///:-
Строки вывода пронумерованы, чтобы вам было удобнее связывать результат с исходным кодом.
В первой строке выводится исходный контейнер List с объектами Pets. В отличие от массивов, List поддерживает добавление и удаление элементов с изменением размеров списка. Результат добавления Hamster виден в строке 2: объект появляется в конце списка.
Метод contains() проверяет, присутствует ли объект в списке. Чтобы удалить объект, передайте ссылку на него методу remove(). Кроме того, при наличии ссылки на объект можно узнать его индекс в списке при помощи метода indexOf(), как показано в строке 4.
При проверке вхождения элемента в List, проверке индекса элемента и удаления элемента из List по ссылке используется метод equals() (из корневого класса Object). Все объекты Pet считаются уникальными, поэтому несмотря на присутствие двух объектов Cymric в списке, если я создам новый объект Cymric и передам его indexOf(), результат будет равен -1 (элемент не найден), а вызов remove() вернет false. Для других классов метод equals() может быть определен иначе — например, объекты String считаются равными в случае совпадения содержимого.
В строках 7 и 8 из List успешно удаляется заданный объект. Строка 9 и предшествующий ей код демонстрируют вставку элемента в середину списка. Метод subList() позволяет легко создать «срез» из подмножества элементов списка; естественно, при передаче его методу containsAll() большего списка будет получен истинный результат. Вызовы Collections.sort() и Collec- tions.shuffle() для sub не влияют на результат вызова containsAll().
Метод retainAll() фактически выполняет операцию «пересечения множеств», то есть определения всех элементов сору, которые также присутствуют в sub. И снова поведение метода зависит от реализации equals().
В строке 14 представлен результат удаления элемента по индексу — это проще, чем удаление по ссылке на объект, потому что вам не придется беспокоиться о поведении equals().
Работа метода removeAll() также зависит от equals(). Как подсказывает название, метод удаляет из List все объекты, входящие в List-аргумент.
Название метода set() выбрано неудачно, потому что оно совпадает с именем класса Set — возможно, лучше было бы назвать метод «replace», потому что он заменяет элемент с заданным индексом (первый аргумент) вторым аргументом.
В строке вывода 17 показано, что для List существует перегруженный метод addAll(), вставляющий новый список в середину исходного списка (вместо простого добавления в конец методом addAll(), унаследованным от Collection).
В строках 18-20 представлен результат вызова методов isEmpty() и clear(). Строки 22 и 23 демонстрируют, что любой объект Collection можно преобразовать в массив с использованием to Array ().
Итераторы
У любого контейнера должен существовать механизм вставки и выборки элементов. В конце концов, контейнер предназначен именно для хранения объектов. При работе с List для вставки может использоваться метод add(), а для выборки — метод get() (впрочем, существуют и другие способы).
Если взглянуть на ситуацию с более высокого уровня, обнаруживается проблема: чтобы использовать контейнер в программе, необходимо знать его точный тип. Что, если вы начали использовать в программе контейнер List, а затем обнаружили, что в вашем случае будет удобнее применить тот же код к множеству (Set)? Или если вы хотите написать универсальный код, который не зависит от типа контейнера и может применяться к любому контейнеру?
С данной абстракцией хорошо согласуется концепцияитератора(iterator). Итератор — это объект, обеспечивающий перемещение по последовательности объектов с выбором каждого объекта этой последовательности, при этом программисту-клиенту не надо знать или заботиться о лежащей в ее основе структуре. Вдобавок, итератор обычно является так называемым «легковесным» (lightweight) объектом: его создание должно обходиться без заметных затрат ресурсов. Из-за этого итераторы часто имеют ограничения; например, Iterator в Java поддерживает перемещение только в одном направлении. Его возможности не так уж широки, но с его помощью можно сделать следующее:
• Запросить у контейнера итератор вызовом метода iterator(). Полученный итератор готов вернуть начальный элемент последовательности при первом вызове своего метода next().
• Получить следующий элемент последовательности вызовом метода next().
• Проверить, остались ли еще объекты в последовательности (метод hasNext()).
• Удалить из последовательности последний элемент, возвращенный итератором, методом remove().
Чтобы увидеть итератор в действии, мы снова воспользуемся иерархией Pets:
// holding/Simplelteration java import typeinfo pets *; import java util *.
public class Simplelteration {
public static void main(String[] args) {
List<Pet> pets = Pets arrayList(12); Iterator<Pet> it = pets iteratorO. whi 1 e(it hasNextO) {
Pet p = it nextO;
System.out pri nt(p id() + " " + p + " ");
}
System.out printlnO; // Более простой способ, for(Pet p • pets)
System out print(p id() + "+ p + " "); System, out. printlnO;
// Итератор также способен удалять элементы: it = pets. iteratorO. for(int i = 0: i < 6: i++) { it nextO: it.removeO.
}
System.out.pnntln(pets):
}
} /* Output-
0:Rat l:Manx 2:Cymric 3-Mutt 4-Pug 5:Cymric 6.Pug 7:Manx 8.Cymric 9:Rat 10:EgyptianMau 11.Hamster
0-Rat 1-Manx 2-Cymric 3:Mutt 4:Pug 5.Cymric 6:Pug 7:Manx 8:Cymric 9-Rat 10-EgyptianMau 11:Hamster
[Pug. Manx. Cymric. Rat. EgyptianMau. Hamster] *///•-
Мы видим, что с Iterator можно не беспокоиться о количестве элементов в последовательности. Проверка осуществляется методами hasNext() и next().
Если вы просто перебираете элементы списка в одном направлении, не пытаясь модифицировать его содержимое, «синтаксис foreach» обеспечивает более компактную запись.
Iterator удаляет последний элемент, полученный при помощи next(), поэтому перед вызовом remove() необходимо вызвать next().
Теперь рассмотрим задачу создания метода display(), не зависящего от типа контейнера: