Класс Hashtable

Класс Hashtable расширяет абстрактный класс Dictionary. В объектах этого класса хранятся пары "ключ — значение". Их можно представить себе как таблицу из двух столбцов. Такие таблицы часто называют словарями или ассоциативными массивами.

Из таких пар "Фамилия И. О. — номер телефона" состоит, например, телефонный справочник.

Еще один пример — анкета. Ее можно представить как совокупность пар "Фамилия — Иванов", "Имя — Петр", "Отчество — Сидорович", "Год рождения — 1975" и т. д.

Подобных примеров можно привести множество.

Каждый объект класса Hashtable кроме размера (size) — количества пар, имеет еще две характеристики: емкость (capacity) — размер буфера, и показатель загруженности (load factor) — процент заполненности буфера, по достижении которого увеличивается емкость таблицы.

Как создать таблицу Hashtable

Для создания объектов класс Hashtable предоставляет четыре конструктора:

□ Hashtable () — создает пустой объект с начальной емкостью в 101 элемент и показателем загруженности 0,75;

□ Hashtable (int capacity) -формирует пустой объект с начальной емкостью capacity и

показателем загруженности 0,75;

□ Hashtable (int capacity, float loadFactor) — создает пустой объект с начальной емкостью capacity и показателем загруженности loadFactor;

□ Hashtable (Map f) — создает объект класса Hashtable, содержащий все элементы отображения f, с емкостью, равной удвоенному числу элементов отображения f, но не менее 11, и показателем загруженности 0,75.

Если предполагается хранить в таблице пары определенных типов, то эти типы можно указать заранее при создании таблицы. Для этого в угловых скобках в шаблоне (generics) коренного типа записываются конкретные типы по такой схеме:

Hashtable h = new Hashtable();

или, используя "ромбовидный оператор",

Hashtable h = new Hashtable<>();

После такого определения компилятор будет следить за типами заносимых в таблицу элементов. Извлечение элементов из таблицы не потребует явного приведения типов.

Как заполнить таблицу Hashtable

Для заполнения объекта класса Hashtable используются два метода:

□ Object put(Object key, Object value) — добавляет пару "key — value", если ключа key не было в таблице, и меняет значение value ключа key, если он уже есть в таблице. Возвращает старое значение ключа или null, если его не было. Если хотя бы один аргумент равен null, возникает исключительная ситуация;

□ void putAll (Map f) — добавляет все элементы отображения f.

В объектах-ключах key должны быть переопределены методы hashCode() и equals ( ), унаследованные от класса Object.

Как получить значение по ключу

Метод get (Object key) возвращает значение элемента с ключом key в виде объекта класса Obj ect или того класса, с которым создана таблица. Если при создании таблицы класс не был указан, то для дальнейшей работы с полученным объектом его следует преобразовать к конкретному типу.

Как узнать наличие ключа или значения

Логический метод containsKey(Object key) возвращает true, если в таблице есть ключ

key.

Логический метод containsValue(Object value) или старый метод contains(Object value) возвращают true, если в таблице есть ключи со значением value.

Логический метод isEmpty() возвращает true, если в таблице нет элементов.

Как получить все элементы таблицы Hashtable

Метод values ( ) представляет все значения value таблицы в виде объекта типа Collection. Все модификации в этом объекте изменяют таблицу, и наоборот.

Метод keySet () предоставляет все ключи key таблицы в виде объекта типа интерфейса Set. Все изменения в этом объекте типа Set корректируют таблицу, и наоборот.

Метод entrySet () представляет все пары "key — value" таблицы в виде объекта типа интерфейса Set. Все модификации в этом объекте типа Set изменяют таблицу, и наоборот.

Итак, таблицу типа Hashtable можно представить в трех формах: в виде коллекции значений, в виде множества ключей или в виде множества пар.

Метод toString () возвращает строку, содержащую все пары таблицы.

Старые методы elements () и keys () возвращают значения и ключи в виде интерфейса

Enumeration.

Как удалить элементы

Метод remove (Obj ect key) удаляет пару с ключом key, возвращая значение этого ключа, если оно есть, и null, если пара с ключом key не найдена.

Метод clear () удаляет все элементы, очищая таблицу.

В листинге 6.3 показано, как можно использовать класс Hashtable для создания телефонного справочника, а на рис. 6.1 — вывод этой программы.

Листинг 6.3. Телефонный справочник

import java.util.*; class PhoneBook{

public static void main(String[] args){

Hashtable yp = new Hashtable<>();

String name = null;

yp.put("John", "123-45-67");

yp.put("Lennon", "567-34-12");

yp.put("Bill", "342-65-87");

yp.put("Gates", "423-83-49");

yp.put("Batman", "532-25-08");

try{

name = args[0];

}catch(Exception e){

System.out.println("Usage: j ava PhoneBook Name"); return;

}

if (yp.containsKey(name))

System.out.println(name + "’s phone = " + yp.get(name));

else

System.out.println("Sorry, no such name");

}

}

Класс Properties

Класс Properties расширяет класс Hashtable таким образом, что в нем хранятся пары ссылок не на произвольный тип, а на строки — пары типа String. Он предназначен в основном для работы с парами "свойства системы — их значения", записанными в файлах свойств.

В классе Properties два конструктора:

□ Properties () — создает пустой объект;

□ Properties (Properties default) — создает объект с заданными парами свойств default.

Кроме унаследованных от класса Hashtable методов в классе Properties есть еще следующие методы:

□ два метода, возвращающих значение ключа-строки в виде строки:

• String getProperty(String key) — возвращает значение по ключу key;

• String getProperty(String key, String defaultValue) — возвращает значение по ключу key; если такого ключа нет, возвращается defaultValue;

□ метод setProperty(String key, String value) добавляет новую пару, если ключа key нет, и меняет значение, если ключ key есть;

