Пакет java.util. Коллекции Интерфейсы List и ListIterator Интерфейс List Классы, реализующие этот интерфейс, содержат упорядоченную последовательность. - презентация

1 Пакет java.util. Коллекции Интерфейсы List и ListIterator Интерфейс List Классы, реализующие этот интерфейс, содержат упорядоченную последовательность объектов (объекты хранятся в том порядке, в котором они были добавлены). Интерфейс List расширяет интерфейс Collection, и любой класс, реализующий List, имеет все методы, определенные в Collection. В то же время определены новые методы, которые позволяют добавлять и удалять элементы из списка. Интерфейс-маркер RandomAccess предназначен для указания, что класс, реализующий список, предоставляет достаточно быстрые методы произвольного доступа к элементам коллекции. Абстрактный класс AbstractList представляет собой основу для реализации различных вариантов интерфейса List на основе массивов и, соответственно, произвольном доступе. Класс AbstractSequentialList предоставляет базовую реализацию интерфейса List, обеспечивая только последовательную обработку связанного списка элементов.

2 Пакет java.util. Коллекции Методы интерфейса List (1) voidadd( int index, E element )Добавляет указанный элемент в указанную позицию списка. booleanaddAll( int index, Collection c ) Вставляет все элементы указанной коллекции в заданную позицию этого списка. Если список изменился, то возвращается true, иначе возвращается false. Eget( int index )Возвращает элемент, находящийся на указанной позиции в данном списке. Если указанный индекс находится за границами списка, то выбрасывается исключение. intindexOf( Object o )Возвращается индекс первого вхождения указанного элемента в список или -1 при его отсутствии. intlastIndexOf( Object o )Возвращается индекс последнего вхождения указанного элемента в список или -1 при его отсутствии.

3 Пакет java.util. Коллекции Методы интерфейса List (2) ListIterator listIterator( )Возвращается объект, реализующий интерфейс java.util.ListIterator. ListIterator listIterator( int index )Возвращается объект, реализующий интерфейс java.util.ListIterator и обеспечивающий доступ к элементам подсписка, начинающегося с элемента с заданным индексом. Eremove( int index )Из списка удаляется элемент, находящийся на заданной позиции в списке. Возвращается удаленный элемент. Eset( int index, E element )Элемент, находящийся на заданной позиции в списке, заменяется заданным элементом. Возвращается удаленный элемент. List subList( int fromIndex, int toIndex ) Возвращается экземпляр интерфейса List, содержащий элементы данного списка, начиная с fromIndex и по toIndex.

4 Пакет java.util. Коллекции Интерфейс Iterator Интерфейс Iterator В Java 1 для перебора элементов коллекции использовался интерфейс Enumeration. Некоторые классы (в частности, реализующие интерфейс Map), предоставляют и методы, возвращающие реализацию интерфейса Enumeration, и методы, возвращающие коллекции, из которых можно получить реализацию более современного интерфейса. В Java 2 для этих целей должны применяться объекты, которые реализуют интерфейс Iterator. Все классы, которые реализуют интерфейс Collection, должны реализовать метод iterator( ), который возвращает объект, реализующий интерфейс Iterator. Интерфейс Iterator похож на Enumeration, с тем лишь отличием, что в нем определен метод remove(), который позволяет удалить объект из коллекции, для которой Iterator был создан. booleanhasNext()Возвращает true, если коллекция содержит еще хотя бы один необработанный элемент. Enext()Возвращает следующий элемент для обработки. voidremove()Удаляет из связанной коллекции элемент, который был возвращен последним вызовом метода next().

5 Пакет java.util. Коллекции Интерфейс ListIterator Специально для коллекций, являющихся списками, существует расширение интерфейса Iterator – ListIterator, обеспечивающий двунаправленное движение по списку. voidadd(E e)Вставляет элемент в список перед тем, который должен быть возвращен при следующем вызове метода next(). booleanhasNext()Возвращает true, если коллекция содержит еще хотя бы один необработанный элемент. booleanhasPrevious()Возвращает true, если коллекция содержит еще хотя бы один необработанный элемент в обратном направлении. Enext()Возвращает следующий элемент для обработки. intnextIndex()Возвращает индекс следующего элемента. Eprevious()Возвращает предыдущий элемент для обработки. intpreviousIndex()Возвращает индекс предыдущего элемента. voidremove()Удаляет из связанной коллекции элемент, который был возвращен последним вызовом метода next() или previous(). voidset(E e)Заменяет указанным элементом тот элемент в связанной коллекции, который был возвращен последним вызовом метода next() или previous().

