Реализации интерфейса Set, Queue

— Ну как твой процессор?

— Норм. Посидел час в жидком азоте и как новенький!

— Отлично. Тогда давай продолжим.

Коллекции Set.

Set переводится как множество. А множество, с математической точки зрения, — это набор уникальных элементов. Но т.к. не все программисты – математики, то обычно говорят, что Set – это коллекция уникальных элементов, или коллекция, которая не позволяет хранить одинаковые элементы.

Не знаю, давала Элли тебе иерархию наследования для Set, но если нет, то вот она:

HashSet – это коллекция, которая для хранения элементов внутри использует их хэш-значения, которые возвращает метод hashCode().

Для простоты внутри HashSet<E> хранится объект HashMap<E, Object>, который и хранит в качестве ключей значения HashSet.

— Ничего себе!

— Использование hash-кодов позволяет довольно быстро искать, добавлять и удалять элементы из множества (Set).

Но учти, чтобы объекты твоих классов можно было класть в Set и правильно находить их там, у твоего класса должны быть правильно реализованы методы hashCode & equals.

И тот и другой активно используются внутри HashSet/HashMap.

Если ты забудешь реализовать метод hashCode(), то рискуешь, что твой объект в коллекции Set не будет найден, даже если он там есть.

— Да, помню, я помню. Ты мне уже рассказывал раньше об этом. Все робоуши прожужжал.

— Ок. Тогда вот тебе еще полезная информация.

Допустим, ты правильно реализовал hashCode и equals в своем классе и такой весь радостный хранишь объекты в Set’е.

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

А это значит, что когда ты будешь его искать в Set’е, его скорее всего не найдут.

— Ничего себе! Это как же?

— Это всем известный косяк с работой хешей. Грубо говоря, поиск в HashSet (и в HashMap) гарантированно работает правильно, только если объекты – immutable.

— Ничего себе! И что, никто ничего не делает?

— Все делают вид, что проблемы не существует. Но на собеседованиях это частенько спрашивают, так что возможно, тебе стоит запомнить этот факт…

LinkedHashSet – это HashSet, в котором элементы хранятся еще и в связном списке. Обычный HashSet не поддерживает порядок элементов. Во-первых, официально его просто нет, во-вторых, даже внутренний порядок может сильно поменяться при добавлении всего одного элемента.

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

— Ясно. Люблю, когда у классов есть такие «на всякий случай» разновидности. Обычно такие случаи наступают не так уж и редко.

— TreeSet – это коллекция, которая хранит элементы в виде упорядоченного по значениям дерева. Внутри TreeSet<E> содержится TreeMap<E, Object> который и хранит все эти значения. А этот TreeMap использует красно—черное сбалансированное бинарное дерево для хранения элементов. Поэтому у него очень быстрые операции add, remove, contains.

— Ага. Я помню, мы же совсем недавно это разбирали. А я еще думал – и где это применяется.

А оказывается, одни из самых популярных коллекций в Java используют это.

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

— Ага. Хотелось бы увидеть лицо спрашивающего в этот момент. Я, пожалуй, даже заучу эту фразу. …

А в принципе, Set оказался не таким уж и простым, как мне казалось в самом начале.

— Зато с Queue ситуация гораздо проще:

Queue – это очередь. Элементы добавляются в конец очереди, а выбираются из ее начала.

PriorityQueue – это фактически единственная классическая реализация интерфейса Queue, не считая LinkedList, который формально тоже является очередью.

Ладно, что-то я устал, на сегодня все. Давай до свидания.