□ метод load(inputStream in) загружает свойства из входного потока in;

□ методы list (PrintStream out) и list(PrintWriter out) выводят свойства в выходной поток out;

□ метод store (OutputStream out, String header) выводит свойства в выходной поток out с заголовком header.

Очень простой листинг 6.4 и рис. 6.2 демонстрируют вывод всех системных свойств Java.

Листинг 6.4. Вывод системных свойств

class Prop{

public static void main(String[] args){

System.getProperties().list(System.out);

}

}

Примеры классов Vector, Stack, Hashtable, Properties показывают удобство классов-коллекций. Такое удобство и необходимость в коллекциях разных видов привели к тому, что для Java была разработана целая иерархия коллекций, получившая название Java Collections Framework. Она показана на рис. 6.3. Курсивом записаны имена интерфейсов. Пунктирные линии указывают классы, реализующие эти интерфейсы.

Все коллекции разбиты на четыре группы, описанные в интерфейсах List, Set, Queue и Map.

Примером реализации интерфейса List может служить описанный ранее класс Vector, примером реализации интерфейса Map — класс Hashtable.

Коллекции List, Set и Queue имеют много схожего, поэтому их общие методы вынесены в отдельный суперинтерфейс Collection.

Object

—AbstractCollection ■* Collection

—AbstractList Ч- - - - ^

^Vector -*r - ~

L Stack

—AbstractSet 4----- = = - Set—

—HashSet ~ ~

L LinkedHashSet

_ TreeSet __ SortedSet —

NavigableSet

—AbstractQueue -4- ----- - Queue -ArrayBlockingQueue BlockingQueue

- ConcurrentLinkedQueue

- DelayQueue

- LinkedBlockingQueue

- PriorityBlockingQueue

- PriorityQueue n

eq ue

^LinkedBlockingDeque BlockingDeque-J

_ ArrayDeque

Рис. 6.3. Иерархия классов и интерфейсов-коллекций

Интерфейс Map не входит в эту иерархию — по мнению разработчиков Java Collections Framework, отображения типа Map не являются коллекциями. Они показаны на рис. 6.4.

Object

Map

РЈ

РЈ

SortedMap —

' NavigableMap J

Map.Entry

-AbstractMap -4- — — — HashMap

L- LinkedHashMap -4-WeakHashMap —TreeMap _

-Arrays

Bitset ^

Collections

Dictionary — Hashtable — Properties

Рис. 6.4. Иерархия классов и интерфейсов-отображений

Все интерфейсы, входящие в Java Collections Framework, — настраиваемые (см. главу 4), их можно использовать как шаблоны классов, хранящих ссылки на элементы одного и того же типа.

Посмотрим, что, по мнению разработчиков Java API, должно содержаться в этих коллекциях.

Интерфейс Collection

Интерфейс Collection из пакета java.util описывает общие свойства коллекций List, Set и Queue. Он содержит методы добавления и удаления элементов, проверки и преобразования элементов:

□ boolean add (Obj ect obj) — добавляет элемент obj в конец коллекции; возвращает false, если такой элемент в коллекции уже есть, а коллекция не допускает повторяющиеся элементы; возвращает true, если добавление прошло удачно;

□ boolean addAll(Collection coll) - добавляет все элементы коллекции coll в конец

данной коллекции;

□ void clear () — удаляет все элементы коллекции;

□ boolean contains(Object obj) — проверяет наличие элемента obj в коллекции;

□ boolean containsAll(Collection coll) — проверяет наличие всех элементов коллекции coll в данной коллекции;

□ boolean isEmpty() — проверяет, пуста ли коллекция;

□ Iterator iterator () — возвращает итератор данной коллекции;

□ boolean remove (Obj ect obj) — удаляет указанный элемент из коллекции; возвращает false, если элемент не найден, true, если удаление прошло успешно;

□ boolean removeAll(Collection coll) - удаляет элементы указанной коллекции, лежа

щие в данной коллекции;

□ boolean retainAll(Collection coll) -удаляет все элементы данной коллекции, кроме

элементов коллекции coll;

□ int size() — возвращает количество элементов в коллекции;

□ Obj ect [ ] toArray () — возвращает все элементы коллекции в виде массива;

□ Obj ect [ ] toArray (Obj ect[] a) — записывает все элементы коллекции в массив a, если в нем достаточно места.

Интерфейс List

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

Класс Vector — одна из реализаций интерфейса List.

Интерфейс List добавляет к методам интерфейса Collection методы, использующие индекс index элемента:

□ void add (int index, Object obj) - вставляет элемент obj в позицию index; старые

элементы, начиная с позиции index, сдвигаются, их индексы увеличиваются на единицу;

□ boolean addAll(int index, Collection coll) — вставляет все элементы коллекции coll;

□ Object get(int index) возвращает элемент, находящийся в позиции index;

□ int indexOf (Obj ect obj) — возвращает индекс первого появления элемента obj в коллекции;

□ int lastIndexOf (Object obj) — возвращает индекс последнего появления элемента obj в коллекции;

□ Listiterator listiterator() — возвращает итератор коллекции;

□ ListIterator listIterator(int index) — возвращает итератор конца коллекции от позиции index;

□ Object set (int index, Object obj ) - заменяет элемент, находящийся в позиции index,

элементом obj ;

□ List subList (int from, int to) - возвращает часть коллекции от позиции from вклю

чительно до позиции to исключительно.

Интерфейс Set

Интерфейс Set из пакета java.util, расширяющий интерфейс Collection, описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Это соответствует математическому понятию множества (set). Такие коллекции удобны для проверки наличия или отсутствия у элемента свойства, определяющего множество. Новые методы в интерфейс Set не добавлены, просто метод add () не станет добавлять еще одну копию элемента, если такой элемент уже есть в множестве.