6 Пакет java.util. Коллекции Интерфейс Queue Интерфейс Queue описывает очередь. Элементы могут добавляться в очередь только с одного конца, а извлекаться с другого (аналогично очереди в магазине). Интерфейс Queue унаследован от интерфейса Collection. Есть абстрактный класс AbstractQueue, содержащий базовую реализацию всех методов интерфейса. Специфические для очереди методы: Epoll()возвращает первый элемент и удаляет его из очереди (если очередь пуста, то возвращает null). Epeek()возвращает первый элемент очереди, не удаляя его(если очередь пуста, то возвращает null). booleanoffer(Object obj)добавляет в конец очереди новый элемент и возвращает true, если вставка удалась. Eelement()работает аналогично методy peek(), но если очередь пуста, то возбуждает исключение. Eremove()работает аналогично методу poll(), но если очередь пуста, то возбуждает исключение.

7 Пакет java.util. Коллекции Интерфейс Deque (1) Интерфейс Queue расширен интерфейсом Deque, который описывает двунаправленную очередь. Элементы могут и добавляться как в начало, так и в конец, и извлекаться и с обеих концов списка. Специфические для двунаправленной очереди методы: voidaddFirst( E e )Вставляет указанный элемент в начало очереди voidaddLast( E e )Вставляет указанный элемент в конец очереди Iterator descendingIterator( )Возвращает итератор, обеспечивающий перебор элементов очереди в обратном порядке EgetFirst( )Возвращает (не удаляя) первый элемент очереди (если список пуст, то возбуждается исключение NoSuchElementException) EgetLast( )Возвращает (не удаляя) последний элемент очереди (если список пуст, то возбуждается исключение NoSuchElementException) booleanofferFirst( E e )Вставляет указанный элемент в начало очереди, если это возможно без увеличения емкости списка и возвращает true. Если емкость исчерпана, то список не изменяется и возвращается false booleanofferLast( E e )Вставляет указанный элемент в конец очереди, если это возможно без увеличения емкости списка и возвращает true. Если емкость исчерпана, то список не изменяется и возвращается false

8 Пакет java.util. Коллекции Интерфейс Deque (2) EpeekFirst()Возвращает не удаляя первый элемент списка или null EpeekLast()Возвращает не удаляя последний элемент списка или null EpollFirst()Возвращает (и удаляет из списка) первый элемент или null EpollLast()Возвращает (и удаляет из списка) последний элемент или null Epop()Аналог метода pollFirst(), только при пустом списке выбрасывает исключение NoSuchElementException voidpush(E e)Аналог метода offerFirst(E e), только выбрасывает исключение IllegalStateException при отсутствии места (не выполняется автоматическое увеличение емкости) EremoveFirst()Аналог метода pollFirst(), только при пустом списке выбрасывает исключение NoSuchElementException booleanremoveFirstOccurrence(Object o)Удаляет первое вхождение указанного элемента из списка и возвращает true. Если элемента нет, возвращается false EremoveLast()Аналог метода pollLast(), только при пустом списке выбрасывает исключение NoSuchElementException booleanremoveLastOccurrence(Object o)Удаляет последнее вхождение указанного элемента из списка и возвращает true. Если элемента нет, возвращается false

9 Пакет java.util. Коллекции Интерфейсы *Map Интерфейс Map. Классы, которые реализуют этот интерфейс, хранят неупорядоченный набор объектов парами ключ/значение. Каждый ключ должен быть уникальным. Порядок следования пар ключ/значение не определен. В других языках коллекции такого типа называют ассоциативными массивами. Интерфейс Map не расширяет интерфейс Collection, а является полностью самостоятельным интерфейсом. Абстрактный класс AbstractMap представляет собой основу для реализации различных вариантов интерфейса Map. Интерфейс SortedMap. Этот интерфейс расширяет Map, требуя, чтобы содержимое коллекции было упорядочено по значениям ключей. Интерфейс NavigableMap - расширение SortedMap с неточным (приблизительным) доступом к элементу. Например, метод higherKey() возвращает наименьший ключ, который больше указанного.

