JavaRush/Курсы/Java Collections/Реализации интерфейса Set, Queue

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

Открыта

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

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

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

Коллекции Set.

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

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

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

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 ситуация гораздо проще:

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

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

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

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

Комментарии (36)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Viter
Уровень 38
14 января 2024, 08:48
При поиске метод equals вызывается только в том случае если мы передаем в contains новый обьект (который при этом не подвергался никаким изменнеиям после создания) созданный с теми же аргументами как и тот с которым сравниваем, как я понял это и является проблемой поиска, если бы такого условия небыло можно было бы настроить equals что бы он корректно сравнивал по нужным полям. В чем причина такого условия интересно
апецт
Уровень 44
22 октября 2022, 15:58
я чет прозевал, в какой момент амиго и диего престали быть напарниками спасающими землю и стали студентом и преподом?
NonGrata
Уровень 51
18 ноября 2022, 17:06
В тот момент когда администрация обновила первый квест, а остальные - нет👩‍🚀
25 сентября 2021, 14:38
Давай До свидания!!! хххаааааа
Ilia lenskii
Уровень 32
18 сентября 2022, 13:55
Только единицы из миллионов понимают это
FatCat Backend Developer
30 сентября 2022, 14:28
ти кто такой?
Pig ManГлавная свинья в Свинарнике
14 февраля 2021, 13:27
Тебе задают вопросы на собеседовании не потому, что не знают ответ, а потому что хотят понять, знаешь ли ты его (как и на любом экзамене). Поэтому если бы я проводил собеседование и мне так ответили, этот человек просто пошел бы нахер и на работу мог бы не рассчитывать. Вот на его лицо в этот момент я бы посмотрел. Вывод: не надо так отвечать на любой вопрос кому-то на собеседовании
cavc
Уровень 41
14 апреля 2021, 15:02
Да я думаю, что 99.9% людей на собеседовании не будут так выражаться. Многие боятся сказать что-то лишнее)
Maks PanteleevJava Developer в Bell Integrator
23 июля 2021, 08:31
если ты агрессивный и неприятный тип, это не значит, что все такие)
Дмитрий
Уровень 35
30 августа 2021, 11:45
ну да, может кому то нравится, что его унижают ))))
Nikita SerkovBackend Developer в Kameleoon
27 октября 2021, 15:29
Не уверен, что такой ответ кого то может обидеть. Нет в ответе ничего обидного, он всего лишь показывает, что ты это знаешь и это азы.
LuneFoxJava Developer в BIFITExpert
15 февраля 2022, 10:31
Это ж то же самое, что "и ёжику понятно", что здесь некрасивого? Конечно, достаточно часто бывает, что люди оскорбляются с какой-нибудь самой безобидной фигни, а потом доказывай сиди, что ничего плохого не имел в виду. Можно даже не понять, что ты сделал не так, а люди тебя уже запомнили и смотрят исподлобья, как на врага народа.
Hidden #213 Урoвень 13 (Forever&Ever)
11 мая 2022, 07:45
Ты на собесе тоже дерзил?😏 Не отвечай, я знаю ответ. Небось накатил вискарика и разнёс всё шарашкину контору)))
Maks PanteleevJava Developer в Bell Integrator
11 мая 2022, 10:17
да не, собесы все проходили +- благоприятно, хотя я очковал конечно дико) ну сейчас бы разнес конечно если б пошел на собес, я теперь царь джавы))
Ilia lenskii
Уровень 32
18 сентября 2022, 13:59
моя мама так не думает, я нашко-котяшко
Сколько времени понадобилось чтобы стать царем джавы?
Maks PanteleevJava Developer в Bell Integrator
14 ноября 2022, 14:54
чуть больше года) ну до царя там еще оч далеко, но в целом хорошо)
успехов, друг! и поскорее стать царем!
Maks PanteleevJava Developer в Bell Integrator
16 ноября 2022, 09:01
спасибо, буду над этим работать)
Denis Odesskiy Full Stack Developer
7 января 2025, 23:10
Не становись царём жабы, а то за тобою придёт лягушка-царевна...😳
wan-derer.ru
Уровень 40
21 декабря 2020, 13:25
Вот про это изменение объекта с последующим разрушением хэша и immutable чтобы этого избежать - хотелось бы поподробнее!
ИльяBackend Developer в СберТех
11 февраля 2021, 08:24
не меняй объекты)))
Артем В.
Уровень 41
12 декабря 2020, 10:47
"Даже ребенку известно, что TreeSet и TreeMap используют сбалансированные красно-черные бинарные деревья, и поэтому такая ситуация невозможна в принципе." - посмотрим на лицо собеседующего, когда я ему это заявлю ;D
Kex
Уровень 38
Expert
17 июля 2020, 10:41
Задался вопросом про null, может ли принимать сеты нуль вот вообщем ответ на этот вопрос PS самое интересное там в коментах
Denis Odesskiy Full Stack Developer
7 января 2025, 23:23
HashSet может принимать null, это написано в доках. TreeMap если ему дать ключ null выбросит NPE, не знаю что там было в древних реализациях, статья на хабре та не очень свежая, на 20 джаве проверял, нефига она не позволяет засунуть null ключом в TreeMap, ровно как и TreeSet...
ЕвгенийBackend Developer в AmwayExpert
8 июля 2020, 19:13
Странно, что PriorityQueue является единственной официальной реализацией Queue, так как сама по себе эта реализация довольно специфична, и я пользовался ей один-два раза от силы. Из-за этого, когда я хочу сделать обычную очередь по принципу FIFO, приходится использовать LinkedBlockingQueue. Или я дурачок и есть обычная очередь, которую я не смог найти? Мне так-то обычно не требуется потокобезопасность.
Kex
Уровень 38
Expert
20 июля 2020, 08:15
а не подойдет ли для обычного FiFO и не потокобезопасный - LinkedList ?
ЕвгенийBackend Developer в AmwayExpert
20 июля 2020, 08:38
Хе-хе, ну да. Недавно только про него читал. Подойдёт. Да и интерфейсы реализует те же, просто название не очень похожее на остальные Queue.
Soros
Уровень 39
19 апреля 2020, 09:14
"Ясно. Люблю, когда у классов есть такие «на всякий случай» разновидности. Обычно такие случаи наступают не так уж и редко.", - сказал умудрённый профессиональным опытом программист Амиго.
skybrightProject Manager в construction companyExpert
20 октября 2019, 16:55
Воу-воу-воу, полегче. Наконец то интересная лекция с офигенными нюансами, спасибо.