Collections Framework Java Advanced

2Georgiy KorneevJava Advanced / Collections Framework Содержание 1.Коллекции 2.Множества 3.Списки 4.Очереди и деки 5.Отображения 6.Упорядоченные коллекции 7.Алгоритмы 8.Устаревшие коллекции 9.Заключение

3Georgiy KorneevJava Advanced / Collections Framework Collections Framework Набор стандартных контейнеров (коллекций) и правил их использования Интерфейсы Реализации Алгоритмы Пакет java.util

Коллекции Часть 1

5Georgiy KorneevJava Advanced / Collections Framework Коллекции Коллекция неупорядоченный набор элементов Интерфейс Collection

6Georgiy KorneevJava Advanced / Collections Framework Немодифицирующие операции Определение размера size() количество элементов isEmpty() проверка на пустоту Проверки на вхождение contains(Object o) одного элемента containsAll(Collection c) всех элементов коллекции c

7Georgiy KorneevJava Advanced / Collections Framework Модифицирующие операции Добавление элементов add(Object e) одного элемента addAll(Collection c) элементов коллекции Удаление элементов remove(Object e) одного элемента removeAll(Collection с) элементов коллекции retainAll(Collection с) удаление элементов не из коллекции clear() удаление всех элементов Исключения UnsupportedOperationException

8Georgiy KorneevJava Advanced / Collections Framework Пример. Чтение в коллекцию public int read(String file) throws IOException { Scanner scanner = new Scanner( new File(file), "Cp1251"); int read = 0; while (scanner.hasNext()) { read++; c.add(scanner.next()); } return read; }

9Georgiy KorneevJava Advanced / Collections Framework Итераторы Итератор обход коллекции Интерфейс Iterator Метод Iterator Collection.iterator()

10Georgiy KorneevJava Advanced / Collections Framework Методы итераторов hasNext() определение наличия следующего элемента next() взятие следующего элемента remove() удаление элемента Исключения NoSuchElementException бросается при достижении конца коллекции ConcurrentModificationException бросается при изменении коллекции

