Коллекции

Сложно придумать проект, в котором не требуется работа с коллекциями. Мы уже сталкивались с этим понятием в примере для отрисовки траектории робота в статье Визуализация робота. Также мы снова подняли этот вопрос в статье Список контактов – начало. Ну что же, пришло время с ними познакомиться. Коллекция в общем виде — это возможность собрать объекты в некоторую группу/множество и работать с этой группой. В общем-то самое главное уже сказано — коллекция предоставляет возможность совершать операции с группой объектов — это добавление, удаление, просмотр всех объектов в группе и прочие более специализированные операции. Еще раз — есть группа объектов, с которой надо совершать определенные операции и для этого нужен специальный класс. Вот этот класс по сути и есть коллекция. Я хотел бы выделить два важных момента:

  1. Группа обычно имеет (я бы даже сказал — должна иметь) базовый набор функций — добавить, удалить, пройтись по всему списку, получить элемент. Но также возникает необходимость иметь дополнительные возможности, которые являются специфическими. Именно этим определяется разнообразие классов коллекций
  2. Группа включает объекты в подавляющем большинстве случаев однотипных (одного класса). Хотя бывают исключения

Базовый функционал

Для работы с коллекциями разработчики Java создали специальный Collection Framework. Наиболее понравившееся мне руководство вот это: Trail: Collection (The Java Tutorials). Возможно я мог бы сказать — ну и читатйте сами его и наслаждайтесь, но все-таки я буду описывать свое понимание этого пакета. Но я не собираюсь рассказывать вам все-все-все. Это превратится в скучное перечисление функций, которое будет повторять официальную документацию, которую вам все равно придется читать во время работы. Не вижу никакого смысла этим заниматься. Но это не значит, что не надо читать другие источники — моя задача (такую я себе сам поставил) «наставить вас на путь истинный», по которому вы должны пойти сами.
Итак, вся система Collection Framework может быть разделена на три составляющих:

  1. Набор базовых интерфейсов для нексольких типов коллекций
  2. Набор классов для реализации базовых интерфейсов с разными «потребительскими» характеристиками
  3. Набор алгоритмов для работы с коллекциями

Базовые интерфейсы

В официальной документации они все перечислены, но я не буду пока приводить его полностью, напишу пока самые важные (на мой взгляд конечно). Основная идея при рассмотрении этих интерфейсов должна быть такая — весьма умные люди разработали список методов, которые крайне важны для определенных типов коллекций — списков, множеств, очередей и прочая. Список имеет свои особенности, множество — свои, очередь — свои. Набор методов для списка и для множества будет различаться, т.к. эти типы коллекций (список и множество) имеют некоторые важные отличия. Рассматривайте их как специализированные инструменты — например, для закручивания шурупов нужен шуруповоерт, для бетонных стен — перформатор, для сверления лунки — ледобур. Заметьте, что они все имеют «одну природу», но каждый имеет некоторую специализацию:

  • java.util.Collection — основной интерфейс, который описывает базовые методы, которыми должна обладать любая коллекция. Т.е. если какой-то класс претендует на звание КОЛЛЕКЦИЯ — он должен реализовать те методы, которые описаны в этом интерфейсе. Проводя аналогию с нашим набором сверлильных инструментов — интерфейс java.util.Collection их общий родитель — у него есть возможнсть сверлить. Советую зайти на сайт с документацией и честно просмотреть все его методы. Возможно, что Java версии 8 (и выше) покажется вам сложноватой, поэтому для начала советую зайти на документацию по Java версии 7. java.util.Collection. Большая часть методов говорит сама за себя, так что почитайте.
  • java.util.List — интерфейс для операций с коллекцией, которая является списком. Список обладает следующими важными признаками:
    1. Список может включать одинаковые элементы
    2. Элементы в списке хранятся в том порядке, в котором они туда помещались. Самопроизвольных перемещений элементов в нем не происходит — только с вашего ведома. Например, вы можете добавить элемент на какую-то позицию и тогда произойдет сдвиг других элементов.
    3. Можно получить доступ к любому элементу по его порядковому номеру/индексу внутри списка

    Т.е. если вам требуется, чтобы коллекция обладала такими свойствами — выбирайте класс, который реализует интерфейс java.util.List

  • java.util.Set — интерфейс для хранения множества. В отличии от java.util.List этот интерфейс как раз не может иметь одинаковые элементы (смотрим методы equals и hashCode в статье Решения на основе классов) и порядок хранения элементов в множестве может меняться при добавлении/удалении/изменении элемента. Может возникнуть вопрос, зачем такиая коллекция нужна — это удобно в случае, когда вы создаете набор уникальных элементов из какой-то группы элементов
  • java.util.SortedSet — это наследник интерфейса java.util.Set и его дополнительным функционалом является автоматическое выстраивание элементов внутри множества по порядку. Как этот порядок настаивается, мы поговорим позже.
  • java.util.Queue — интерфейс предлагает работать с коллекцией как с очередью, т.е. коллекция имеет метод для добавления элементов в один конец и метод для получения элемента с другого конца — т.е. настоящая очередь по принципу FIFO — First In First Out — если первым пришел, то первым и уйдешь. Для широкого круга задач такая конструкция работы с коллекцией бывает достаточно удобной структурой.
  • java.util.Map — очень удобная конструкция, которая хранит данные не в виде списка значений, а в виде пары ключ-значение. Это очень востребованная форма, в которой вы получаете доступ к значению в коллекции по ключу. Например, доступ к данным пользователя на сайте может быть осуществлен по логину (по email например). Самих данных может быть достаточно много, но для поиска можно использовать очень короткую строку-ключ.

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