10 Пакет java.util. Коллекции Методы интерфейса Map (1) voidclear( )Удаление всех пар "ключ-значение". booleancontainsKey( Object key ) Возвращает true, если отображение содержит пару с заданным ключом. booleancontainsValue( Object value ) Возвращает true, если отображение содержит одну или несколько пар с заданным значением. Set >entrySet( )Возвращает экземпляр интерфейса Set, содержащий все представления элементов отображения в виде интерфейсного типа Map.Entry. Vget( Object key )Возвращает значение, ассоциированное с заданным ключом или null, если в отображении нет пары с заданным ключом. inthashCode( )Возвращает хэш-код этого отображения. booleanisEmpty( )Возвращает true, если отображение пусто. entrySet( )Возвращает экземпляр интерфейса Set, содержащий все представления элементов отображения в виде интерфейсного типа Map.Entry. Vget( Object key )Возвращает значение, ассоциированное с заданным ключом или null, если в отображении нет пары с заданным ключом. inthashCode( )Возвращает хэш-код этого отображения. booleanisEmpty( )Возвращает true, если отображение пусто.">

11 Пакет java.util. Коллекции Методы интерфейса Map (2) Set keySet( )Возвращает экземпляр интерфейса Set, содержащий все ключи отображения. Vput( K key, V value )Добавляет пару "key-value" в данное отображение. Возвращает предыдущее значение, ассоциированное с заданным ключом или null. voidputAll( Map m ) Добавляет все пары заданного аргументом отображения, замещая значения при совпадении ключей. Vremove( Object key )Удаляет из отображения пару с заданным ключом. Возвращает удаленное значение, ассоциированное с заданным ключом или null, если пары не было. intsize( )Возвращает количество пар "ключ-значение". Collection values( )Возвращает коллекцию значений данного отображения.

12 Пакет java.util. Коллекции Взаимосвязь основных классов и интерфейсов, версия JDK 1.5 и 1.6 S

13 Пакет java.util. Классы коллекций (1) Элементами коллекций могут быть экземпляры любых классов (не могут быть переменные примитивных типов). Использование Generic's позволяет разрешать возможные коллизии на этапе компиляции. Класс ArrayList расширяет AbstractList, так же как и класс Vector (и его наследник Stack). Все три класса используют динамически расширяемые массивы для хранения списка элементов, предоставляя возможность быстрого произвольного доступа. Разница между ними состоит в том, что все методы классов Vector и Stack являются синхронизированными, а методы ArrayList (как и всех остальных классов-коллекций) – нет. Соответственно, ArrayList работает быстрее, однако при использовании его экземпляров несколькими потоками в многопоточных приложениях нужно заботиться о корректности последовательностей операций. Класс LinkedList - является другой реализацией интерфейса List. LinkedList является двухсвязным списком и позволяет перемещаться как от начала в конец списка, так и наоборот. Кроме методов интерфейса List в нем реализован еще ряд методов, которые позволяют добавлять, удалять и получать элементы в/из произвольной точке списка.

14 Пакет java.util. Классы коллекций (2) Классы HashSet и TreeSet, являясь реализациями интерфейса Set, обеспечивают уникальность каждого элемента коллекций (отсутствие дубликатов). Под уникальностью понимается различие значений, возвращаемых методом hashCode( ). При необходимости можно переопределять нужным образом этот метод, наследуемый любым классом от Object. Классы HashSet и TreeSet используют массивы для хранения указателей на объекты коллекции. В отличие от них класс LinkedHashSet строит двусвязный список элементов. Класс TreeSet поддерживает упорядоченность хранимого множества элементов, для чего используются интерфейсы Comparable и Comparator. Если при создании экземпляра TreeSet не был задан (в качестве аргумента конструктора) экземпляр интерфейса Comparator, то для сравнения любых двух элементов коллекции используется метод object1.compareTo( object2 ), иначе – метод указанного Comparator'a compare( object1, object2 ). Этот класс кроме приблизительного доступа к элементам позволяет получать subset'ы (от начала до заданного элемента, от заданного до конца и от одного заданного до другого).

15 Пакет java.util. Классы коллекций (3) PriorityQueue: - бесконечная очередь на основе структуры heap (куча). Методы не синхронизированы (нельзя использовать при одновременном доступе из нескольких потоков), но существует многопоточная реализация – PriorityBlockingQueue. Обход очереди выполняется в произвольном порядке. Для обхода кучи в порядке убывания/возрастания элементов можно использовать конструкцию Arrays.sort(priorityQueue.toArray()). ArrayDeque: - реализация двусвязной очереди на базе динамического массива. Методы не синхронизированы (нельзя использовать в нескольких потоках). Если был получен iterator или descendingIterator, а затем была изменена структура очереди, то будет выброшено исключение ConcurrentModificationException. Но это поведение не гарантируется при изменении структуры несколькими потоками.