11Georgiy KorneevJava Advanced / Collections Framework Применение итераторов Обход коллекции for(Iterator i = c.iterator(); i.hasNext(); ) { Object element = i.next();... } Фильтрование коллекции for(Iterator i = c.iterator(); i.hasNext(); ) { if (!p(i.next()) i.remove(); }

12Georgiy KorneevJava Advanced / Collections Framework Пример. Вывод коллекции на экран public void dump() { for (Iterator i = c.iterator(); i.hasNext(); ) { String word = (String) i.next(); System.out.print(word + ", "); } System.out.println(); }

13Georgiy KorneevJava Advanced / Collections Framework Преобразование в массив Object[] toArray() создает новый массив Object[] toArray(Object[] a) использует переданный массив Пример использования String[] i = (String[]) c.toArray(new String[c.size()]);

14Georgiy KorneevJava Advanced / Collections Framework Класс AbstractCollection Позволяет быстро реализовывать коллекции Реализация неизменяемых коллекций iterator() size() Реализация изменяемых коллекций add(Object o) iterator.remove()

Множества Часть 2

16Georgiy KorneevJava Advanced / Collections Framework Множества Множество коллекция без повторяющихся элементов Интерфейс Set

17Georgiy KorneevJava Advanced / Collections Framework Сравнение элементов Метод Object.equals(Object object) Рефлексивность o1.equals(o1) Симметричность o1.equals(o2) == e2.equals(o1) Транзитивность o1.equals(o2) && o2.equals(o3) => o1.equals(o3) Устойчивость o1.equals(o2) не изменяется, если o1 и o2 не изменяются Обработка null o1.equals(null) == false

18Georgiy KorneevJava Advanced / Collections Framework Операции над множествами addAll(Collection c) – объединение множеств retainAll(Collection c) – пересечение множеств containsAll(Collection c) – проверка вхождения removeAll(Collection c) – разность множеств

19Georgiy KorneevJava Advanced / Collections Framework Классы HashSet и LinkedHashSet HashSet множество на основе хэша LinkedHashSet множество на основе хэша c сохранение порядка обхода

20Georgiy KorneevJava Advanced / Collections Framework Конструкторы HashSet HashSet() пустое множество HashSet(Collection c) элементы коллекции HashSet(int initialCapacity) начальная вместимость HashSet(int initialCapacity, double loadFactor) начальная вместимость и степень заполнения

21Georgiy KorneevJava Advanced / Collections Framework Вычисление хэшей Метод Object.hashCode() Устойчивость hashCode() не изменяется, если объект не изменяется Согласованность с equals o1.equals(o2) => o1.hashCode() == o2.hashCode()

22Georgiy KorneevJava Advanced / Collections Framework Пример. Поиск уникальных слов CollectionExample c = new CollectionExample(new HashSet()); int words = c.read(args[0]); System.out.println("Words total: " + words); System.out.println("Unique words: " + c.getCollection().size()); c.dump();

23Georgiy KorneevJava Advanced / Collections Framework Класс AbstractSet Позволяет быстро реализовывать множества Неизменяемые множества iterator() size() Изменяемые множества add(Object o) iterator.remove()

Списки Часть 3

25Georgiy KorneevJava Advanced / Collections Framework Списки Список коллекция с индексированными элементами Интерфейс List

26Georgiy KorneevJava Advanced / Collections Framework Операции со списками Доступ по индексу get(int i) чтение set(int I, Object e) запись add(int i, Object e) добавление remove(int i) удаление Поиск элементов indexOf(Object e) поиск с начала lastIndexOf(Object e) поиск с конца Взятие вида List subList(int from, int to)

27Georgiy KorneevJava Advanced / Collections Framework Итератор по списку Интерфейс ListIterator extends Iterator Метод listIterator() Предыдущий / Следующий элементы

28Georgiy KorneevJava Advanced / Collections Framework Операции итератора по списку Передвижение hasNext() / hasPrevious() проверка next() / previous() взятие элемента nextIndex() / previousIndex() определение индекса Изменение remove() удаление элемента set(Object e) изменение элемента add(Object e) добавление элемента

29Georgiy KorneevJava Advanced / Collections Framework Класс ArrayList ArrayList список на базе массива Плюсы Быстрый доступ по индексу Быстрая вставка и удаление элементов с конца Минусы Медленная вставка и удаление элементов

30Georgiy KorneevJava Advanced / Collections Framework Вместимость ArrayList Вместимость реальное количество элементов Дополнительные методы ensureCapacity(int c) определение вместимости trimToSize() подгонка вместимости

31Georgiy KorneevJava Advanced / Collections Framework Конструкторы ArrayList ArrayList() пустой список ArrayList(Collection c) копия коллекции ArrayList(int initialCapacity) пустой список заданной вместимости

32Georgiy KorneevJava Advanced / Collections Framework Применения ArrayList Бесконечный массив Стек

33Georgiy KorneevJava Advanced / Collections Framework Пример. Вывод ArrayList на экран List list = new ArrayList(); … for (int i = list.size() - 1; i >= 0; i--) { System.out.println(list.get(i)); }

34Georgiy KorneevJava Advanced / Collections Framework Класс LinkedList LinkedList двусвязный список Плюсы Быстрое добавление и удаление элементов Минусы Медленный доступ по индексу

35Georgiy KorneevJava Advanced / Collections Framework Возможности LinkedList Конструкторы LinkedList() пустой список LinkedList(Collection c) копия коллекции Методы addFirst(Object o) – добавить в начало списка addLast(Object o) – добавить в конец списка removeFirst() – удалить первый элемент removeLast() – удалить последний элемент

36Georgiy KorneevJava Advanced / Collections Framework Применения LinkedList Стек Очередь Дек

37Georgiy KorneevJava Advanced / Collections Framework Пример. Вывод LinkedList на экран List list = new LinkedList(); … for (ListIterator li = list.listIterator(list.size()); li.hasPrevious(); ) { System.out.println(li.previous()); }

38Georgiy KorneevJava Advanced / Collections Framework Класс AbstractList Позволяет быстро реализовывать списки с произвольным доступом Неизменяемые списки get(index) size() Изменяемые списки set(index, element) Списки переменной длины add(index, element) remove(index)

39Georgiy KorneevJava Advanced / Collections Framework Класс AbstractSequentialList Позволяет быстро реализовывать списки с последовательным доступом Неизменяемые списки listIterator() (методы перемещения) size() Изменяемые списки ListIterator.set(index, element) Списки переменной длины ListIterator.add(element) ListIterator.remove(element)

Очереди и деки Часть 4

41Georgiy KorneevJava Advanced / Collections Framework Очередь Очередь – хранилище элементов для обработки Интерфейс Queue Свойства очередей Порядок выдачи элементов определяется конкретной реализацией Очереди не могут хранить null У очереди может быть ограничен размер

42Georgiy KorneevJava Advanced / Collections Framework Методы очередей Обычные методы add(Object o) – добавить элемент Бросает UnsupportedOperationException Object element() – вершина очереди Бросает NoSuchElementException Object remove() – удалить элемент из вершины Бросает NoSuchElementException Методы, не бросающие исключений offer(Object o) – добавить элемент Object peek() – вершина очереди Object poll() – удалить элемент из вершины

43Georgiy KorneevJava Advanced / Collections Framework Класс LinkedList Очередь на двусвязном списке

44Georgiy KorneevJava Advanced / Collections Framework Класс AbstractQueue Позволяет быстро реализовывать очереди Методы size() offer(Object o) peek() poll() iterator()

45Georgiy KorneevJava Advanced / Collections Framework Деки Интерфейс Deque Класс ArrayDeque –циклическая очередь Класс LinkedList – двусвязный список Действи е ГоловаХвост ИсключениеКод возврата ИсключениеКод возврата Вставка addFirstofferFirstaddLastofferLast Доступ getFirstpeekFirstgetLastpeekLast Удаление removeFirstpollFirstremoveLastpolLast

Отображения Часть 5

47Georgiy KorneevJava Advanced / Collections Framework Отображение Отображение множество пар ключ-значение при уникальности ключа Интерфейс Map

48Georgiy KorneevJava Advanced / Collections Framework Методы отображений (1) Доступ get(Object k) получение значение put(Object k, Object v) запись remove(Object k) удаление Проверки containsKey(Object k) наличие ключа containsValue(Object v) наличие значения Определения размера size() размер отображения isEmpty() проверка на пустоту

49Georgiy KorneevJava Advanced / Collections Framework Методы отображений (2) Взятие видов entrySet() множество пар values() коллекция значений keySet() множество ключей Массовые операции putAll(Map map) добавление всех пар

50Georgiy KorneevJava Advanced / Collections Framework Пары Пара ключ + значение Интерфейс Map.Entry Методы Object getKey() Object getValue() setValue(Object v)

51Georgiy KorneevJava Advanced / Collections Framework Классы HashMap и LinkedHashMap HashMap отображение на основе хэшей LinkedHashMap отображение на основе хэшей с сохранением порядка обхода

52Georgiy KorneevJava Advanced / Collections Framework Конструкторы HashMap HashMap() пустое отображение HashMap(Map m) копия отображения HashMap(int initialCapacity) начальная вместимость HashMap (int initialCapacity, int loadFactor) начальная вместимость и степень заполнения

53Georgiy KorneevJava Advanced / Collections Framework Класс AbstractMap Позволяет быстро реализовывать множества Метод entrySet()

54Georgiy KorneevJava Advanced / Collections Framework Пример. Подсчет слов в тексте (1) while (scanner.hasNext()) { String word = scanner.next(); Integer count = (Integer) map.get(word); int value = (count == null) ? 0 : count.intValue(); map.put(word, new Integer(value + 1)); }

55Georgiy KorneevJava Advanced / Collections Framework Пример. Подсчет слов в тексте (2) for ( Iterator i = map.entrySet().iterator(); i.hasNext(); ) { Map.Entry entry = (Map.Entry) i.next(); System.out.println( entry.getKey() + " " + entry.getValue()); }

Упорядоченные коллекции Часть 6

57Georgiy KorneevJava Advanced / Collections Framework Сравнение элементов Интерфейс Comparable int compareTo(Object o) естественный порядок Интерфейс Comparator int compare(Object o1, Object o2) сравнение элементов

58Georgiy KorneevJava Advanced / Collections Framework Сравнение элементов (контракт) Транзитивность Антисимметричность sgn(o1.compareTo(o2)) == -sgn(o2.compareTo(o1)) Согласованность с равенством o1.compareTo(o2) == 0 => sgn(o1.compareTo(o3)) == sgn(o2.compareTo(o3)) Согласованность с equals() o1.equals(o2) == (o1.compareTo(o2) == 0)

59Georgiy KorneevJava Advanced / Collections Framework Упорядоченные множества (1) Интерфейс SortedSet first() – минимальный элемент last() – максимальный элемент headSet(Object o) – подмножество элементов меньших o tailSet(Object o) – подмножество элементов больших либо равных o subSet(Object o1, Object o2) – подмножество элементов меньших o2 и больше либо равных o2 Класс TreeSet

60Georgiy KorneevJava Advanced / Collections Framework Упорядоченные множества (2) Интерфейс NavigableSet pollLast()– максимальный элемент lower(o) – максимальный элемент < данного floor(o) – максимальный элемент данного pollFirst() – минимальный элемент higher(o) – минимальный элемент > данного ceiling(o) – минимальный элемент данного descendingSet() – вид с обратным порядком Класс TreeSet

61Georgiy KorneevJava Advanced / Collections Framework Упорядоченные отображения (1) Интерфейс SortedMap firstKey() – минимальный ключ lastKey() – максимальный ключ headMap(Object o) – отображение ключей меньших o tailMap(Object o) – отображение ключей больших либо равных o subMap(Object o1, Object o2) – отображение ключей меньших o2 и больше либо равных o1 Класс TreeMap

62Georgiy KorneevJava Advanced / Collections Framework Упорядоченные отображения (2) Интерфейс NavigableMap {pollLast|lower|floor|first|higher| ceiling}Key – поиск ключа {pollLast|lower|floor|first|higher|ceiling}Entry – поиск пары descendingMap() – вид с обратным порядком

63Georgiy KorneevJava Advanced / Collections Framework Класс PriorityQueue Очередь с приоритетами Реализована на основе двоичной кучи

64Georgiy KorneevJava Advanced / Collections Framework Пример. Применение TreeSet Естественный порядок CollectionExample c = new CollectionExample( new TreeSet()); c.read(args[0]); c.dump(); Порядок без учета регистра CollectionExample c = new CollectionExample(new TreeSet(String.CASE_INSENSITIVE_ORDER)); int words = c.read(args[0]); c.dump();

Алгоритмы Часть 7

66Georgiy KorneevJava Advanced / Collections Framework Класс Collections Алгоритмы для работы с коллекциями Простые операции Перемешивание Сортировка Двоичный поиск Поиск минимума и максимума Специальные коллекции Оболочки коллекций

67Georgiy KorneevJava Advanced / Collections Framework Простые операции Заполнение списка указанным значением fill(List l, Object v) Переворачивание списка reverse(List l) Копирование из списка в список copy(List l1, List l2)

68Georgiy KorneevJava Advanced / Collections Framework Перемешивание Генерирует случайную перестановку Методы shuffle(List l) shuffle(List l, Random r)

69Georgiy KorneevJava Advanced / Collections Framework Сортировки Устойчивая сортировка Алгоритм – Merge Sort Методы sort(List l) – сортировка списка (естественный порядок) sort(List l, Comparator c) – сортировка списка (указанный порядок)

70Georgiy KorneevJava Advanced / Collections Framework Двоичный поиск Осуществляет двоичный поиск в списке Методы binarySearch(List l, Object o) – ищет o в списке binarySearch(List l, Object o, Comparator c) – ищет o в списке

71Georgiy KorneevJava Advanced / Collections Framework Поиск минимума и максимума Поиск минимума min(Collection c) – минимальный элемент (естественный порядок) min(Collection c, Comparator cmp) – минимальный элемент (указанный порядок) Поиск максимума max(Collection c) – максимальный элемент (естественный порядок) max(Collection c, Comparator cmp) – максимальный элемент (указанный порядок)

72Georgiy KorneevJava Advanced / Collections Framework Пример. Алгоритмы на списках List list = new ArrayList(); CollectionExample c = new CollectionExample(list); c.read(args[0]); Collections.reverse(list); Collections.shuffle(list); Collections.sort(list); Collections.sort(list, String.CASE_INSENSITIVE_ORDER); Collections.fill(list, "temp"); System.out.println(Collections.min(list)); System.out.println(Collections.min(list, String.CASE_INSENSITIVE_ORDER));

73Georgiy KorneevJava Advanced / Collections Framework Специальные коллекции Пустые коллекции emptySet() – пустое множество emptyList() – пустой список emptyMap() – пустое отображение Коллекции из одного элемента singleton(Object o) – множество singletonList(Object o) – список singletonMap(Object key, Object value) – отображение

74Georgiy KorneevJava Advanced / Collections Framework Оболочки коллекций Неизменяемые виды на коллекции unmodifiableSet(Set s) – неизменяемое множество unmodifiableSortedSet(SortedSet s) – неизменяемое упорядоченное множество unmodifiableList(List l) – неизменяемый список unmodifiableMap(Map m) – неизменяемое отображение unmodifiableSortedMap(SortedMap m) – неизменяемое упорядоченное отображени

75Georgiy KorneevJava Advanced / Collections Framework Класс Arrays Операции с массивами Сортировка Двоичный поиск Поиск минимума и максимума Заполнение Вид массива как списка List asList()

Устаревшие коллекции Часть 8

77Georgiy KorneevJava Advanced / Collections Framework Устаревшие коллекции Устаревшие коллекции являются синхронизированными Vector (ArrayList) Stack (ArrayList) Dictionary (Map) Hashtable (HashMap) Enumeration (Iterator)

Заключение Часть 9

79Georgiy KorneevJava Advanced / Collections Framework Структура Collections Framework (1)

80Georgiy KorneevJava Advanced / Collections Framework Структура Collections Framework (2)

81Georgiy KorneevJava Advanced / Collections Framework Ссылки Collections Framework // ections/index.html ections/index.html Collections Tutorial // ions/index.html ions/index.html Introduction to the Collections Framework // collections/ collections/

82Georgiy KorneevJava Advanced / Collections Framework Вопросы