Простой пример использования коллекций

Прдлагаю посмотреть пример (демонстрацию) использования основных методов интерфейса java.util.Collection. Сначала просто напишу код примера и после этого прокомментирую его

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

Как видите, все достаточно просто — мы берем нужный класс и создаем его экземпляр. Я для примера взял java.util.ArrayList. Т.к. этот класс реализует (имплементирует) интерфейс java.util.Collection, то у него есть все методы, которые в интерфейсе описаны. Добавление в коллекцию происходит очень просто — вызываем метод add. Вызывали — теперь ваш объект уже в коллекции. Добавляйте сколько угодно строк или другие объекты. У вас может возникнуть вопрос «Какие типы данных можно поместить в коллекцию ?». Вопрос резонный и я буду на него отвечать более подробно несколько позже. Пока можно сказать так — в коллекцию можно поместить объект любого класса, но нельзя туда поместить элементарный тип — int, char, long. Этот вопрос я тоже буду рассматривать более подробно чуть позже. Также может возникнуть еще один вопрос: «А почему мы создаем класс ArrayList, но присваиваем их ссылке на интерфейс Collection?». Вопрос тоже достаточно интересный и я попробую на него ответить. Дело в том, что при построении крупных систем очень выгодно интегрировать одтельные части через интерфейсы — контракты. Как один модуль реализует для другого этот контракт — это личное дело модуля-реализатора. Главное — выполнить контракт в полном объеме. И чем меньше надо выполнять — тем проще. Мне в данном примере нужна коллекция и не больше. Значит есть смысл сознательно использовать только то, что надо и не «расстрачивать себя по мелочам». Вот такой вот практический посыл этой идеи.
А теперь давайте посмотрим наш код.

