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

TreeSet хранит элементы в отсортированном порядке и использует для этого красно-черное дерево. HashSet не гарантирует порядок элементов и основан на хеш-таблице.

Основные отличия:

• Порядок элементов: TreeSet упорядочен по возрастанию, HashSet – нет.
• Производительность: Для большинства операций (add, remove, contains) HashSet имеет среднюю сложность O(1), тогда как TreeSet – O(log n).
• Реализация: TreeSet использует TreeMap, где элементы хранятся как ключи. HashSet использует HashMap, где элементы хранятся как ключи, а значения – фиктивный объект.
• Хранение null: HashSet допускает один null элемент. TreeSet не допускает null, так как для сравнения элементов требуется их негомогенность.
• Сравнение элементов: TreeSet требует, чтобы элементы реализовывали интерфейс Comparable или был предоставлен компаратор. HashSet требует корректную реализацию методов equals() и hashCode() для элементов.

Пример использования:

import java.util.HashSet;
import java.util.TreeSet;

public class SetDifference {

    public static void main(String[] args) {
        // HashSet - без порядка
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Orange");
        System.out.println("HashSet: " + hashSet); // Порядок может меняться

        // TreeSet - отсортированный
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Orange");
        System.out.println("TreeSet: " + treeSet); // Всегда отсортирован
    }
}

Таблица сравнения: