Тема 5.9Краткий обзор коллекций

Пакет java.util содержит одно из наиболее захватывающих расширений Java 2 – коллекции.

Коллекция – это группа объектов. Добавление коллекций вызвало фундаментальные изменения в структуре и архитектуре многих элементов пакета java.util. Они также расширили круг задач, к которым может применяться пакет. Коллекции – современная технология, которая заслуживает внимания всех программистов Java.

В дополнение к коллекциям, java.util содержит большой выбор классов и интерфейсов, которые поддерживают широкий диапазон функциональных возможностей. Эти классы и интерфейсы используются повсюду в пакетах ядра Java, а также доступны для применения в пользовательских программах. Подобные приложения включают генерацию псевдослучайных чисел, манипулирование датой и временем, наблюдение за событиями, манипулирование наборами битов и синтаксический анализ строк. Из-за обширного набора свойств java.util– один из наиболее широко используемых пакетов Java.

Структура коллекций (collections framework) Java стандартизирует способ, с помощью которого ваши программы обрабатывают группы объектов. В прошлых версиях Java обеспечивал специальные классы типа Dictionary, Vector, Stack и Properties для хранения и манипулирования группами объектов. Хотя перечисленные классы были весьма полезны, они испытывали недостаток в централизованном, унифицирующем подходе при работе с группами объектов. Таким образом, способ использования класса vector, например, отличался от способа применения класса Properties. Кроме того, предыдущий специальный (ad hoc) подход не был предназначен длялегкого расширения и адаптации. Коллекции как раз явились ответом на эти (и другие) проблемы.

Структура коллекций была разработана для нескольких целей. Во-первых, структура должна была быть высокоэффективной. Действительно, реализации фундаментальных коллекций (динамических массивов, связанных списков, деревьев и хеш-таблиц) в структуре коллекций Java 2 высокоэффективны. Во-вторых, структура коллекций должна была позволить различным типам коллекций работать похожим друг на друга образом и с высокой степенью способности к взаимодействию. В-третьих, расширение и/или адаптация коллекции должна была быть простой.

Для удобства созданы различные реализации специального назначения, а также некоторые частичные реализации, которые упрощают создание собственного коллекционного класса. Наконец, были добавлены механизмы, которые позволяют интегрировать в структуру коллекций стандартные массивы.

Алгоритмы – другая важная часть механизма коллекций. Алгоритмы работают на коллекциях и определены как статические методы в классе Collections. Таким образом, они доступны для всех коллекций. Каждый коллекционный класс не нуждается в реализации своих собственных версий. Алгоритмы обеспечивают стандартные средства манипулирования коллекциями..

Другой элемент, созданный структурой коллекций, – это интерфейс Iterator. Итератор обеспечивает универсальный, стандартизированный способ доступа к элементам коллекции – по одному. Таким образом, итератор обеспечивает средства перечисления содержимого коллекции. Поскольку каждая коллекция интерфейс Iterator, к элементам любого коллекционного класса можно обращаться через методы этого интерфейса. Поэтому (и только с мелкими изменениями) код, который циклически проходит, скажем, через набор, может также использоваться для циклического прохода списка, например.

И последнее, если вы знакомы с C++, то полезно знать, что технология коллекций Java подобна (по духу) Стандартной Библиотеке Шаблонов (STL. Standard Template Library), определенной в C++. То, что C++ называет контейнером, Java называет коллекцией.

На рисунке 5.1 показана общая структура коллекций.

В структуре коллекций определено несколько интерфейсов. Начать с интерфейсов коллекции необходимо потому, что они определяют фундаментальный характер коллекционных классов. Иначе, конкретные классы просто являются различными реализациями стандартных интерфейсов. Интерфейсы, которые подкрепляют коллекции, кратко описаны в таблице 5.1.

Рисунок 5.1 – Структура коллекций

Таблица 5.1 Интерфейсы коллекций

