В чём разница между HashSet, LinkedHashSet и TreeSet?

Короткий ответ

HashSet основан на HashMap (элементы — ключи карты) и не гарантирует порядка: элементы распределяются по корзинам по хэш-коду, операции добавления и поиска в среднем O(1), допускается один null. LinkedHashSet наследует HashSet и дополнительно прошивает элементы связным списком в порядке вставки. TreeSet хранит элементы отсортированными в красно-чёрном дереве за O(log n), а null не допускает.

Как это работает подробнее

Порядок в LinkedHashSet задаётся порядком добавления: при итерации элементы приходят именно в нём, цена — чуть больший расход памяти и немного более медленные операции. TreeSet сортирует по естественному порядку (Comparable) либо по переданному Comparator; при вставке элемент сразу сравнивается с другими, поэтому null даёт NullPointerException. Дерево позволяет отдавать диапазоны: subSet, headSet, tailSet.

• HashSet: максимальная скорость, порядок не важен.
• LinkedHashSet: нужен порядок вставки.
• TreeSet: нужен отсортированный обход и диапазонные операции.

Пример кода

SetDemo.javaКопировать

Set<String> hash = new HashSet<>();
hash.add("b");
hash.add("a");   // порядок обхода не гарантирован
Set<String> linked = new LinkedHashSet<>();
linked.add("b");
linked.add("a"); // итерация в порядке вставки: b, a
Set<String> tree = new TreeSet<>();
tree.add("b");
tree.add("a");   // итерация по возрастанию: a, b

Что использовать на практике

• Нужна максимальная скорость и не важен порядок — берите HashSet.
• Нужен порядок добавления — берите LinkedHashSet.
• Нужно отсортированное множество, ближайшие элементы или диапазоны — берите TreeSet.

Подводные камни

• TreeSet требует, чтобы элементы реализовывали Comparable или был передан Comparator, иначе вставка падает с ClassCastException.
• В TreeSet нельзя добавить null — элемент сравнивается при вставке.
• Порядок обхода HashSet нестабилен и меняется при добавлении элементов и resize — не полагайтесь на него.

Как отвечать на собеседовании

• Начните с общего: все три — реализации Set без дубликатов → затем по каждой: HashSet — хэш-таблица на базе HashMap, порядок не гарантирован, O(1); LinkedHashSet — добавляет связный список порядка вставки; TreeSet — красно-чёрное дерево, сортировка через Comparable или Comparator, O(log n) → закончите правилом выбора по нужному порядку и набору операций.