Чем HashSet, LinkedHashSet и TreeSet отличаются?
- Какое множество выбрать в Java?
HashSet — без порядка, операции O(1); LinkedHashSet — помнит порядок вставки, O(1); TreeSet — отсортирован (красно-чёрное дерево), O(log n) и навигация: first, ceiling, subSet.
- Уникальность: HashSet и LinkedHashSet — hashCode и equals, TreeSet — compareTo или компаратор
- HashSet — вариант по умолчанию
- TreeSet не допускает null (естественный порядок)
А ещё Неизменяемое — Set.of(...), без гарантированного порядка
Подробно
HashSet построен на HashMap: элементы — ключи. Добавление, удаление, contains — O(1) в среднем. Порядок обхода не определён и может меняться после расширения таблицы.
LinkedHashSet — то же плюс двусвязный список по всем элементам: обход в порядке вставки. Немного больше памяти. Удобен, когда нужна уникальность и стабильный порядок (удалить дубли из списка, сохранив порядок: new LinkedHashSet<>(list)).
TreeSet построен на TreeMap (красно-чёрное дерево): элементы отсортированы по естественному порядку или компаратору. Операции O(log n). Даёт навигацию NavigableSet: first, last, floor, ceiling, headSet, tailSet, subSet, descendingSet. Уникальность определяется сравнением, а не equals.
Выбор: просто уникальность — HashSet; плюс порядок вставки — LinkedHashSet; сортировка или запросы «ближайший», «в диапазоне» — TreeSet.
Что хотят услышать
- Устройство и порядок каждого.
- Сложность операций.
- Как определяется уникальность.
- Когда что выбрать.
Частые ошибки
- Ожидать порядок вставки от HashSet.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗TreeSet без порядка, HashSet отсортирован
- ✗Все три сохраняют порядок вставки
- ✗LinkedHashSet сортирует элементы по значению, а TreeSet хранит порядок вставки
- ✓HashSet без порядка; LinkedHashSet — порядок вставки; TreeSet — сортировка
Что спросят дальше
- На чём основан HashSet?
- Почему mutable элементы опасны в HashSet?
Разбор темы
- Set: HashSet, LinkedHashSet, TreeSet
Почему Set построен поверх Map, три реализации и их гарантии порядка, роль equals/hashCode.
- TreeMap, TreeSet и сортировка
Красно-чёрное дерево, NavigableMap, Comparable против Comparator, согласованность с equals и TimSort.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.