1 Java 10. КОЛЛЕКЦИИ Основные концепции. Интерфейсы. Списки.

2 hashCode() This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable. Object#hashCode() - возвращает хэш-код объекта, (адрес объекта в памяти в шестнадцатеричном формате. Равные объекты (equals = true) должны иметь одинаковые хэш-коды. Разные объекты (equals = false) могут иметь одинаковые хэш-коды. При переопределении метода equals(), изменяется способ, которым сравниваются два объекта, и реализация Object's hashCode() становится не действительна. Поэтому, при переопределении метода equals(), необходимо также переопределить метод hashCode().

3 Общие определения Коллекции – это хранилища, поддерживающие различные способы накопления и упорядочения объектов с целью обеспечения возможностей эффективного доступа к ним. Они представляют собой реализацию абстрактных типов (структур) данных, поддерживающих три основные операции: добавление нового элемента в коллекцию; удаление элемента из коллекции; изменение элемента в коллекции. В качестве других операций могут быть реализованы: просмотреть элементы, подсчитать их количество и др.

4 Java1 и Java2+ Коллекции в языке Java объединены в библиотеке классов java.util и представляют собой контейнеры для хранения и манипулирования объектами. До появления Java 2 эта библиотека содержала классы только для работы с простейшими структурами данных: Vector, Stack, Hashtable, BitSet, а также интерфейс Enumeration для работы с элементами этих классов. Коллекции, появившиеся в Java 2, представляют общую технологию хранения и доступа к объектам. Скорость обработки коллекций повысилась по сравнению с предыдущей версией языка за счет отказа от их потокобезопасности. Если объект коллекции может быть доступен из различных потоков, следует использовать коллекции из Java 1.

5 Типизированные коллекции Одна из проблем, существовавших при работе с контейнерами до выхода Java SE5, заключалась в том, что компилятор позволял вставить в контейнер объект неверного типа. Такие ошибки при использовании нетипизированных коллекций выявляются на стадии выполнения, что повышает трудозатраты на исправление и верификацию кода. Начиная с версии 5.0 коллекции стали типизированными. Более удобным стал механизм работы с коллекциями: предварительное сообщение компилятору о типе ссылок, которые будут храниться в коллекции, при этом проверка осуществляется на этапе компиляции; отсутствие необходимости постоянно преобразовывать возвращаемые по ссылке объекты (тип Object) к требуемому типу. /* eck01 : Простой пример работы с контейнером: ApplesAndOrangesWithoutGenerics.java ApplesAndOrangesWithGenerics.java */

6 Элементы коллекций Структура коллекций характеризует способ, с помощью которого программы Java обрабатывают группы объектов. Так как Object – суперкласс для всех классов, то в коллекции можно хранить объекты любого типа, кроме базовых.

7 Основные концепции В библиотеке контейнеров Java проблема хранения объектов делится на две концепции, выраженные в виде базовых интерфейсов библиотеки: Коллекция: группа отдельных элементов, сформированная по некоторым правилам Класс List (список) хранит элементы в порядке вставки, в классе Set (множество) нельзя хранить повторяющиеся элементы, а класс Queue (очередь) выдает элементы в порядке, определяемом спецификой очереди. Карта: набор пар объектов «ключ-значение», с возможностью выборки по ключу. Класс Map (карта также встречаются термины ассоциативный массив и словарь) позволяет искать объекты по другим объектам например, получить объект значения по объекту ключа.

8 Интерфейсы коллекций Collection – вершина иерархии остальных коллекций; List – специализирует коллекции для обработки списков; Set – специализирует коллекции для обработки множеств, содержащих уникальные элементы; Map – карта отображения вида ключ-значение. Все классы коллекций реализуют также интерфейсы Serializable, Cloneable (кроме WeakHashMap). Кроме того, классы, реализующие интерфейсы List и Set, реализуют также интерфейс Iterable.

9 Интерфейс Collection В интерфейсе Collection определены методы, которые работают на всех коллекциях

10 Методы интерфейса Collection boolean add(E obj)добавляет obj к вызывающей коллекции возвращает true, если объект добавлен, и false, если obj уже элемент коллекции boolean addAll( Collection c) добавляет все элементы коллекции к вызывающей коллекции void clear()удаляет все элементы из коллекции boolean contains(Object obj)возвращает true, если вызывающая коллекция содержит элемент obj boolean equals(Object obj)возвращает true, если коллекции эквивалентны boolean isEmpty()возвращает true, если коллекция пуста

11 Методы интерфейса Collection Iterator iterator()извлекает итератор boolean remove(Object obj)удаляет obj из коллекции int size()возвращает количество элементов в коллекции Object[ ] toArray()копирует элементы коллекции в массив объектов T[ ] toArray(T a[ ])копирует элементы коллекции в массив объектов определенного типа /* eck02: Добавление групп элементов AddingGroups.java */