Этот интерфейс расширен интерфейсом SortedSet.

Интерфейс SortedSet

Интерфейс SortedSet из пакета java.util, расширяющий интерфейс Set, описывает упорядоченное множество, отсортированное по естественному порядку возрастания его элементов или по порядку, заданному какой-либо реализацией интерфейса Comparator.

Элементы не нумеруются, но есть понятие первого, последнего, большего и меньшего элемента.

Дополнительные методы интерфейса отражают эти понятия:

□ Comparator comparator () — возвращает способ упорядочения коллекции;

□ Object first () — возвращает первый, меньший элемент коллекции;

□ SortedSet headSet(Object toElement) — возвращает начальные, меньшие элементы до элемента toElement исключительно;

□ Object last () — возвращает последний, больший элемент коллекции;

□ SortedSet subSet(Object fromElement, Object toElement) — возвращает подмножество коллекции от элемента fromElement включительно до элемента toElement исключительно;

□ SortedSet tailSet(Object fromElement) — возвращает последние, большие элементы коллекции от элемента fromElement включительно.

Интерфейс NavigableSet

Интерфейс NavigableSet из пакета java.util, расширяющий интерфейс SortedSet, описывает отсортированное множество, в котором можно организовать бинарный поиск.

Чтобы осуществить это, в интерфейсе описаны методы, позволяющие для каждого данного элемента множества найти ближайший больший и ближайший меньший элементы

того же множества.

Методы возвращают null, если элемент не удалось найти:

□ Object lower (Object elem) — возвращает ссылку на наибольший элемент множества, меньший данного элемента elem;

□ Object floor (Object elem) — возвращает ссылку на наибольший элемент множества, меньший или равный данному элементу elem;

□ Object higher (Object elem) — возвращает ссылку на наименьший элемент множества, больший данного элемента elem;

□ Object ceiling (Obj ect elem) — возвращает ссылку на наименьший элемент множества, больший или равный данному элементу elem.

Следующие методы позволяют выделить отсортированное подмножество:

в–Ў NavigableSet subSet(Object fromElement, boolean frominclusive, Object toElement,

boolean toinclusive) - возвращает подмножество коллекции от элемента fromElement

включительно, если frominclusive == true, или исключительно, если

frominclusive == false, до элемента toElement включительно или исключительно в зависимости от истинности последнего параметра toinclusive;

□ NavigableSet headSet(Object toElement, boolean inclusive) — возвращает начальные, меньшие элементы до элемента toElement включительно или исключительно в зависимости от истинности параметра inclusive;

□ NavigableSet tailSet(Object fromElement, boolean inclusive) — возвращает последние, большие элементы коллекции от элемента fromElement включительно или исключительно в зависимости от истинности параметра inclusive.

Наконец, два метода удаляют наименьший и наибольший элементы множества:

□ Object pollFirst () — возвращает ссылку на наименьший элемент множества и удаляет его;

□ Obj ect pollLast () — возвращает ссылку на наибольший элемент множества и удаляет его.

Интерфейс Queue

Интерфейс Queue из пакета java.util, расширяющий интерфейс Collection, описывает методы работы с очередями. Очередью называется коллекция, элементы в которую добавляются с одного конца, а удаляются с другого конца. Хороший пример такой коллекции — обычная житейская очередь в магазине или на автобусной остановке. Такой порядок обработки называется FIFO (First In — First Out, первым пришел — первым ушел).

Интерфейс Queue добавляет к методам интерфейса Collection методы, характерные для очередей:

□ Object element () — возвращает первый элемент очереди, не удаляя его из очереди. Метод выбрасывает исключение, если очередь пуста;

□ Object peek() — возвращает первый элемент очереди, не удаляя его. В отличие от метода element () не выбрасывает исключение;

□ Object remove() — возвращает первый элемент очереди и удаляет его из очереди. Метод выбрасывает исключение, если очередь пуста;

□ Object poll () — возвращает первый элемент очереди и удаляет его из очереди. В отличие от метода remove () не выбрасывает исключение;

□ boolean offer(Object obj) - вставляет элемент в конец очереди и возвращает true,

если вставка удалась.

Интерфейс BlockingQueue

Интерфейс BlockingQueue из пакета java.util.concurrent, расширяющий интерфейс Queue, описывает очередь, с которой работают одновременно несколько подпроцессов, вставляющих и удаляющих элементы. Их работа организуется таким образом, чтобы подпроцесс, пытающийся забрать элемент из пустой очереди, ждал, когда другой подпроцесс занесет в нее хотя бы один элемент. Подпроцесс, ставящий элемент в очередь, ждет, когда для него освободится место, если очередь уже переполнена.

Для организации такой совместной работы добавлены следующие методы:

□ Obj ect take () — возвращает и удаляет первый элемент, ожидая поступления элемента, если очередь пуста;

□ void put (Object element) — ставит элемент element в очередь, ожидая уменьшения очереди, если она переполнена;

□ int drainTo(Collection coll, int num) — удаляет по крайней мере num элементов из очереди, переписывая их в коллекцию coll, и возвращает их фактическое количество;

□ int drainTo(Collection coll) — удаляет все доступные элементы из очереди, переписывая их в коллекцию coll и возвращая их количество.

Интерфейс Deque

Интерфейс Deque (double ended queue) из пакета java.util, расширяющий интерфейс Queue, описывает методы работы с разновидностью очередей, называемой деком, у которого элементы вставляются и удаляются с обоих концов.

Интерфейс Deque добавляет к методам интерфейса Queue методы, характерные для дека:

□ Object getFirst () — возвращает первый элемент дека, не удаляя его из дека. Эквивалентен методу element () интерфейса Queue. Метод выбрасывает исключение, если дек пуст;