Интерфейс	Описание
Collection	Дает возможность работать с группами объектов; он находится наверху всей иерархии коллекций
List	Расширяет Collection для обработки последовательностей (списков) объектов
Set	Расширяет Collection для обработки наборов (sets), которые должны содержать уникальные элементы
SortedSet	Расширяет Set для обработки сортированных наборов (sorted sets)

 

В дополнение к этим интерфейсам, коллекции используют также интерфейсы Comparator, Iterator и ListIterator.

Для обеспечения максимальной гибкости в использовании, некоторые методы в интерфейсах коллекций могут быть необязательными. Необязательные методы дают возможность изменить содержимое коллекции. Коллекции, которые поддерживают эти методы, называются изменяемыми(modifiable). Коллекции, которые не допускают изменения их содержимого, называются неизменяемыми (unmodifiable). Если сделана попытка использования одного из необязательных методов на неизменяемой коллекции, выбрасывается исключение UnsupportedOperationException. Все встроенные коллекции являются изменяемыми.

Интерфейс Collection– это основа, на которой сформирована структура коллекций. В нем объявляются основные методы, которые будут наследоваться всеми коллекциями. Эти методы описаны в таблице5.2. Поскольку все коллекции реализуют интерфейс Collection, знакомство с его методами необходимо для четкого понимания структуры коллекций. Некоторые из методов могут выбрасывать исключение UnsupportedOperationException. Это происходит, если коллекция не может быть изменена. Исключение ClassCastException генерируется тогда, когда один объект несовместим с другим, т. е. когда осуществляется попытка добавить к коллекции несовместимый объект.

Таблица5.2. Методы интерфейса Collection

Метод	Описание
boolean add(Object obj)	Прибавляет obj к вызывающей коллекции. Возвращает true, если obj был добавлен к коллекции, и false, если obj уже является элементом коллекции или если коллекция не допускает дубликатов
boolean addAll (Collection c)	Добавляет все элементы с к вызывающей коллекции. Возвращает true, если операция закончилась успешно (т. е. все элементы были добавлены). Иначе возвращает false
void clear ()	Удаляет все элементы из вызывающей коллекции
boolean contains(Object obj)	Возвращает true, если вызывающая коллекция содержит элемент obj. Иначе – false
boolean containsAll(Collection c)	Возвращает true, если вызывающая коллекция содержит все элементы с. Иначе – false
boolean equals(Object obj)	Возвращает true, если объект вызывающей коллекции и объект obj равны. Иначе – false
int hashCode()	Возвращает хэш-код вызывающей коллекции
boolean isEmpty()	Возвращает true, если вызывающая коллекция пуста. Иначе – false
Iterator iterator()	Возвращает итератор (iterator) для вызывающей коллекции
boolean remove(object obj)	Удаляет один экземпляр obj из вызывающей коллекции. Возвращает true, если элемент был удален. Иначе – false
boolean removeAll(Collection c)	Удаляет все элементы с из вызывающей коллекции. Возвращает true, если коллекция изменена (т. е. элементы были удалены). Иначе возвращает false
boolean retainAll(Collection c)	Удаляет все элементы из вызывающей коллекции, кроме элементов с. Возвращает true, если коллекция изменена (т. е. элементы были удалены). Иначе возвращает false
int size()	Возвращает число элементов, содержащихся в вызывающей коллекции
Object[ ] toArray()	Возвращает массив, который содержит все элементы, хранящиеся в вызывающей коллекции. Элементы массива являются копиями элементов коллекции
Object[ ] toArray(Object array[ ])	Возвращает массив, содержащий только те элементы коллекции, чей тип согласуется с типом элементов массива array. Элементы этого массива являются копиями элементов коллекции Если размер массива array равен количеству согласованных элементов, они возвращаются прямо в массиве array. Если размер array меньше, чем количество согласованных элементов, то распределяется и возвращается новый массив необходимого размера. Если размер array больше, чем количество согласованных элементов, элемент массива, следующий за последним элементом коллекции, устанавливается в null. Если любой элемент коллекции имеет тип, который не является подтипом массива array, то выбрасывается исключение ArrayStoreException.

 

