1 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-1 Коллекции и generics

2 © Luxoft Training 2013 Коллекции Очень часто требуется работать с группами связанных элементов данных Часто массивы не удовлетворяют этим требованиям так как: Размер массива нельзя изменить после создания Массивы имеют ограниченные методы обработки 4-2 Введение

3 © Luxoft Training 2013 Коллекции Для решения задач создания сложных структур данных применяются классы Java Collections Framework Коллекции – это механизм манипулирования ссылками объектов, в отличие от массивов, которые могут хранить примитивные типы 4-3 Введение

4 © Luxoft Training 2013 Коллекции Центральные интерфейсы Java Collection Framework: java.util.Collection java.utils.List (расширяет java.util.Collection ) java.utils.Set (расширяет java.util.Collection ) java.utils.Map (не расширяет java.util.Collection ) 4-4 Введение

5 © Luxoft Training 2013 Коллекции 4-5 Иерархия основных интерфейсов

6 © Luxoft Training 2013 Коллекции 4-6 Иерархия основных интерфейсов

7 © Luxoft Training 2013 Коллекции Фреймворк – нечто большее, чем просто набор интерфейсов Помимо декларации методов каждый интерфейс определяет специфическую семантику (поведение) Кроме того, фреймворк предлагает набор имплементаций конкретного интерфейса 4-7 Введение

8 © Luxoft Training 2013 Коллекции Некоторые коллекции могут работать быстро, но потреблять много памяти Некоторые коллекции работают быстро в определенных условиях Все современные коллекции не threadsafe – их нельзя использовать в нескольких потоках Программист обязан обеспечивать целостность данных самостоятельно 4-8 Введение

9 © Luxoft Training 2013 Коллекции Java Collections Framework был введен в Java 1.2 До этого существовали некоторые разрозненные коллекции, которые принято называть legacy коллекциями К ним относятся классы Vector, Stack, Hashtable и некоторые другие (рассмотрим далее) 4-9 Введение

10 © Luxoft Training 2013 Коллекции 4-10 Иерархия основных интерфейсов

11 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-11 Коллекции и generics

12 © Luxoft Training 2013 Коллекции Интерфейс java.util.Collection является базовым в иерархии коллекций Коллекция – группа объектов, называемых элементами Некоторые коллекции могут допускать повторение элементов, некоторые нет Некоторые сохраняют порядок, некоторые - нет 4-12 Интерфейс java.util.Collection

13 © Luxoft Training 2013 Коллекции SDK не предоставляет конкретных имплементация данного интерфейса, он предоставляет имплементации для унаследованных интерфейсов, таких как Set и List При этом java.util.Collection задает методы, общие для всех коллекций 4-13 Интерфейс java.util.Collection

14 © Luxoft Training 2013 Коллекции 4-14 Интерфейс java.util.Collection

15 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-15 Коллекции и generics

16 © Luxoft Training 2013 Коллекции java.util.Collection расширяет интерфейс java.util.Iterable, определяющий метод iterator() Данный метод возвращает экземпляр интерфейса java.util.Iterator Iterator позволяет перебирать элементы коллекции и заменяет legacy класс Enumeration, который служил той же цели 4-16 Интерфейс java.util.Iterator

17 © Luxoft Training 2013 Коллекции Кроме перебора элементов коллекции Iterator позволяет безопасно удалить данный элемент из итерируемой коллекции 4-17 Интерфейс java.util.Iterator

18 © Luxoft Training 2013 Коллекции boolean hasNext() возвращает true, если в коллекции есть элементы Object next() возвращает следующий элемент void remove() удаляет элемент, возвращенный next() Безопасный способ удаления при итерации коллекции 4-18 Интерфейс java.util.Iterator

19 © Luxoft Training 2013 Коллекции 4-19 Интерфейс java.util.Iterator

20 © Luxoft Training 2013 Коллекции Список хранит элементы в той последовательности, в которой они были добавлены Список индексируется с нуля Список схож с массивом, но может изменять размер 4-20 Интерфейс java.util.List

21 © Luxoft Training 2013 Коллекции 4-21 Дополнительные методы java.util.List

22 © Luxoft Training 2013 Коллекции java.util.ArrayList – имплементация списка на базе массива Быстрый поиск Медленный рост, т.к. необходимо перекопировать массив во внутреннем представлении Медленное удаление, т.к. необходимо переинициализировать внутренний массив 4-22 Имплементации java.util.List

23 © Luxoft Training 2013 Коллекции java.util.LinkedList – имплементация списка на двух связанного списка Медленный поиск Быстрый рост, т.к. добавить новый элемент можно без перекопированния – добавить в конец очереди 4-23 Имплементации java.util.List