□ Object getLast () — возвращает последний элемент дека, не удаляя его из дека. Метод выбрасывает исключение, если дек пуст;

□ Object peekFirst () — возвращает первый элемент дека, не удаляя его. Эквивалентен методу peek () интерфейса Queue. Не выбрасывает исключение;

□ Object peekLast () — возвращает последний элемент дека, не удаляя его. Не выбрасывает исключение;

□ void addFirst(Object obj) — вставляет элемент в начало дека;

□ void addLast (Obj ect obj) — вставляет элемент в конец дека. Эквивалентен методу add () интерфейса Collection;

□ boolean offerFirst (Object obj ) - вставляет элемент в начало дека и возвращает true,

если вставка удалась;

□ boolean offerLast(Object obj) - вставляет элемент в конец дека и возвращает true,

если вставка удалась. Эквивалентен методу offer() интерфейса Queue;

□ Object removeFirst() — возвращает первый элемент дека и удаляет его из дека. Эквивалентен методу remove () интерфейса Queue. Метод выбрасывает исключение, если дек пуст;

□ Object removeLast() — возвращает последний элемент дека и удаляет его из дека. Метод выбрасывает исключение, если дек пуст;

□ Object pollFirst () — возвращает первый элемент дека и удаляет его из дека. Эквивалентен методу poll () интерфейса Queue. В отличие от метода removeFirst ( ) не выбрасывает исключение;

□ Object pollLast() — возвращает последний элемент дека и удаляет его из дека. В отличие от метода removeLast () не выбрасывает исключение;

□ boolean removeFirstOccurrence(Object obj) — удаляет первый встретившийся элемент obj дека и возвращает true, если удалось это сделать. Метод выбрасывает исключение, если дек пуст;

□ boolean removeLastOccurrence(Object obj) — удаляет последний встретившийся элемент obj из дека и возвращает true, если удалось это сделать. Метод выбрасывает исключение, если дек пуст.

Интерфейс BlockingDeque

Интерфейс BlockingQueue из пакета java.util.concurrent, расширяющий интерфейсы Queue

и Deque, описывает дек, с которым работают одновременно несколько подпроцессов,

вставляющих и удаляющих элементы. Их работа организуется таким образом, чтобы

подпроцесс, пытающийся забрать элемент из пустого дека, ждал, когда другой подпро-

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

Для организации такой совместной работы добавлены следующие методы:

□ Object takeFirst() — возвращает и удаляет первый элемент, ожидая поступления элемента, если дек пуст. Эквивалентен методу take () интерфейса BlockingQueue;

□ Obj ect takeLast () — возвращает и удаляет последний элемент, ожидая поступления элемента, если дек пуст;

□ void putFirst(Object element) - вставляет элемент element в начало дека, ожидая

уменьшения дека, если он переполнен. Эквивалентен методу put() интерфейса

BlockingQueue;

□ void putLast (Obj ect element) - вставляет элемент element в конец дека, ожидая

уменьшения дека, если он переполнен.

Интерфейс Map

Интерфейс Map из пакета java.util описывает своеобразную коллекцию, состоящую не из элементов, а из пар "ключ — значение". У каждого ключа может быть только одно значение, что соответствует математическому понятию однозначной функции, или отображения (map).

Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associative array).

Обычный массив — простейший пример словаря с заранее заданным числом элементов. Это отображение множества первых неотрицательных целых чисел на множество элементов массива, множество пар "индекс массива — элемент массива".

Класс Hashtable — одна из реализаций интерфейса Map.

Интерфейс Map содержит методы, работающие с ключами и значениями:

□ boolean containsKey(Object key) — проверяет наличие ключа key;

□ boolean containsValue(Object value) — проверяет наличие значения value;

□ Set entrySet () — представляет коллекцию в виде множества с элементами в виде пар из данного отображения, с которыми можно работать методами вложенного интерфейса Map.Entry;

□ Object get (Object key) -возвращает значение, отвечающее ключу key;

□ Set keyset () — представляет ключи коллекции в виде множества;

□ Object put(Object key, Object value) — добавляет пару "key — value", если такой пары не было, и заменяет значение ключа key, если такой ключ уже есть в коллекции;

□ void putAll (Map m) — добавляет к коллекции все пары из отображения m;

□ Collection values () — представляет все значения в виде коллекции.

В интерфейс Map вложен интерфейс Map.Entry, содержащий методы работы с отдельной парой отображения.

Вложенный интерфейс Map.Entry

Этот интерфейс описывает методы работы с парами, полученными методом entrySet ():

□ методы getKey () и getValue () позволяют получить ключ и значение пары;

□ метод setvalue(Object value) меняет значение в данной паре.

Интерфейс SortedMap

Интерфейс SortedMap, расширяющий интерфейс Map, описывает упорядоченную по ключам коллекцию Map. Сортировка производится либо в естественном порядке возрастания ключей, либо в порядке, описываемом в интерфейсе Comparator.

Элементы не нумеруются, но есть понятия большего и меньшего из двух элементов, первого, самого маленького, и последнего, самого большого элемента коллекции. Эти понятия описываются следующими методами, возвращающими:

□ Comparator comparator ( ) -способ упорядочения коллекции;

□ Object firstKey () — первый, меньший элемент коллекции;

□ SortedMap headMap(Object toKey) - начало коллекции до элемента с ключом toKey ис

ключительно;

□ Object lastKey() — последний, больший ключ коллекции;

□ SortedMap subMap(Object fromKey, Object toKey) — часть коллекции от элемента с ключом fromKey включительно до элемента с ключом toKey исключительно;

□ SortedMap tailMap(Object fromKey) - остаток коллекции, начинающийся от элемента

fromKey включительно.

Интерфейс NavigableMap

Интерфейс NavigableMap из пакета java.util, расширяющий интерфейс SortedMap, описывает отсортированное по ключам отображение, в котором можно организовать бинарный поиск.