12 List Контейнеры List гарантируют определенный порядок следования элементов. Интерфейс List дополняет Collection несколькими методами, обеспечивающими вставку и удаление элементов в середине списка. Существует две основные разновидности List: Базовый контейнер ArrayList, оптимизированный для произвольного доступа к элементам, но с относительно медленнными операциями вставки (удаления) элементов в середине списка. Контейнер LinkedList, оптимизированный для последовательного доступа, с быстрыми операциями вставки (удаления) в середине списка; Произвольный доступ к элементам LinkedList выполняется относительно медленно, но по широте возможностей он превосходит ArrayList. Иерархия наследования списков рис.10.1

13 Методы интерфейса List void add(int index, E element)вставляет element в позицию, указанную в index void addAll( int index, Collection c) вставляет в вызывающий список все элементы коллекции с, начиная с позиции index E get(int index)возвращает элемент в виде объекта из позиции index int indexOf(Object ob)возвращает индекс указанного объекта E remove(int index)удаляет объект из позиции index E set(int index, E element)заменяет объект в позиции index, возвращает при этом удаляемый элемент List subList(int fromIndex, int toIndex) извлекает часть коллекции в указанных границах /* eck02: методы List: ListFeatures.java */

14 Интерфейсы для работы с элементами коллекции Для сравнения объектов: Comparator Для перечисления и доступа к объектам коллекции: Iterator ListIterator Map.Entry

15 Интерфейс Comparator Реализация интерфейса Comparator обеспечивает возможность сортировки списка объектов конкретного типа по правилам, определенным для этого типа. Для этого необходимо реализовать метод int compare(T ob1, T ob2) Этот метод автоматически вызывается методом public static void sort( List list) класса Collections /* eck03: CompareFeatures.java */

16 Итераторы У любого контейнера должен существовать механизм вставки и выборки элементов. Итератор это объект, обеспечивающий перемещение по последовательности объектов с выбором каждого объекта этой последовательности, при этом не надо знать или заботиться о лежащей в ее основе структуре. Итератор обычно является «легковесным» (light­weight) объектом: его создание должно обходиться без заметных затрат ресурсов. Ограничения: например, в Java Iterator поддерживает перемещение только в одном направлении.

17 Интерфейс Iterator Используется для построения объектов, которые обеспечивают доступ к элементам коллекции. К этому типу относится объект, возвращаемый методом iterator(). Такой объект позволяет просматривать содержимое коллекции последовательно, элемента за элементом. Позиции итератора располагаются в коллекции между элементами. В коллекции, состоящей из N элементов, существует N+1 позиций итератора. Итераторы унифицируют доступ к контейнерам

18 Методы интерфейса Iterator boolean hasNext() проверяет наличие следующего элемента, а в случае его отсутствия (завершения коллекции) возвращает false. Итератор при этом остается неизменным E next()возвращает объект, на который указывает итератор, и передвигает текущий указатель на следующий, предоставляя доступ к следующему элементу. Если следующий элемент коллекции отсутствует, то метод next() генерирует исключение NoSuchElementException; void remove()удаляет объект, возвращенный последним вызовом метода next() /* eck04: методы Iterator: SimpleIteration.java CrossContainerIteration.java*/

19 Интерфейс ListIterator ListIterator более мощная разновидность Iterator, поддерживаемая только классами List. E previous() int previousIndex() boolean hasPrevious() обеспечивают обратную навигацию по списку int nextIndex()возвращает номер следующего итератора void add(E obj)позволяет вставлять элемент в список текущей позиции void set(E obj)производит замену текущего элемента списка на объект, передаваемый методу в качестве параметра. /* eck04: методы ListIterator: ListIteration.java */

20 Контейнер LinkedList Класс LinkedList тоже реализует базовый интерфейс List, как и ArrayList, но выполняет некоторые операции (например, вставку и удаление в середине списка) более эффективно, чем ArrayList. И наоборот, операции произвольного доступа выполняются им с меньшей эффективностью. В отличие от массива, который хранит объекты в последовательных ячейках памяти, связанный список хранит объекты отдельно, но вместе со ссылками на следующее и предыдущее звенья последовательности. Класс LinkedList содержит методы, позволяющие использовать его в качестве стека(Stack), очереди (Queue) двусторонней очереди (Deque).

21 Доп. методы LinkedList интерфейс Queue void addFirst(E ob) добавляет элемент в начало void addLast(E ob)boolean offer(E o) добавляет элемент в конец E getFirst()E element() возвращает головной элемент NoSuchElementException для пустого списка E peek() возвращает головной элемент null, если очередь пуста E remove() возвращает и удаляет из очереди головной элемент NoSuchElementException для пустого списка E getLast() возвращает последний элемент E removeFirst() удалить первый E removeLast() удалить последний /* eck05 LinkedListFeatures.java */