24 © Luxoft Training 2013 Пример: LinkedOrArrayListTutor Коллекции

25 © Luxoft Training 2013 Коллекции Set не имеет концепции порядка – просто набор элементов Set не может иметь дублирующиеся элементы 4-25 Интерфейс java.util.Set

26 © Luxoft Training 2013 Коллекции При попытке вставить в set уже существующий элемент, метод add() возвращает false и не вставляет элемент При сравнении элементов set использует метод equals(), а не == 4-26 Интерфейс java.util.Set

27 © Luxoft Training 2013 Коллекции 4-27 Интерфейс java.util.Set

28 © Luxoft Training 2013 Коллекции Реализация java.util.HashSet хранит элементы в специальной хэш- структуре. Порядок элементов, возвращенный iterator() не детерминирован 4-28 Имплементация java.util.HashSet

29 © Luxoft Training 2013 Коллекции Вне зависимости от количества элементов в HashSet, доступ в нему занимает константное время HashSet хранит элементы в специальных контейнерах (bucket) сгруппированных по значению hashCode() 4-29 Имплементация java.util.HashSet

30 © Luxoft Training 2013 Коллекции Реализация java.util.TreeSet гарантирует, что элементы, перебираемые с помощью iterator() возвращаются в некотором порядке Время доступа к элементам log(n), где n - число элементов в set 4-30 Имплементация java.util.TreeSet

31 © Luxoft Training 2013 Коллекции Интерфейс java.util.SortedSet расширяет java.util.Se t и представляет отсортированный набор элементов Элементы, добавленные в такой набор пересортировываются, java.util.SortedSet позволяет получить элементы в некотором порядке 4-31 Имплементация java.util.TreeSet

32 © Luxoft Training 2013 Коллекции При этом необходимо задать способ сравнения элементов коллекции (рассмотрим ниже) Одной из реализация интерфейса java.util.SortedSet является класс java.util.TreeSet 4-32 Имплементация java.util.TreeSet

33 © Luxoft Training 2013 Коллекции 4-33 Методы java.util.SortedSet

34 © Luxoft Training 2013 Примеры: CollectionTutor CollectionRemoveTutor Коллекции

35 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-35 Коллекции и generics

36 © Luxoft Training 2013 Коллекции Т.к. класс TreeSet поддерживает порядок элементов, ему необходим механизм сравнения двух объектов Для сравнения он может использовать интерфейсы java.lang.Comparable и java.util.Comparator 4-36 Сравнение элементов

37 © Luxoft Training 2013 Коллекции java.lang.Comparable определяет метод public int compareTo(Object x), который возвращает положительное число, если текущий объект «больше», чем х, отрицательное, если меньше, и ноль, если они равны 4-37 Java.lang.Comparable

38 © Luxoft Training 2013 Коллекции Все элементы, которые вставляются в java.util.TreeSet должны имплементировать Comparable java.util.TreeSet допускает вставку произвольного наследника Object, однако, если элемент не имплементирует Comparable, в runtime возбудится ClassCastException 4-38 Java.lang.Comparable

39 © Luxoft Training 2013 Коллекции Многие классы Core Java имплементируют Comparable (String, Date, Integer) Реализация Comparable должна задавать т.н. натуральный порядок. Например, для строк это лексикографический порядок 4-39 Java.lang.Comparable

40 © Luxoft Training 2013 Коллекции Для класса Student натуральный порядок может быть неочевиден: можно сортировать «студентов» по имени, фамилии, оценкам, году приема и т.п. Если натуральный порядок задать нельзя, или если необходим иной способ сравнения элементов, следует использовать java.util.Comparator 4-40 Java.lang.Comparable

41 © Luxoft Training 2013 Коллекции Так же можно определить класс, реализующий интерфейс java.util. Comparator сравнивающий объекты данного типа Соответствующий Comparator можно передать в TreeSet, используя специальный конструктор int compare(Object o1, Object o2) сравнивает два объекта 4-41 java.lang.Comparator

42 © Luxoft Training 2013 Коллекции 4-42 java.lang.Comparator

43 © Luxoft Training 2013 Коллекции Парадигма натурального порядка Comparable и механизм Comparatorов используется не только при сортировки TreeSet, но и при сортировке массивов и прочих структур данных Цель данных инструментов – предоставить возможность сравнения объектов данного типа 4-43 java.lang.Comparator

44 © Luxoft Training 2013 Пример: ComparableTutor Коллекции java.lang.Comparator

45 © Luxoft Training 2013 Коллекции 4-45 Диаграмма коллекций