Чтобы осуществить это, в интерфейсе описаны методы, позволяющие для каждой данной пары из отображения получить ссылки на меньшую и большую ее пары или на ключ такой пары. Они возвращают null, если ключ не удалось найти:

□ Map lowerEntry(Obj ect key) — возвращает ссылку на наибольшую пару отображения с ключом, меньшим данного ключа key;

□ Object lowerKey(Object key) — возвращает ссылку на наибольший ключ отображения, меньший данного ключа key;

□ Map floorEntry(Obj ect key) — возвращает ссылку на наибольшую пару отображения с ключом, меньшим или равным данному ключу key;

□ Object floorKey(Object key) — возвращает ссылку на наибольший ключ отображения, меньший или равный данному ключу key;

□ Map higherEntry (Obj ect key) — возвращает ссылку на наименьшую пару отображения с ключом, большим данного ключа key;

□ Object highe rKey (Obj e ct key) - возвращает ссылку на наименьший ключ отображе

ния, больший данного ключа key;

□ Map ceilingEntry(Object key) — возвращает ссылку на наименьшую пару отображения с ключом, большим или равным данному ключу key;

□ Object ceilingKey(Object key) — возвращает ссылку на наименьший ключ отображения, больший или равный данному ключу key.

Следующие методы позволяют выделить отсортированное подмножество пар:

в–Ў NavigableMap subMap(Object fromKey, boolean frominclusive, Object toKey, boolean

toinclusive) - возвращает подмножество отображения от пары с ключом fromKey

включительно, если frominclusive == true, или исключительно, если

frominclusive == false, до пары с ключом toKey включительно или исключительно в зависимости от истинности последнего параметра toinclusive;

□ NavigableMap headMap(Object toKey, boolean inclusive) — возвращает начальные, меньшие пары до пары с ключом toKey включительно или исключительно в зависимости от истинности параметра inclusive;

□ NavigableMap tailMap(Object fromKey, boolean inclusive) — возвращает последние, большие пары от пары с ключом fromKey включительно или исключительно в зависимости от истинности параметра inclusive.

Наконец, два метода удаляют наименьший и наибольший элементы множества:

□ Map pollFirstEntry() — возвращает ссылку на наименьшую пару отображения и удаляет ее;

□ Map pollLastEntry() — возвращает ссылку на наибольшую пару отображения и удаляет ее.

Абстрактные классы-коллекции

Вы можете создать свои коллекции, реализовав рассмотренные ранее интерфейсы. Это дело трудное, поскольку в интерфейсах много методов. Чтобы облегчить данную задачу, в Java Collections Framework введены частичные реализации интерфейсов — абстрактные классы-коллекции.

Эти классы лежат в пакете j ava. util.

Абстрактный класс AbstractCollection реализует интерфейс Collection, но оставляет нереализованными методы iterator (), size().

Абстрактный класс AbstractList реализует интерфейс List, но оставляет нереализованным метод get (int) и унаследованный метод size(). Этот класс позволяет реализовать коллекцию с прямым доступом к элементам, подобно массиву.

Абстрактный класс AbstractSequentialList реализует интерфейс List, но оставляет нереализованным метод listiterator (int index) и унаследованный метод size(). Данный класс позволяет реализовать коллекции с последовательным доступом к элементам с помощью итератора Listiterator.

Абстрактный класс AbstractSet реализует интерфейс Set, но оставляет нереализованными методы, унаследованные от AbstractCollection.

Абстрактный класс AbstractQueue реализует интерфейс Queue, но оставляет нереализованными методы, унаследованные от AbstractCollection.

Абстрактный класс AbstractMap реализует интерфейс Map, но оставляет нереализованным метод entrySet ().

Наконец, в составе Java API есть полностью реализованные классы-коллекции. Помимо уже рассмотренных классов Vector, Stack, Hashtable и Properties, это классы ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, WeakHashMap и много других классов.

Для работы с указанными классами разработаны интерфейсы iterator, Listiterator, Comparator и классы Arrays и Collections.

Перед тем как рассмотреть использование данных классов, обсудим понятие итератора.

Интерфейс Iterator

В 70—80-х годах прошлого столетия, после того как была осознана важность правильной организации данных в определенную структуру, большое внимание уделялось изучению и построению различных структур данных: связанных списков, очередей, деков, стеков, деревьев, сетей.

Вместе с развитием структур данных развивались и алгоритмы работы с ними: сортировка, поиск, обход, хеширование.

Этим вопросам посвящена обширная литература, посмотрите, например, книгу [11].

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

В частности, задачу обхода возложили на саму коллекцию. В Java Collections Framework введен интерфейс iterator, описывающий способ обхода всех элементов коллекции. В каждой коллекции есть метод iterator(), возвращающий реализацию интерфейса iterator для указанной коллекции. Получив эту реализацию, можно обходить коллекцию в некотором порядке, определенном данным итератором, с помощью методов, описанных в интерфейсе iterator и реализованных в этом итераторе. Подобная техника использована в классе StringTokenizer, описанном в конце главы 5.

В интерфейсе iterator представлены всего три метода:

□ логический метод hasNext () возвращает true, если обход еще не завершен;

□ метод next () делает текущим следующий элемент коллекции и возвращает его в виде объекта класса Object;

□ метод remove () удаляет текущий элемент коллекции.

Можно представить себе дело так, что итератор — это указатель на элемент коллекции. При создании итератора указатель устанавливается перед первым элементом, метод next () перемещает указатель на первый элемент и показывает его. Следующее применение метода next () перемещает указатель на второй элемент коллекции и демонстрирует его. Последнее применение метода next () выводит указатель за последний элемент коллекции.

