— Як твій процесор?
— норм. Посидів годину в рідкому азоті і як новенький!
— Чудово. Тоді давай продовжимо.
Колекції 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, який формально теж є чергою.
Добре, щось я втомився, на сьогодні все. Давай до побачення.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