Интерфейс List расширяет Collection и объявляет поведение коллекции, которая хранит последовательность элементов. Элементы могут быть вставлены или извлечены с помощью их позиций в списке через отсчитываемый от нуля индекс. Список может содержать дублированные элементы.

В дополнение к методам, определенным в Collection, интерфейс List определяет собственные методы, которые показаны в таблице5.3. Некоторые из этих методов выбрасывают исключения UnsupportedOperationException, если коллекция не может изменяться, и ClassCastException, когда один объект несовместим с другим, например, когда делается попытка добавить к коллекции несовместимый объект.

Таблица5.3 Методы интерфейса List

Метод	Описание
void add(int index, Object obj)	Вставляет obj в вызывающий список в позицию с индексом index. Любые элементы, существовавшие ранее в точке вставки или за ней, сдвигаются (т. е. никакие элементы не перезаписываются поверх уже существующих)
boolean addAll (int index, Collection c)	Вставляет все элементы с в вызывающий список с позиции(индекса! index. Любые элементы, существовавшие ранее в точке вставки или за ней, сдвигаются (т. е. никакие элементы не перезаписываются поверх уже существующих). Возвращает true, если вызывающий список изменяется, и false – иначе
Object get(int index)	Возвращает объект, хранящийся в индексной позиции index вызывающей коллекции
indexOf (Object obj)	Возвращает индекс (номер) первого экземпляра объекта obj в вызывающем списке. Если obj – не элемент списка, то возвращается -1
int lastlndexOf (Object obi)	Возвращает индекс последнего экземпляра obj в вызывающем списке. Если obj - не элемент списка, то возвращается -1
ListIterator listIterator()	Возвращает итератор, установленный к началу вызывающего списка
ListIterator listIterator(int index)	Возвращает итератор, установленный к позиции index вызывающего списка
Object remove(int index)	Удаляет элемент в позиции index из вызывающего списка и возвращает удаленный элемент. Результирующий список уплотняется (т. е. индексы последующих элементов уменьшаются на 1)
Object set(int index, Object obj)	Устанавливает объект obj S позицию, указанную в index, в вызывающем списке
List subList(int start, int end)	Возвращает список, который включает элементы от номера start до end-1 вызывающего списка. После этого вызывающий обьект будет ссылаться на элементы возвращенного (а не исходного)списка

 

Вызывая метод subList(), можно получить подсписок списка, указывая индексы (номера позиций) начала и окончания подсписка (в исходном списке). Использование этого метода обеспечивает очень удобную обработку списков.

Интерфейс Set расширяет интерфейс Collection и объявляет поведение коллекции, не допускающей дублирования элементов. Поэтому метол add() возвращает false, если осуществляется попытка добавить в набор дублирующие элементы. В Set не определяется никаких дополнительных собственных методов.

Интерфейс SortedSet расширяет Set и объявляет поведение набора, отсортированного в возрастающем порядке. В дополнение к методам, определенным в Set, интерфейс SortedSet объявляет методы, представленные в таблице 5.4.

Некоторые методы выбрасывают исключение NoSuchElementException, когда элементы не содержатся в вызывающем наборе. Исключение ClassCastException выбрасывается, когда объект несовместим с элементами набора, а исключение NuiiPointerException – если сделана попытка использовать null-объект1 (null-объекты недопустимы в наборе).

Таблица5.4 Методы интерфейса SortList

Метод	Описание
Comparator comparator()	Возвращает компаратор вызывающего сортированного набора. Если для этого набора используется естественное упорядочение, то возвращается null (пустая ссылка)
Object first ()	Возвращает первый элемент вызывающего сортированного набора
SortedSet headSet(Object end)	Возвращает SortedSet-объект, содержащий те элементы вызывающего сортированного набора, которые меньше, чем end. На эти элементы ссылается также и вызывающий объект
Object last()	Возвращает последний элемент вызывающего отсортированного набора
SortedSet subset(Objectstart, Object end)	Возвращает объект SortedSet, который содержит элементы, находящиеся между объектами start и end-1 вызывающего отсортированного списка. На эти элементы ссылается также и вызывающий объект
SortedSettailSet(Objectstart)	Возвращает объект SortedSet, который содержит элементы сортированного набора, больше чем или равные start-объекту. На элементы возвращенного набора ссылается также и вызывающий объект

 

После ознакомления с интерфейсами коллекций рассмотрим стандартные классы, которые их реализуют. Для некоторых классов обеспечены полные реализации, которые можно использовать непосредственно (т. е. сразу же приступая к созданию их экземпляров). Другие классы являются абстрактными и обеспечивают только схематические реализации, которые служат отправными точками для создания конкретных коллекций. Ни один из коллекционных клaccoв не синхронизирован, но можно получить и синхронные версии. Стандартные классы коллекций перечислены в таблице 5.5

Таблица 5.5 Стандартные классы коллекций

Класс	Описание
AbstractCollection	Реализует большую часть интерфейса Collection
AbstractList	Расширяет AbstractCollection и реализует большую масть интерфейса List
AbstractSequentiaList	Расширяет класс AbstractList для реализации коллекции, которая использует последовательный, а не произвольный доступ к ее элементам
LinkedList	Реализует связный список, расширяя класс AbstractSequentialList
ArrayList	Реализует динамический массив, расширяя класс AbstractList
AbstractSet	Расширяет класс AbstractCollection и реализует большую часть интерфейса Set
HashSet	Расширяет класс AbstractSet для реализации хеш-таблиц
TreeSet	Реализует набор, хранящийся в виде дерева (древовидный набор). Расширяет класс AbstractSet

 

5.9.1Класс ArrayList

Класс ArrayList расширяет AbstractList и реализует интерфейс List. ArrayList поддерживает динамические массивы, которые могут расти по мере необходимости. В Java стандартные массивы имеют фиксированную длину. После того как массивы созданы, они не могут расширяться или сжиматься, что означает, что вы должны знать заранее, сколько элементов массив будет содержать. Но, иногда, вы не можете знать до момента выполнения точного размера массива. Для обработки подобных ситуаций в структуре коллекцией определен класс ArrayList. По существу, он является массивом объектных ссылок переменной длины. To есть ArrayList можно динамически увеличивать или уменьшать в размере. Списки массивов создаются с некоторым начальным размером. Когда этот размер превышается, коллекция автоматически расширяется. Когда объекты удаляются, массив может быть сокращен.

ArrayList имеет следующие конструкторы:

ArrayList()

ArrayList (Collection с)

ArrayList (int capacity)

Первый конструктор строит пустой список массива. Второй – список массива, который инициализирован элементами коллекции с. Третий формирует спсиок с указанной начальной емкостью (capacity). Емкость – это размер(т.е. количество элементов) рассматриваемого массива, который служит для хранения указанного (в параметре capacity) количества элементов. Когда элементы добавляются к списку массива, емкость растет автоматически.

Листинг 5.12

import java.util.ArrayList;

public class Main {

public static void main(String[] args) {

ArrayList a = new ArrayList();

System.out.println(" Size " + a.size());

a.add(" 123" );

a.add(" hello" );

a.add(10);

System.out.println(" Size " + a.size());

System.out.println(a);

a.add(1, 100);

System.out.println(" Size " + a.size());

System.out.println(a);

a.remove(" 123" );

System.out.println(" Size " + a.size());

System.out.println(a);

}

}

Обратите внимание, что объект a создается пустым и растет по мере добавления в него элементов. При удалении элементов его размер уменьшается. В один ArrayList можно помещать объекты разных типов.

В результате выполнения данной программы получим:

Size 0

Size 3

[123, hello, 10]

Size 4

[123, 100, hello, 10]

Size 3

[100, hello, 10]

 

Задание:

Напишите методы пересечения и объединения двух коллекций.

 

5.9.2 Класс LinkedList

Класс LinkedList расширяет AbstractSequentialList и реализует интерфейс List. Oн обеспечивает структуру данных связного списка и имеет два следующих конструктора:

LinkedList ()

LinkedList (Collection с)

Первый конструктор строит пустой связный список, а второй создает связный список, инициализированный элементами коллекции с.

В дополнение к методам, которые он наследует, класс LinkedList определяет некоторые собственные полезные методы для манипулирования и доступа к спискам. Чтобы добавить Элемент в начало списка, используйте метод addFirst(), а для добавления элементов в конец списка вызывайте метод addLast():

void addFirst (Object obj)

void addLast (Object obj)

Здесь оbj – добавляемый элемент.

Чтобы получить первый элемент, вызовите метод getFirst (), а для извлечения последнего элемента – метод getLast():

ObjectgetFirst()

ObjectgetLast()

Для удаления первого элемента служит метод removeFirst(), а для удаления последнего – removeLast ():

Object removeFirst()

Object removeLast()

5.9.3 КлассHashSet

Класс HashSet расширяет AbstractSet и реализует интерфейс Set. Он создает коллекцию, которая использует хеш-таблицу для хранения коллекций. Хеш-таблица хранит информацию, используя механизм называемый хешированием. При хешировании информационное содержание ключа используется, чтобы определить уникальное значение, называемое его хэш-кодом. Затем хэш-код применяется как индекс (номер) элемента, в котором хранятся данные, связанные с ключом. Преобразование ключа в его хэш-код выполняется автоматически – вы никогда не видите сам хэш-код. Ваш код не может также прямо индексировать хеш-таблицу. Преимущество хеширования состоит в том, что оно сохраняет постоянным время выполнения основных операций, таких как add(), contains(), remove() и size() даже для больших наборов.

В классе определены следующие конструкторы:

HashSet()

HashSet(Collection с)

HashSet(int capacity)

HashSet (int capacity, float fillRatio)

Первая форма организует заданный по умолчанию хэш-набор. Вторая инициализирует хэш-набор, используя элементы с. Третья создает емкость хэш-набора величиной capacity. Четвертая форма инициализирует как емкость (capacity), так и отношение (коэффициент) заполнения (fillRatio), называемое также емкостью загрузки хэш-набора. Коэффициент заполнения должен быть между 0.0 и 1.0, и он определяет, насколько полным может быть хэш-набор, прежде чем он увеличивает свой размер. Когда число элементов больше, чем емкость хэш-набора, умноженная на его коэффициент заполнения, хэш-набор расширяется. Для конструкторов, которые не принимают коэффициент заполнения, используется множитель 0.75.

HashSet не определяет никаких дополнительных методов, кроме тех, что обеспечены его суперклассами и интерфейсами.

Важно обратить внимание, что хэш-набор не гарантирует упорядочивания его элементов, потому что процесс хеширования не предназначен для создания сортируемых наборов. Если вам нужна сортируемая память, то лучше выбрать другую коллекцию, такую как TreeSet.

Листинг 5.13

import java.util.HashSet;

public class Main {

public static void main(String[] args) {

HashSet a = new HashSet();

a.add(" 123" );

a.add(" hello" );

a.add(10);

a.add(5);

a.add(" A" );

System.out.println(a);

}

}

В результате выполнения данной программы получим:

[hello, A, 5, 123, 10]

 

5.9.4 Класс TreeSet

Класс TreeSet обеспечивает реализацию интерфейса Set и использует иерархическую (древовидную) структуру для хранения данных. Объекты.хранятcя в сортированном по возрастанию порядке. Время доступа и поиска в такой структуре не велико, что делает TreeSet превосходным выбором для хранения больших количеств сортированной информации, которая должна быть быстро найдена.

В классе определены следующие конструкторы:

TreeSet ()

TreeSet(Collection с)

TreeSet(Comparator comp)

TreeSet(SortedSetss)

Первая форма создает пустой древовидный набор, который будет сортироваться в восходящем порядке согласно естественному порядку его элементов. Вторая – формирует древовидный набор, который содержит элементы коллекции с. Третья форма создает пустой древовидный набор, который будет сортироваться в соответствии с компаратором comp. Четвертая – строит древовидный набор, который содержит элементы сортированного набора ss.

Листинг 5.14

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

TreeSet a = new TreeSet();

a.add(" 123" );

a.add(" hello" );

a.add(10);

a.add(5);

a.add(" A" );

System.out.println(a);

}

}