Метод remove () позволяет при просмотре коллекции удалять из нее ненужные элементы, сохраняя при этом порядок следования элементов. Дело в том, что метод remove () самой коллекции, удалив элемент, перестроит оставшиеся элементы коллекции и итератор может неправильно просмотреть оставшуюся часть коллекции.

В листинге 6.5 к тексту листинга 6.1 добавлена работа с итератором. Впрочем, для обхода коллекции типа List можно использовать оператор "for-each". Этот способ тоже показан в листинге 6.5.

Листинг 6.5. Использование итератора вектора j

Vector v = new Vector<>();

String s = "Строка, которую мы хотим разобрать на слова.";

StringTokenizer st = new StringTokenizer(s, " \t\n\r,.");

while (st.hasMoreTokens()){

// Получаем слово и заносим в вектор

v.add(st.nextToken()); // Добавляем элемент в конец вектора.

}

System.out.println(v.firstElement()); // Первый элемент. System.out.println(v.lastElement()); // Последний элемент. v.setSize(4); // Уменьшаем число элементов.

v.add("собрать."); // Добавляем в конец укороченного вектора.

v.set(3, "опять"); // Ставим элемент в позицию 3.

// Первый способ обхода коллекции типа List // использует индексы ее элементов:

for (int i = 0; i < v.size(); i++) // Перебираем весь вектор.

System.out.print(v.get(i) + " ");

System.out.println();

// Второй способ обхода коллекции использует итератор:

Iterator it = v.iterator(); // Получаем итератор вектора.

try{

while (it.hasNext()) // Пока в векторе есть элементы,

System.out.println(it.next()); // выводим текущий элемент.

}catch(Exception e){}

// Третий способ обхода коллекции использует оператор for-each: for (String s: v) // Цикл по всем элементам вектора.

System.out.println(s); // Выводим текущий элемент вектора.

Интерфейс ListIterator

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

В интерфейс Listiterator добавлены следующие методы:

□ void add (Obj ect element) — добавляет элемент element перед текущим элементом;

□ boolean hasPrevious() — возвращает true, если в коллекции есть элементы, стоящие перед текущим элементом;

□ int nextindex () — возвращает индекс текущего элемента; если текущим является последний элемент коллекции, возвращает размер коллекции;

□ Object previous () — возвращает предыдущий элемент и делает его текущим;

□ int previousindex() — возвращает индекс предыдущего элемента;

□ void set (Obj ect element) заменяет текущий элемент элементом element; выполняется

сразу после next () или previous ( ).

Как видите, итераторы могут изменять коллекцию, в которой они работают, добавляя, удаляя и заменяя элементы. Чтобы это не приводило к конфликтам, предусмотрена исключительная ситуация, возникающая при попытке использования итераторов параллельно "родным" методам коллекции. Именно поэтому в листинге 6.5 действия с итератором заключены в блок try{} catch () {}.

Изменим часть листинга 6.5 с использованием итератора Listiterator.

// Текст листинга 6.1...

// ...

ListIterator lit = v.listIterator(); // Получаем итератор вектора.

// Указатель сейчас находится перед началом вектора.

try{

while(lit.hasNext()) // Пока в векторе есть элементы,

System.out.println(lit.next()); // переходим к следующему

// элементу и выводим его.

// Теперь указатель находится за концом вектора.

// Перейдем к началу вектора. while(lit.hasPrevious())

System.out.println(lit.previous());

}catch(Exception e){}

Интересно, что повторное применение методов next () и previous () друг за другом будет выдавать один и тот же текущий элемент.

Посмотрим теперь, какие возможности предоставляют полностью определенные, готовые к работе классы-коллекции Java.

Классы, создающие списки

Класс ArrayList полностью реализует интерфейс List и итератор типа iterator. Класс ArrayList очень похож на класс Vector, у него тот же набор методов, он может использоваться в тех же ситуациях. Главное отличие класса ArrayList от класса Vector заключается в том, что класс ArrayList не синхронизован. Это означает, что одновременное изменение экземпляра этого класса несколькими подпроцессами приведет к непредсказуемым результатам. Эти вопросы мы рассмотрим в главе 22.

В классе ArrayList три конструктора:

□ ArrayList () — создает пустой объект;

□ ArrayList (Collection coll) — формирует объект, содержащий все элементы коллекции coll;

□ ArrayList (int initCapacity) — создает пустой объект емкости initCapacity.

В качестве примера использования класса ArrayList перепишем класс Chorus из листинга 3.3, используя вместо массива коллекцию.

public class Chorus{

public static void main(String[] args){

List singer = new ArrayList<>(); singer.add(new Dog()); singer.add(new Cat()); singer.add(new Cow()); for (Voice v: singer) v.voice();

}

}

Двунаправленный список

Класс LinkedList полностью реализует интерфейсы List, Queue и Deque. Он реализует итераторы типа iterator и Listiterator, что превращает его в двунаправленный список. Он удобен и для организации списков, стеков, очередей и деков. Класс LinkedList не синхронизован. Кроме того, он допускает хранение ссылок null.

В классе LinkedList два конструктора:

□ LinkedList () — создает пустой объект;

□ LinkedList (Collection coll) — создает объект, содержащий все элементы коллекции

coll.

В классе LinkedList реализованы только методы интерфейсов. Других методов в нем нет.

Дек

Класс ArrayDeque полностью реализует интерфейсы Queue и Deque. В отличие от класса LinkedList он синхронизован и допускает одновременную работу нескольких подпроцессов с его объектом. Кроме того, он не допускает хранение ссылок null. Он удобен для организации стеков, очередей и деков, тем более что он работает быстрее, чем классы Stack и LinkedList.

В классе ArrayDeque три конструктора:

□ ArrayDeque ( ) -создает пустой объект;

□ ArrayDeque (Collection coll) — создает объект, содержащий все элементы коллекции

coll;