16 Пакет java.util.concurrent Интерфейсы "параллельных" коллекций BlockingQueue: блокирующая очередь для передачи данных между потоками. Читающий поток будет остановлен, пока не появится хотя бы одна запись в очереди. Пишущий поток будет остановлен, если превышен предел количества элементов в очереди. Когда количество элементов станет меньше, он продолжит свою работу. Метод remainingCapacity - возвращает число свободных слотов. Существует 5 наборов методов для вставки и получения элементов: add(e), element(), remove() - добавить, достать, удалить. При запрете операции в данный момент (отсутствии элементов, или заполненности очереди) бросается исключение IllegalStateException. offer(e), poll() - добавить/извлечь элемент без блокировки потока. При запрете операции будет возвращен результат false или null offer(e, time, unit), poll(time, unit) - добавить/извлечь элемент c блокировкой не дольше заданного интервала put(e), take() - добавить/извлечь элемент c блокировкой потока drainTo(Collection) - извлечь все элементы из очереди и поместить в указанную коллекцию BlockingDeque: блокирующая двунаправленная очередь, для передачи данных между потоками. Аналогична BlockingQueue но позволяет добавлять и извлекать элементы с обоих концов. Имена методов имеют приставки: First - означает начало и Last - хвост очереди. Также есть методы removeFirstOccurrence(e)/removeLastOccurrence(e) - удаляющие первое или последнее вхождение данного элемента.

17 Пакет java.util.concurrent Классы "параллельных" коллекций (1) CopyOnWriteArrayList : - потоко-безопасный вариант ArrayList. Все операции, изменяющие структуру коллекции, применяются к новой копии существующего массива данных (для быстрого копирования используются нативные системные функции). Если один поток хочет читать данные из коллекции - он получает ее снимок и работает с возможно устаревшими данными, а другой поток в это время может безбоязненно изменять оригинал коллекции. Операции, связанные с изменением структуры коллекции, синхронизированы: в любой момент времени только один поток может изменять структуру данных. Операции связанные с чтением, не блокируют запись данных. Нельзя изменять структуру данного списка через итератор (так как итератор работает с более старым снимком данных). Операции итератора remove, set, add будут бросать UnsupportedOperationException. ConcurrentLinkedQueue: - бесконечная потокобезопасная очередь. Элементы хранятся в отдельных объектах (нодах), которые связываются посредством ссылок. Изменения структуры отслеживаются через класс AtomicReferenceFieldUpdater. Методы не синхронизированы, но структура этой очереди позволяет множеству потоков работать с одной и той же коллекцией безопасно.

18 Пакет java.util.concurrent Классы "параллельных" коллекций (2) ArrayBlockingQueue: блокирующая очередь на базе массива постоянной длины. Описывает классический буфер ограниченной длины для обмена данными между потоками. После создания нельзя изменить размер буфера. LinkedBlockingQueue: блокирующая очередь на базе связанного списка. Элементы хранятся в отдельных объектах (нодах), которые связываются посредством ссылок. Описывает буфер произвольной длины для обмена данными между потоками. При создании можно задать размер буфера, по умолчанию он неограничен. После создания изменять размер буфера нельзя. Очередь не ограничена, но можно нарваться на OutOfMemoryError. PriorityBlockingQueue: блокирующий вариант PriorityQueue. При создании можно задать размер буфера, по умолчанию он неограничен. После создания изменять размер буфера нельзя. Очередь не ограничена, но можно нарваться на OutOfMemoryError.

19 Пакет java.util.concurrent Классы "параллельных" коллекций (3) SynchronousQueue: блокирующая очередь, для синхронизации двух потоков. Аналог ArrayBlockingQueue с размером буфера 1. DelayQueue: неограниченная очередь, элементы которой становятся доступными другому потоку только по истечении заданного интервала времени. Каждому элементу задается свое время после которого он станет доступен для чтения. Очередь не ограничена, но можно нарваться на OutOfMemoryError. LinkedBlockingDeque: - Блокирующая двунаправленная очередь на базе связанного списка. Элементы хранятся в отдельных объектах (нодах), которые связываются посредством ссылок. Описывает буфер произвольной длины для обмена данными между потоками. При создании можно задать размер буфера, по умолчанию он неограничен. После создания изменять размер буфера нельзя. Очередь не ограничена, но можно нарваться на OutOfMemoryError.