Если выполнить данный код, то получим:

Exception in thread " main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

at java.lang.Integer.compareTo(Integer.java: 52)

at java.util.TreeMap.put(TreeMap.java: 560)

at java.util.TreeSet.add(TreeSet.java: 255)

at javaapplication2.Main.main(Main.java: 9)

Данная ошибка возникла из-за того что невозможно отсортировать объекты разных классов, т.е. в TreeSet нужно помещать все объекты одного класса.

Листинг 5.15

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

TreeSet a = new TreeSet();

a.add(" 123" );

a.add(" hello" );

a.add(" people" );

a.add(" cat" );

a.add(" 10" );

TreeSet b = new TreeSet();

b.add(10);

b.add(5);

b.add(20);

b.add(1);

System.out.println(" a: " +a);

System.out.println(" b: " +b);

}

}

В ходе выполнения данной программы получим:

a: [10, 123, cat, hello, people]

b: [1, 5, 10, 20]

Видим, что объекты отсортировались в, так называемом, естественном порядке: строки – по алфавиту, числа – по возрастанию.

Естественный порядок сортировки можно задать для любого класса. Для этого достаточно реализовать параметризированный интерфейсComparable и его методpublicintcompareTo(Objecto). Данный метод возвращает число, но само число роли не играет. Важен знак этого числа. Минус соответствует знаку больше, плюс – меньше и 0 – равно.