□ ArrayDeque (int numElement) — создает пустой объект емкости numElement.

Упражнение

1. Перепишите листинг 6.1 с использованием классов списков.

Классы, создающие отображения

Класс HashMap полностью реализует интерфейс Map, а также итератор типа iterator. Класс HashMap очень похож на класс Hashtable и может использоваться в тех же ситуациях. Он имеет тот же набор функций и такие же конструкторы:

□ HashMap () — создает пустой объект с показателем загруженности 0,75;

□ HashMap (int capacity) - формирует пустой объект с начальной емкостью capacity и

показателем загруженности 0,75;

□ HashMap (int capacity, float loadFactor) — создает пустой объект с начальной емкостью capacity и показателем загруженности loadFactor;

□ HashMap(Map f) — создает объект класса HashMap, содержащий все элементы отображения f, с емкостью, равной удвоенному числу элементов отображения f, но не менее 11, и показателем загруженности 0,75.

Класс WeakHashMap отличается от класса HashMap только тем, что в его объектах неиспользуемые элементы, на которые никто не ссылается, автоматически исключаются из объекта.

Связанные отображения

Класс LinkedHashMap полностью реализует интерфейс Map. Реализация сделана в виде двунаправленного списка, а значит, его элементы хранятся в упорядоченном виде. Порядок элементов задается порядком их занесения в список.

В этом классе пять конструкторов:

□ linkedHashMap () — создает пустой объект с емкостью в 16 элементов;

□ LinkedHashMap (int capacity) -создает пустой объект с емкостью capacity элементов;

□ LinkedHashMap(int capacity, float loadFactor) — формирует объект с емкостью capacity элементов и показателем загруженности loadFactor;

□ LinkedHashMap(int capacity, float loadFactor, boolean order) — создает объект с емкостью capacity элементов, показателем загруженности loadFactor и порядком элементов order, прямым или обратным;

□ LinkedHashMap(Map sf) — создает объект, содержащий все элементы отображения sf.

Упорядоченные отображения

Класс TreeMap полностью реализует интерфейс SortedMap. Класс реализован как бинарное дерево поиска, что значительно ускоряет поиск нужного элемента.

Порядок задается либо естественным следованием элементов, либо объектом, реализующим интерфейс сравнения Comparator.

В данном классе четыре конструктора:

□ TreeMap () — создает пустой объект с естественным порядком элементов;

□ TreeMap (Comparator c) -создает пустой объект, в котором порядок задается объектом

сравнения c;

□ TreeMap(Map f) — формирует объект, содержащий все элементы отображения f, с естественным порядком его элементов;

□ TreeMap(SortedMap sf) — создает объект, содержащий все элементы отображения sf в том же порядке.

Хотя элементы отображения упорядочены, чтобы получить итератор для его обхода,

надо преобразовать отображение во множество методом entrySet (), например так:

iterator it = tm.entrySet().iterator();

Здесь надо пояснить, каким образом можно задать упорядоченность элементов коллекции.

Сравнение элементов коллекций

Интерфейс Comparator описывает два метода сравнения:

□ int compare (Obj ect objl, Object obj2) - возвращает отрицательное число, если objl

в каком-то смысле меньше obj2; нуль, если они считаются равными; положительное число, если obj 1 больше obj 2. Для читателей, знакомых с теорией множеств, скажем, что этот метод сравнения обладает свойствами тождества, антисимметричности и транзитивности;

□ boolean equals(Object obj) — сравнивает данный объект с объектом obj, возвращая true, если объекты совпадают в каком-либо смысле, заданном этим методом.

Для каждой коллекции можно реализовать эти два метода, задав конкретный способ сравнения элементов, и определить объект класса SortedMap вторым конструктором. Элементы коллекции будут автоматически отсортированы в заданном порядке.

Листинг 6.6 показывает один из возможных способов упорядочения комплексных чисел - объектов класса Complex из листинга 2.4. Здесь описывается класс ComplexCompare,

реализующий интерфейс Comparator. В листинге 6.7 он применяется для упорядоченного хранения множества комплексных чисел.

Листинг 6.6. Сравнение комплексных чисел

import java.util.*;

class ComplexCompare implements Comparator{

public int compare(Object objl, Object obj2){ Complex zl = (Complex)objl, z2 = (Complex)obj2; double rel = zl.getRe(), iml = zl.getim(); double re2 = z2.getRe(), im2 = z2.getim(); if (rel != re2)

return (int)(rel — re2);

else if (iml != im2)

return (int)(iml — im2); else return 0;

}

public boolean equals(Object z){ return compare(this, z) == 0;

}

}

Упражнение

2. Перепишите листинг 6.3 с использованием классов отображений.

Классы, создающие множества

Класс HashSet полностью реализует интерфейс Set и итератор типа iterator. Класс

HashSet применяется в тех случаях, когда надо хранить только одну копию каждого элемента.

В классе HashSet четыре конструктора:

□ HashSet () — создает пустой объект с показателем загруженности 0,75;

□ HashSet (int capacity) - формирует пустой объект с начальной емкостью capacity и

показателем загруженности 0,75;

□ HashSet (int capacity, float loadFactor) — создает пустой объект с начальной емкостью capacity и показателем загруженности loadFactor;

□ HashSet(Collection coll) — создает объект, содержащий все элементы коллекции coll, с емкостью, равной удвоенному числу элементов коллекции coll, но не менее 11, и показателем загруженности 0,75.

Связанные множества

Класс LinkedHashSet полностью реализует интерфейс Set и итератор типа iterator. Класс

реализован как двунаправленный список, значит, его элементы хранятся в упорядоченном виде. Порядок элементов задается последовательностью их занесения в объект.

В классе LinkedHashSet четыре конструктора, которые создают:

□ LinkedHashSet () — пустой объект с емкостью 16 и показателем загруженности 0,75;