46 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-46 Коллекции и generics

47 © Luxoft Training 2013 Коллекции java.util.Map объединяет две коллекции – коллекцию ключей и значений Map ассоциирует ровно 1 значение (которое может быть null ) с каждым ключом Каждый ключ содержится в Map ровно 1 раз Хороший пример - словарь 4-47 Интерфейс java.util.Map

48 © Luxoft Training 2013 Коллекции 4-48 Интерфейс java.util.Map

49 © Luxoft Training 2013 Коллекции 4-49 Реализации java.util.Map

50 © Luxoft Training 2013 Коллекции java.util.HashMap хранит ключи в недетерминированном порядке. Доступ к ключам осуществляется быстро Метод hashCode() должен быть переопределен и возвращать равномерно различные числа При проверке равенства элементов используется метод equals() (а не ==) 4-50 Реализации java.util.Map

51 © Luxoft Training 2013 Коллекции java.util.TreeMap возвращает ключи упорядоченно. Реализует интерфейс java.util.SortedMap Ключи должны имплементировать интерфейс java.lang.Comparable Либо передавать экземпляр java.util.Comparator в конструктор HashMap 4-51 Реализации java.util.Map

52 © Luxoft Training 2013 Коллекции Интерфейс java.util.SortedMap расширяет java.util.Map 4-52 Интерфейс java.util.SortedMap

53 © Luxoft Training 2013 Коллекции 4-53 Пример

54 © Luxoft Training 2013 Пример: MapTutor Коллекции java.util.Map

55 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-55 Коллекции и generics

56 © Luxoft Training 2013 Коллекции Существует два вспомогательных класса, содержащих статические методы, позволяющие оперировать коллекциями и массивами: java.util.Collections java.util.Arrays 4-56 Вспомогательные классы

57 © Luxoft Training 2013 Коллекции 4-57 Некоторые методы java.util.Collections

58 © Luxoft Training 2013 Коллекции 4-58 Некоторые методы java.util.Arrays

59 © Luxoft Training 2013 Пример: CollectionUtilitiesTutor Коллекции Некоторые методы java.util.Arrays

60 © Luxoft Training 2013 Коллекции Интерфейсы Collection Framework были введены в Java 1.2 До этого существовали похожие структуры данных, но их поведение не было унифицировано Все методы этих структур были синхронизированы, что, в общем виде, ведет к снижению производительности 4-60 Legacy коллекции

61 © Luxoft Training 2013 Коллекции С Java 1.2 legacy коллекции стали имплементировать интерфейсы Collections Framework, однако, несмотря на это, использовать их не рекомендуется в силу причин, приведенных выше Для синхронизации использовать другие механизмы 4-61 Legacy коллекции

62 © Luxoft Training 2013 Коллекции Класс Vector, имплементирует List. Вместо Vector следует использовать класс ArrayList Класс Stack, подкласс класса Vector, поддерживает операции работы со стеком: push(), pop(), peek() Класс Hashtable, имплементирует интерфейс Map. Вместо Hashtable следует использовать класс HashMap 4-62 Legacy коллекции

63 © Luxoft Training 2013 Коллекции Каждая из этих коллекций имеет метод elements(), возвращающий объект Enumeration, позволяющий итерировать элементы подобно итератору Однако, этот класс не совместим с Iterator Поэтому, использовать Enumeration не рекомендуется 4-63 Legacy коллекции

64 © Luxoft Training 2013 Коллекции Все коллекции Collections Framework не синхронизированы. То есть, методы классов не помечены как synchronized Это увеличивает скорость работы однопоточной программы 4-64 Синхронизация коллекций

65 © Luxoft Training 2013 Коллекции Для того, чтобы получить экземпляр синхронизированной коллекции, необходимо вызвать Collections.synchronizedXXX(), где XXX - это наименование интерфейса: Set, List, Map, Collection и д.р Синхронизация коллекций

66 © Luxoft Training 2013 Коллекции При этом создается примитивный класс-делегат, все методы которого синхронизированы, и делегируют вызов на проексируемую коллекцию 4-66 Синхронизация коллекций

67 © Luxoft Training 2013 Коллекции 4-67 Синхронизация коллекций. Пример

68 © Luxoft Training 2013 Коллекции С точки зрения инкапсуляции данных, неправильным является возвращение экземпляра коллекции из метода класса, так как клиентский код может модифицировать эту коллекцию Одна из техник решения этой проблемы – возвратить копию коллекции, при этом скопируется только структура коллекции, но не содержимое 4-68 Немодифицируемые коллекции