В данном кусочке демонстрируется конструкция, которая позволяет обратиться к каждому элементу коллекции (очень похоже на массив — мы такое смотрели в разделе Массивы – знакомство. Обратите внимание — т.к. все классы наследуются от класса Object, то любой элемент в коллекции может рассматриваться как Object.
Здесь при каждом цикле мы помещаем в переменную o ссылку на следующий объект в коллекции. Т.е. у нас получается две ссылки — одна внутри самой коллекции, вторая — наша переменная .
Такая конструкция появилась только в Java 1.5. До этого для прохода по коллекции надо было использовать итератор:

java.util.Iterator — это интерфейс, который позволяет перемещаться по списку элементов. При вызове метода iterator() вы получаете указатель на начало коллекции, но — ВНИМАНИЕ — не на первый элемент. Метод итератора hasNext() возвращает true в случае, если итератор может переместиться к следующему элементу (есть следующий за текущим), если получаем false — значит элементов больше нет.
Метод итератора next() перемещается на следующий элемент и возвращает его значение — объект типа . Еще раз — это объект типа Object. Обратите внимание — я здесь специально продемонстрировал (как я называю «жесткое») приведение типа — т.к. я знаю, что в коллекции находятся объекты типа String, то я преобразую ссылку на объект типа Object на ссылку на объект типа String.
Напомню, что с объектами мы работаем через ссылки и т.к. реальный объект в коллекции имеет тип Ыекштп, то приведение не вызовет ошибок. Такое приведение позволит мне работать теперь с объектов как со строкой — там много всяких интересных методов есть, которых нет у Object.
Код для демонстрации групповых операций я предлагаю вам разобрать самим — в качестве самостоятельной работы. Там ничего особенного нет, так что дерзайте. Хочу выделить вот этот фрагмент:

Здесь мы удаляем элемент из коллекции. Но что весьма важно отметить — мы передаем ДРУГОЙ объект. Элемент, который мы передали методу remove и объект, который находится в коллекции — это ОДИНАКОВЫЕ, но РАЗНЫЕ объекты. По сути из коллекции удаляется объект, для которого метод equals возвращает true — смотрим раздел Решения на основе классов.
И на «закуску» сами разбираетесь в части, где удалаются все элементы через итератор

Как видите мы каждый раз после удаления проверяем не пуста ли наша коллекция (метод isEmpty) и если это не так, выставляем итератор в начало, переставляем его на первый элемент (т.к. коллекция не пустая, значит он точно есть) и удаляем.
Вот так вот на самом деле несложно получается работать с колекциями. Понятно, что дьявол кроется в деталях, но коллекции действительно сильно облегчают вам жизнь. Через некоторе время вы настолько к ним привыкните, что будете не понимать, как же без них раньше обходились.
Мы позже более подробно познакомимся с интерфейсами и классами, напишем небольшие примеры и я предложу вам самостоятельные задачки. Но сейчас мы поговорим о другой теме, которая имеет очень важную связь с коллекциями. В разделе Список контактов – начало мы использовали коллекцию для работы со списком контактов. Теперь вы даже можете новыми галазами посмотреть на наш класс ContactSimpleDAO. Там вы могли видеть вот такую конструкцию — описание функции findContacts() для возвращения списка контактов

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

Что такое Generic

Давайте еще раз посмотрим на объявление нашего метода:

Как видим, он возвращает список контактов (это класс, который реализует интерфейс java.util.List). Но что это за угловые скобочки, внутри которых находится слово Contact ? Давайте разбираться.

Старые песни на новый лад. Очередь объектов с Generic

Когда-то я написал статью Что нового в Java SE 5.0 и там упоминал о Generic. Так что кое-что можете посмотреть там тоже. Но и здесь мы будем изучать этот вопрос на примере, который мы разбирали раньше — Пример – очередь объектов.
Наша очередь, которую мы создали в этом примере, предоставляет возможность хранить список (произвольного размера) объектов любого типа. Но это достигается не самым приятным способом — мы вынуждены приводить полученные объекты к нужному нам типу из класса Object. С одной стороны — у нас очень гибкий инструмент. Мы туда можем положить и строки, и даты, и числа — все что угодно. Но на практике такое разнообразие типов в одном списке больше мешает, чем помогает. Идея создания класса, который бы мог работать с одной стороны с любым обхектом, а с другой стороны позволял четко определить с каким именно классом/типом он должен работать «на лету» достаточно продуктивна и поэтоу был создан механизм Generic.
Основную мысль я уже озвучил, так что повторюсь — Generic позволяет во-первых, определить класс, функциональность которого не зависит от типа объектов, с которыми он работает. И во-вторых, вы можете определить точный тип «на лету». Причем как только вы определяете тип, то все методы класса с Generic понимают только этот класс и никакой другой (дальше мы увидим, что это не совсем так, но для простоты я пока предлагаю понимать так). Как определяется Generic рассмотрим на самом простом примере, после которого перейдем к нашей очереди.
Итак, я хочу определить класс, у которого может быть поле произвольного класса и два метода — сеттер и геттер. Если не использовать Generic, то для универсальности мне пришлось бы написать что-то такое:

Использвать это класс для работы со строкой (String) пришлось бы как-то так

Самой важной здесь является третья строка с жестким приведением типа. Для одного случая это не самая большая проблема, но когда у вас сотни или даже тысячи разных классов, которые надо помещать в какие-то списки, очереди и т.д., то держать в голове, какие именно классы вы помещали в ту или иную очередь — это очень сложно и неудобно. Попробуем применить Generic.

Давайте внимательно посмотрим, что здесь изменилось. В первую очередь, в самом описании класса мы видим вот такую конструкцию

Буква «T» в угловых скобках говорит о том, что это — абстрактный тип (можно использовать не букву «Т», а любое другое имя — например «SIMPLE» или «Test»). И этот абстрактный тип мы будем использовать в дальнейшем описании нашего generic-класса. Если я хочу вернуть объект из метода getElement, то я в описании указываю «T» вместо Object. Это означает, что наш класс в какой-то степени «полуфабрикат» — он заранее не знает, какой именно класс он будет использовать в этих методах. Но т.к. его алгоритм универсален (в данном случае мы делаем очень простые функции, которые не зависят от класса), то мы как бы говорим нашему классу — «не парься, что именно за класс у тебя будет, в свое время узнаешь. И подставишь его вместо «T». Но чтобы ты понимал, в каких методах он встречается, мы тебе создаем подсказку в виде некоторого абстрактного типа «T» в угловых скобках». Именно угловые скобки говорят о том, что этот тип «для подстановки». Давайте посмотрим теперь как делать эту самую подстановку.

Обратите внимание, что при объявлении переменной, мы в угловых скобках указываем конкретный класс. В первом случае это String, во втором — Integer. Т.е. при объявлении переменной мы уже точно определяем, с каким типом будет работать эта переменная. Теперь проверка правильности подстановки нужного типа проверяется уже на этапе компиляции. Например, если вы попробуете установить для переменной sg2 строку — будет выдаваться ошибка. Попробуйте сделать вот так — и увидите.

До версии java 1.7 вы должны были дублировать содержиме угловых скобок и для правой части (точнее при вызове конструктора) — посмотрите пример.

В работе с Generic-классами важно уловить самое важное — умение работать С ЛЮБЫМ КЛАССОМ. Ну или с некоторой группой классов, имеющих один и тот же интерфейс (мы это еще увидим). Коллекции в этом отношении — самые благодарные. Им в общем-то без разницы объект какого класса у них находится в работе — как грузовику совершенно не важно, коробки с какими надписями лежат у него в кузове.
Нашей очереди в общем не важно, какой именно тип будет использоваться. Но в этом случае объявление абстрактонго типа несколько сложнее, т.к. он используется сразу в двух классах — ObjectQueue и QueueBox. Давайте сначал рассмотрим вложенный класс QueueBox.

Как видите тут описание сложнее. Наверно самое зубодробительное — это описание private ObjectBox<T> next;. Дело в том, что мы описываем переменную next и в этот момент мы должны указать, а какой тип будет использовать ObjectBox для этой переменной. Само собой мы не знаем. Но мы знаем, что он будет таким же, что и у основного класса. Т.е. мы инициализируем next, но инициализируем опять же абстрактным класом. Поэтому такая хитрая конструкция.
На таком же принципе мы определяем и нашу очередь — класс ObjectQueue. Смотрим полный код класса

Как видите, теперь мы везде используем абстрактный класс «T». Я вам советую внимательно разобраться в примере. Класс для проверки нашей очереди теперь выглядит вот так

В первой же строке мы указываем, что наша очередь будет работать со строками. Теперь все методы, которые объявлены с «T» по сути заменят его на String. Наши методы становятся жестко типизироваными (для переменной queue) — мы не сможем положить в нашу очередь queue числа или даты и при вызове метода get или pull методы будут сразу возвращать String. Что несомненно удобно. Причем если мы объявим переменную queue2 и типизируем ее Integer, то для этой переменнй строки будут недоступны.
В качестве домашнего задания попробуйте переписать пример из раздела Визуализация робота с использованием нашей типизированной очереди. На этом я хочу закончить первое знакомство с generic-классами и перейти к коллекциям. Но мы еще вернемся к этой теме.

Классы из CollectionFramework

Итак, мы с вами поззнакомились с понятие generic и теперь пора познакомиться с некоторыми готовыми классами, которые уже написаны и включены в Java SE.
Когда вы приступаете к выбору класса для коллекции, то вам необходимо определить набор характеристик, которые являются важными в рамках тех задач, которые призвана решать эта коллекция. Мы уже прошлись по списку базовых интерфейсов и это первый шаг для выбора коллекции. Например, если у вас предполагается ситуация с одинаковыми элементами в коллекции или вам крайне важен порядок элементов в коллекции, да к тому же вам надо иметь возможность обратиться к элементу на определенной позиции, то практически однозначно вам нужны реализации интерфейса List. Если вам необходима уникальность, быстрый поиск элемента внутри коллекции и порядок не важен — смотрим в сторорну Set. Нужен отсортированный порядок уникальных элементов — смотрим SortedSet.
Если работа с коллекцией требует поиска элемента по ключу, то на первом месте идет Map.
После того, как вы определитесь с базовым интерфейсом, наступает время выбора конкретной реализации, что тоже требует знакомства с конкретными классами. Например вы остановили свой выбор на интерфейсе List. Если зайти на страницу с документацией List (Java Platform SE 8 ), то выбор конечно не огромный, но достаточный, чтобы задуматься. Например, что нам больше подойдет — arrayList, LinkedList, Vector ? Здесь начинается изучение особенностей реализации. Класс ArrayList — прекрасный выбор, если вам нужен быстрый доступ к элементу по индексу и вы заранее знаете (хотя бы приблизительно) сколько элементов будет в этой коллекции. Но если вам надо много добавлений и не требуется доступ к элементу, а нужно пробегать по всему списку, то этот класс невыгоден — он основан на массиве и как только вы достигаете определенного размера, то будет создаваться новый массив, в который будут копироваться все элементы. Это дорогое удовольствие. Зато класс LinkedList прекрасно подходит. Мы уже в этом убедились — ведь мы создавали по сути свою версию этого класса — класс ObjectQueue. Могут быть дополнительные требования — например потокобезопасность (мы будем говорить о потоках позже). В этом случае возможно подойдет что-то еще. Т.е. с одной стороны все выглядит достаточно несложно — надо просто выбрать подходящий класс, но как говорится «дьявол кроется в деталях». Я встречал ситуации, когда разработчики создавали свои версии коллекций, т.к. существующие им не подходили.

Алгоритмы для работы с коллекциями

Алгоритмы для работы с коллекциями реализуются (в основном) в классе java.util.Collections. Не перепутайте с классом, о котором мы уже говорили — java.util.Collection. Отличие минимальное — в конце стоит дополнительная буква s. Если честно, мне не нравится — слишком похожие имена легко путаются, что меня никогда не радовало. Но что сделано, то сделано.
Я надеюсь, что вы уже достаточно продвинулись в изучении java и тратить кучу слов на описание методов мне бы не хотелось. Поэтому сразу предлагаю посмотреть пример — в нем последовательно приведены вызовы с некоторым набором функций класса java.utilCollections. просто посмотрите код, потом запустите и посмотрите на результаты. Весь пример посвящен нескольким операциям, результат которых демонстрируется выводом коллекции

И наш «подопытный» класс, в котором надо обатить внимание на мметоды equals и hashcode

при замене нам нужно находить равные объекты.

Сортировка

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

  1. Использовать коллекцию с реализацией интерфейса java.util.SortedSet — например класс java.util.TreeSet
  2. Использовать метод sort класса java.util.Collections

В первом случае (и частично во втором тоже) на класс, который вы храните в коллекции, накладывается требование — он должен реализовать интерфейс . При использовании SortedSet сортировка происходит сразу после добавления. Я предлагаю вам проверить это в качестве домашнего задания. В случае использования метода sort класса java.util.Collections вам потребуется создать класс, который реализует интерфейс java.util.Comparator. Задача этого класса очень простая — он должен сравнить два объекта. Предлагаю опять же рассмотреть все на примере. У нас будет 4 класса:

  1. MyClass — самый обычный класс, который мы сможем отсортировать
  2. MyClassCompare — класс, которые реализует интерфейс Comparable
  3. MyClassComparator — реализация интерфейса java.util.Comparator
  4. Main — класс для демонстрации

Я выделю следующие моменты:

  • Класс MyClassCompare реализует метод compareTo. Он возвращает число. Если оно больше нуля, то объект больше того, который передан в аргументе, если равен нулю — объекты равны, если меньше — переданный объект больше. Т.к. стандартные классы (в том числе и String) реализуют интерфейс Comparabe, то я им и воспользовался. Также обратите внимание, что интерфейс является generic — т.е. мы можем заранее сказать, какие классы будут сравниваться.
  • Класс MyClassComparator занимается сравнением двух объектов (отметим, что интерфейс Comparator тоже generic) с помощью метода compare, который работает по такому же принципу, что и метод compareTo у интерфейса Comparabe
  • Методы printCollection1 и printСollection2 выглядят очень похоже, но т.к. коллекции используют разные классы, мы вынуждены их разделить. Наверно это не так удобно, как хотелось бы — мы еще посмотрим, как с этим бороться

Хотелось бы отметить важный момент — при использовании класса от интерфейса Comparator сортируемый класс не должен реализовывать интерфейс Comparable. Также использование нескольких компараторов может позволить вам делать разные сортировки одной и той же коллекции.

Домашнее задание

  1. Попробуйте модифицировать класс MyClassComparator так, чтобы он мог сортировать не только в
    алфавитном порядке — от А до Я, но и в обратном — от Я до А
  2. Возьмите класс Contact из нашего проекта список контактов — начало и напишите для него компаратор, который может сортировать его по любому из полей
  3. Более сложный вариант — сделайте так, чтобы при сортировке контактов вы могли передать список полей, по которым хотите его отсортировать

Удачи.