□ LinkedHashSet (int capacity) — пустой объект с начальной емкостью capacity и показателем загруженности 0,75;

□ LinkedHashSet (int capacity, float loadFactor) — пустой объект с начальной емкостью capacity и показателем загруженности loadFactor;

□ LinkedHashSet(Collection coll) — объект, содержащий все элементы коллекции coll, с показателем загруженности 0,75.

Упорядоченные множества

Класс TreeSet полностью реализует интерфейс SortedSet и итератор типа iterator. Класс TreeSet реализован как бинарное дерево поиска. Это существенно ускоряет поиск нужного элемента.

Порядок задается либо естественным следованием элементов, либо объектом, реализующим интерфейс сравнения Comparator.

Этот класс удобен при поиске элемента во множестве, например для проверки, обладает ли какой-либо элемент свойством, определяющим множество.

В классе TreeSet четыре конструктора, создающих:

□ TreeSet () — пустой объект с естественным порядком элементов;

□ TreeSet (Comparator c) - пустой объект, в котором порядок задается объектом срав

нения c;

□ TreeSet(Collection coll) — объект, содержащий все элементы коллекции coll, с естественным порядком ее элементов;

□ TreeSet(SortedMap sf) — объект, содержащий все элементы отображения sf, в том же порядке.

В листинге 6.7 показано, как можно хранить комплексные числа в упорядоченном виде. Порядок задается объектом класса ComplexCompare, определенного в листинге 6.6.

Листинг 6.7. Хранение комплексных чисел в упорядоченном виде !

TreeSet ts = new TreeSet<>(new ComplexCompare());

ts.add(new Complex(l.2, 3.4));

ts.add(new Complex(-l.25, 33.4));

ts.add(new Complex(l.23, -3.45));

ts.add(new Complex(l6.2, 23.4));

iterator it = ts.iterator();

while (it.hasNext())

((Complex)it.next()).pr();

// for (Complex z: ts) z.pr(); // Другой способ обхода множества.

Действия с коллекциями

Коллекции предназначены для хранения элементов в удобном для дальнейшей обработки виде. Очень часто обработка заключается в сортировке элементов и поиске нужного элемента. Эти и другие методы обработки собраны в класс Collections.

Методы класса Collections

Все методы класса Collections статические, ими можно пользоваться, не создавая экземпляры класса Collections. Методов очень много, их количество увеличивается с каждой новой версией JDK, поэтому мы перечислим только основные методы.

Как обычно в статических методах, коллекция, с которой работает метод, задается его параметром.

Сортировка может быть сделана только в упорядочиваемой коллекции, реализующей интерфейс List. Для сортировки в классе Collections есть два метода:

□ static void sort(List coll) — сортирует в естественном порядке возрастания коллекцию coll, реализующую интерфейс List;

□ static void sort(List coll, Comparator c) — сортирует коллекцию coll в порядке, заданном объектом c.

После сортировки можно осуществить бинарный поиск в коллекции:

□ static int binarySearch(List coll, Object element) — отыскивает элемент element в отсортированной в естественном порядке возрастания коллекции coll и возвращает индекс элемента или отрицательное число, если элемент не найден; отрицательное число показывает индекс, с которым элемент element был бы вставлен в коллекцию, с обратным знаком;

□ static int binarySearch(List coll, Object element, Comparator c) — то же, но коллекция отсортирована в порядке, определенном объектом c.

Четыре метода находят наибольший и наименьший элементы в упорядочиваемой коллекции:

□ static Object max(Collection coll) - возвращает наибольший в естественном поряд

ке элемент коллекции coll;

□ static Object max(Collection coll, Comparator c) — то же в порядке, заданном объектом c;

□ static Object min(Collection coll) — возвращает наименьший в естественном порядке элемент коллекции coll;

□ static Object min(Collection coll, Comparator c) — то же в порядке, заданном объектом c.

Два метода "перемешивают" элементы коллекции в случайном порядке:

□ static void shuffle(List coll) — случайные числа задаются по умолчанию;

□ static void shuffle(List coll, Random r) — случайные числа определяются объектом r.

Метод reverse (List coll) меняет порядок расположения элементов на обратный.

Метод copy(List from, List to) копирует коллекцию from в коллекцию to.

Метод fill (List coll, Object element) заменяет все элементы существующей коллекции coll элементом element.

С остальными методами класса Collections мы будет знакомиться по мере надобности.

Упражнение

3. Упорядочите коллекции, созданные в этой главе, и проделайте в них бинарный поиск.

Заключение

Итак, в данной главе мы выяснили, что язык Java предоставляет множество средств для работы с большими объемами информации. В массе случаев достаточно добавить в программу три — пять операторов, чтобы можно было проделать нетривиальную обработку информации.

В следующей главе мы рассмотрим аналогичные средства для работы с массивами, датами, для получения случайных чисел и прочих необходимых средств программирования.

Вопросы для самопроверки

1. Что называется коллекцией?

2. В чем отличие вектора от массива?

3. Что дает задание конкретного класса в шаблоне при определении коллекции?

4. В чем различие интерфейсов List и Set?

5. В чем различие интерфейсов List и Queue?

6. Что дополняет интерфейс Deque к интерфейсу Queue?

7. Зачем в Java введены интерфейсы NavigableSet и NavigableMap?

8. Что такое стек?

9. Что такое ассоциативный массив?

10. Что такое линейный список?

11. Что такое двунаправленный список?

12. Какие способы обхода коллекции вы знаете?

13. Каким классом-коллекцией лучше всего организовать очередь?

14. Когда удобнее использовать класс Vector, а когда — ArrayList?

15. Можно ли совсем отказаться от объекта iterator в пользу цикла "for-each"?

16. Какие классы-коллекции реализуют структуру данных "дерево"?

ГЛАВА 7