69 © Luxoft Training 2013 Коллекции Второй вариант – вызвать Collections. unmodifiableXXX, возвращающий простой класс-прокси, делегирующий вызовы немодифицирующим методам ( get(), size() ) соответствующей коллекции, и возбуждающий UnsupportedOperationException для методов, модифицирующих коллекцию (например add(), remove() ) 4-69 Немодифицируемые коллекции

70 © Luxoft Training 2013 Коллекции 4-70 Немодифицируемые коллекции. Пример

71 © Luxoft Training 2013 Пример: SynchronizedListTutor Коллекции

72 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-72 Коллекции и generics

73 © Luxoft Training 2013 Generics При работе с коллекциями положить объект в коллекцию намного проще, чем получить из нее. Т.к. при сохранении объекта он автоматически конвертируется, но при получении программист обязан выполнить cast 4-73 Введение

74 © Luxoft Training 2013 Generics 4-74 Введение

75 © Luxoft Training 2013 Generics Java 1.5 позволяет избежать необходимости делать cast Generic collections (или generics) – это коллекции, которые содержат элементы одного типа известного компилятору 4-75 Введение

76 © Luxoft Training 2013 Generics Объекты, полученные из generic коллекции, не должны приводиться (cast) Компилятор обеспечивает, что объекты неправильного типа не могут быть сохранены в generic коллекции 4-76 Плюсы generics

77 © Luxoft Training 2013 Generics Чтобы создать generic коллекцию, которая содержит только экземпляры класса Dragon : При декларации переменной myList, идентификатор между угловыми скобками – имя класса или интерфейса 4-77 Создание generics

78 © Luxoft Training 2013 Generics Это декларирует, что myList – коллекция объектов совместимых (compatible) с типом Dragon При создании объекта коллекций используется та же нотация: …= new ArrayList (); 4-78 Создание generics

79 © Luxoft Training 2013 Generics При создании объекта коллекции необходимо указывать в точности тот же тип, что и при декларации коллекции Если при создании объекта коллекции не парамметризовать его, то компилятор выдаст предупреждение 4-79 Создание generics

80 © Luxoft Training 2013 Коллекции Теперь в примере все методы работы с вектором ожидают в качестве аргументов экземпляр класса Dragon или его подкласс или (если Dragon – это интерфейс) класс, имплементирующий интерфейс Dragon 4-80 Использование generics

81 © Luxoft Training 2013 Коллекции 4-81 Использование generics. Пример

82 © Luxoft Training 2013 Коллекции Итератор так же может быть generic в рассматриваемом примере myList.iterator() возвращает Iterator При вызове метода next() итератора нет необходимости приводить тип 4-82 Generic итераторы

83 © Luxoft Training 2013 Коллекции 4-83 Generic итераторы. Пример

84 © Luxoft Training 2013 Коллекции При работе с generics невозможно получить ClassCastException, т.к. компилятор проверяет что не совместимые объекты не могут быть добавлены в generic коллекцию 4-84 Generics

85 © Luxoft Training 2013 Коллекции Все классы Collections фреймворк могут быть generic : Set s = new TreeSet (); Map d = new HashMap (); Iterator i = d.values().iterator(); 4-85 Generics

86 © Luxoft Training 2013 Коллекции При работе с документацией коллекций необходимо правильно понимать новый синтаксис Декларация Interface Set объявляет интерфейс, который будет работать с типом E Объявление boolean add(E o) говорит, что метод add() принимает тип E в качестве параметра 4-86 Generics и API документация

87 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-87 Коллекции и generics

88 © Luxoft Training 2013 Коллекции При итерировании коллекций можно избавиться от необходимости явно использовать итератор, используя расширенный оператор for В следующем примере он вызывается неявно: for (Dragon d:dragons) d.sitOnGold(); 4-88 Generics и расширенный цикл for

89 © Luxoft Training 2013 Коллекции Это эквивалентно: Справа от двоеточия в операторе for может стоять любой тип, расширяющий java.util.Collection 4-89 Generics и расширенный цикл for

90 © Luxoft Training 2013 Коллекции Данный синтаксис позволяет писать более чистый, менее уязвимый от ошибок, более легкий для чтения код 4-90 Generics и расширенный цикл for

91 © Luxoft Training 2013 Упражнение 4-91 Упражнение 16 Bank Application Использование коллекций

92 © Luxoft Training 2013 Модуль 4 Обзор Collections Framework Интерфейс java.util.Collection и его реализации Итерация коллекций Сравнение элементов, интерфейсы Comparable и Comparator Интерфейс java.util.Map и его реализации Утилитные классы java.util.Collections и java.util.Arrays Generics Generics и расширенный цикл for 4-92 Коллекции и generics