В чём разница между 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.