Ответ
HashSet и TreeSet — реализации интерфейса Set, которые не допускают дубликатов, но имеют фундаментальные различия в внутренней организации, производительности и контрактах.
Сравнительная таблица:
| Критерий | HashSet |
TreeSet |
|---|---|---|
| Внутренняя структура | Хеш-таблица (на основе HashMap). |
Красно-черное дерево (сбалансированное бинарное дерево поиска). |
| Порядок элементов | Не гарантируется. Зависит от хеш-кодов и емкости таблицы. | Элементы отсортированы согласно их естественному порядку (интерфейс Comparable) или переданному Comparator. |
| Производительность (Big O) | add(), remove(), contains() в среднем O(1). В худшем случае (все коллизии) O(n). |
add(), remove(), contains() гарантированно O(log n). |
Поддержка null |
Разрешает один null элемент. |
Не разрешает null (выбрасывает NullPointerException), если только Comparator явно не поддерживает сравнение null. |
| Требования к элементам | Требует корректной реализации hashCode() и equals(). |
Требует, чтобы элементы были Comparable или предоставлен Comparator. |
| Дополнительные операции | Нет операций, связанных с порядком. | Предоставляет методы для работы с порядком: first(), last(), headSet(), tailSet(), subSet(). |
Практические примеры выбора:
// Используем HashSet, когда важен быстрый поиск и порядок не важен.
Set<String> quickLookupSet = new HashSet<>();
quickLookupSet.add("apple");
quickLookupSet.add(null); // Допустимо
quickLookupSet.add("banana");
System.out.println(quickLookupSet); // Порядок вывода может быть любым, например [null, banana, apple]
// Используем TreeSet, когда элементы должны быть отсортированы.
Set<String> sortedSet = new TreeSet<>();
sortedSet.add("banana");
sortedSet.add("apple");
// sortedSet.add(null); // Вызовет NullPointerException
System.out.println(sortedSet); // Гарантированно [apple, banana]
// TreeSet с пользовательским Comparator для сортировки по длине строки.
Set<String> lengthSortedSet = new TreeSet<>(Comparator.comparing(String::length).thenComparing(s -> s));
lengthSortedSet.add("fig");
lengthSortedSet.add("apple");
lengthSortedSet.add("kiwi");
System.out.println(lengthSortedSet); // [fig, kiwi, apple] (по длине, затем лексикографически)