20 Пакет java.util. Коллекции Взаимосвязь классов и интерфейсов *Map, версия JDK 1.5 и 1.6 S

21 Пакет java.util. Классы коллекций (4) Классы, реализующие интерфейс Map, отображают уникальные ключи в конкретные значения. Map - это коллекция пар ключ-значение, которая не может содержать дублированные ключи. Каждому ключу сопоставлено единственное значение, причем и ключи и значения могут быть любого объектного типа. HashMap – наиболее быстрый и простой способ реализации, основанный на использовании хеш-таблицы (которая, в свою очередь, реализуется с помощью массива и односвязного списка). Однако его элементы не находятся в каком-либо порядке. В нём разрешен один пустой ключ и много пустых значений. LinkedHashMap сохраняет порядок элементов, в котором они бы- ли добавлены, но требует дополнительных затрат времени при выполнении операций добавления и удаления элементов. В IdentityHashMap для сравнения объектов напрямую используются указатели на них. TreeMap реализуется на основе красно-черного (почти полностью сбалансированного) двоичногодерева. TreeMap хранит свои элементы в отсортированном порядке, операции доступа и модификации выполняются за время, пропорциональное log2n.

22 Пакет java.util. Классы коллекций (5) Класс WeakHashMap использует так называемые "слабые" ссылки, позволяющие сборщику мусора при необходимости утилизировать объекты (вместе со ссылками на них), если на эти объекты не указывают "жесткие", т.е. обычные ссылки. Этот класс можно эффективно использовать например для хранения коллекции слушателей событий. Существуют еще "мягкие" и "фантомные" ссылки, для их реализации есть пакет java.lang.ref. Пакет java.util начиная с версии 1.5 содержит два узко специализированных класса EnumSet и EnumMap, в которых в качестве ключей используются значения из перечислений. Это может быть удобно для ряда конкретных прикладных задач. Dictionary (словарь) – абстрактный класс, представляющий собой хранилище информации типа ключ-значение. И этот класс, и все его подклассы (Hashtable, Properties) следует считать устаревшими и использовать вместо них классы/интерфейсы *Map. Hashtable – это подкласс Dictionary, являющийся конкретной реализацией словаря. Все его методы синхронизированы. Properties – подкласс Hashtable, в который для удобства использования добавлено несколько методов, позволяющих читать из файла/писать в файл всю коллекцию разом (в виде строк = ) и получать значения, которые, возможно, не определены в таблице. В частности, в методе getProperty( ) вместе с именем можно указывать значение по умолчанию: getРrореrtу( "key", "default_value" );

23 Пакет java.util.concurrent Интерфейсы и классы "параллельных" отображений Интерфейс ConcurrentMap: карта, предоставляющая атомарные операции putIfAbsent( ), remove( ), replaсe( ). Возвращают true - если операция изменила данные, иначе false. Интерфейс ConcurentNavigableMap -расширяет интерфейс NavigableMap, возвращая результатом операций тип ConcurentNavigableMap вместо NavigableMap. Класс ConcurrentHashMap - более новая реализация Hashtable. Все методы имеют ту же сигнатуру, поэтому можно просто заменить Hashtable на ConcurentHashMap. Все операции потокобезопасны. Операции извлечения данных не блокируют потоки выполнения, и возвращают согласованные данные (относительно завершившихся операций по изменению данных). Операции по изменению данных блокируют только часть таблицы (грубо говоря, нельзя одновременно изменять один элемент, но разные можно). Операции по изменению набора данных типа putAll( ), clear( ) на время своей работы блокируют ограниченные сегменты коллекции, но не всю таблицу. Операции для работы с набором данных putAll( ), clear( ) не атомарны. При создании можно указать concurrencyLevel – требуемое число одновременно работающих потоков. Таблица будет разбита на соответствующее число сегментов (по умолчанию на 16).

24 Пакет java.util. Коллекции Сравнение коллекций Коллекциядобавлениевыборкаудаление Vector Stack ArrayList ArrayDeque PriorityQueue HashSet LinkedHashSet TreeSet LinkedList HashMap IdentityHashMap LinkedHashMap WeakHashMap TreeMap Hashtable Properties