Как TreeSet определяет уникальность значений

TreeSet и определение уникальности значений

TreeSet в Java — это реализация интерфейса NavigableSet, которая хранит элементы в отсортированном порядке. Уникальность значений в TreeSet определяется через компаратор, а не через equals/hashCode, как в HashSet.

Как TreeSet работает

TreeSet использует красно-чёрное дерево (Red-Black Tree) для хранения элементов. Два элемента считаются одинаковыми, если компаратор для них возвращает 0, что означает их равенство:

// Если comparator.compare(e1, e2) == 0, то e1 и e2 считаются одинаковыми
// и e2 НЕ будет добавлен в TreeSet

Естественный порядок сортировки (Comparable)

Если TreeSet создан без явного компаратора, используется естественный порядок — элементы должны реализовать интерфейс Comparable:

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(3);
numbers.add(5); // Не добавится — уже есть 5

System.out.println(numbers); // [3, 5]

Ключевой момент: TreeSet использует compareTo() для определения уникальности, а не equals()!

class Student implements Comparable<Student> {
    int id;
    String name;
    
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.id, other.id);
    }
}

TreeSet<Student> students = new TreeSet<>();
students.add(new Student(1, "Alice"));
students.add(new Student(1, "Bob")); // Не добавится — ID одинаковый

// Хотя Alice != Bob по equals(), TreeSet считает их дубликатами!

Кастомный компаратор (Comparator)

Для большей гибкости можно передать кастомный компаратор:

TreeSet<String> words = new TreeSet<>((s1, s2) -> {
    // Сравниваем по длине слова
    return Integer.compare(s1.length(), s2.length());
});

words.add("apple");    // длина 5
words.add("banana");   // длина 6
words.add("cat");      // длина 3
words.add("dog");      // длина 3 — не добавится, "cat" уже есть!

System.out.println(words); // [cat, apple, banana]

TreeSet vs HashSet: различия в определении уникальности

Важная ошибка в определении уникальности

class Person {
    String name;
    int age;
    
    // equals() говорит, что они разные
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    // Но compareTo() говорит, что они одинаковые
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

TreeSet<Person> people = new TreeSet<>();
people.add(new Person("Alice", 25));
people.add(new Person("Bob", 25)); // Не добавится!
// equals() вернул false, но compareTo() вернул 0 — TreeSet победит

Лучшие практики

1. Если comparator.compare() возвращает 0, элемент считается дубликатом, независимо от equals()
2. TreeSet НЕ использует hashCode(), это только для HashSet
3. Компаратор должен быть согласован с equals() для предсказуемого поведения:
   • Если compareTo() == 0, то equals() == true
4. Используй HashSet, если тебе не нужна сортировка — это быстрее
5. TreeSet идеален для отсортированных данных и range-запросов (headSet, tailSet)

Пример правильной реализации

class Product implements Comparable<Product> {
    int id;
    String name;
    double price;
    
    @Override
    public int compareTo(Product other) {
        return Integer.compare(this.id, other.id);
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Product)) return false;
        Product product = (Product) o;
        // equals() должен быть согласован с compareTo()
        return id == product.id;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

TreeSet<Product> products = new TreeSet<>();
products.add(new Product(1, "Laptop", 999.99));
products.add(new Product(2, "Mouse", 29.99));
products.add(new Product(1, "Keyboard", 79.99)); // Не добавится — ID = 1

В итоге: TreeSet определяет уникальность через компаратор (compareTo или Comparator), а не через equals/hashCode.