Листинг 5.16

public class Circle implements Comparable< Circle> {

private int radius;

public Circle(int radius) {

this.radius = radius;

}

@Override

public String toString() {

return " Circle{" + " radius=" + radius + '}';

}

@Override

public int compareTo(Circle o) {

return this.radius - o.radius;

}

}

 

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

TreeSet< Circle> a = new TreeSet< Circle> ();

a.add(new Circle(5));

a.add(new Circle(3));

a.add(new Circle(10));

a.add(new Circle(15));

a.add(new Circle(2));

System.out.println(" a: " + a);

}

}

В результате выполнения данной программы получили:

a: [Circle{radius=2}, Circle{radius=3}, Circle{radius=5}, Circle{radius=10}, Circle{radius=15}]

Т.е. все объекты автоматически отсортировались по возрастанию радиуса.

 

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Популярное:

1. A.19. Противопожарная система
2. A.32.4.5.3. Система УСАВП: тест управления рекуперативным торможением
3. II. Поселение в Испании. Взаимоотношения вестготов и римлян. Королевская власть. Система управления. Церковная политика.
4. II. ТЕМАТИЧЕСКИЙ РАСЧЕТ ЧАСОВ
5. V. Письменно переведите текст и выпишите слова юридической тематики.
6. VII. ЛЕКСИКА ДРУГИХ АКТУАЛЬНЫХ ТЕМАТИЧЕСКИХ ГРУПП
7. А. Обзорно-аналитическое исследование.
8. АВАРИИ НА КОММУНАЛЬНЫХ СИСТЕМАХ ЖИЗНЕОБЕСПЕЧЕНИЯ
9. Автоматизированная система мониторинга вычислительной среды и обнаружения сетевых атак.
10. АВТОМАТИЧЕСКАЯ СИСТЕМА ОПОВЕЩЕНИЯ И ТУШЕНИЯ ПОЖАРА АСОТП ИГЛА-М.5К-Т И СКТБ
11. Административно-территориальное деление и система местного самоуправления США
12. Анализ исходных данных и разработка математической модели