Что будет с повторяющимся элементом при передаче в TreeSet?

TreeSet и обработка повторяющихся элементов

При передаче повторяющегося элемента в TreeSet, он не будет добавлен. TreeSet — это отсортированное множество без дубликатов.

Поведение TreeSet с дубликатами

TreeSet отклоняет дубликаты

TreeSet<Integer> set = new TreeSet<>();

set.add(5);
set.add(3);
set.add(7);
set.add(5);  // Дубликат, будет отклонен

System.out.println(set); // [3, 5, 7]
System.out.println(set.size()); // 3, а не 4

Возвращаемое значение add()

TreeSet<Integer> set = new TreeSet<>();

boolean added1 = set.add(5);
System.out.println(added1); // true — элемент добавлен

boolean added2 = set.add(5);
System.out.println(added2); // false — дубликат отклонен

Как TreeSet определяет дубликаты

TreeSet использует Comparator или Comparable

// Вариант 1: Comparable
public class User implements Comparable<User> {
  private String name;
  private int age;
  
  @Override
  public int compareTo(User other) {
    // Если возвращает 0, элемент считается дубликатом
    return this.name.compareTo(other.name);
  }
}

TreeSet<User> users = new TreeSet<>();
users.add(new User("John", 25));
users.add(new User("John", 30)); // Дубликат по имени

System.out.println(users.size()); // 1

Вариант 2: Custom Comparator

TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
  @Override
  public int compare(String a, String b) {
    // Сравнение case-insensitive
    return a.compareToIgnoreCase(b);
  }
});

set.add("Hello");
set.add("hello");  // Дубликат (case-insensitive)
set.add("HELLO");  // Дубликат (case-insensitive)

System.out.println(set.size()); // 1
System.out.println(set); // [Hello]

Внутренний механизм TreeSet

TreeSet использует Red-Black Tree

TreeSet использует NavigableMap интерфейс, обычно TreeMap
   ↓
TreeMap хранит элементы в красно-чёрном дереве
   ↓
Деревья отсортированы по compareTo() или compare()
   ↓
Когда добавляется элемент:
  1. Ищется место в дереве (binary search)
  2. Если найдено равное (compareTo() == 0) → отклоняется
  3. Если место свободно → добавляется

Как работает поиск дубликата:

public boolean add(E e) {
  return map.put(e, PRESENT) == null;
}

public V put(K key, V value) {
  Entry<K,V> t = root;
  
  while (t != null) {
    cmp = key.compareTo(t.key); // ← ключевое сравнение
    
    if (cmp < 0)
      t = t.left;
    else if (cmp > 0)
      t = t.right;
    else
      return t.setValue(value); // ← дубликат найден, не добавляем
  }
  
  // Если дошли сюда — добавляем новый элемент
  addEntry(key, value);
}

Примеры реального поведения

Пример 1: Встроенные типы

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(10);
numbers.add(5);
numbers.add(15);
numbers.add(5); // Дубликат

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

Пример 2: Объекты с Comparable

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

TreeSet<Product> products = new TreeSet<>();
products.add(new Product(1, "Laptop"));
products.add(new Product(2, "Phone"));
products.add(new Product(1, "Desktop")); // id=1, дубликат

System.out.println(products.size()); // 2
// Второй элемент с id=1 отклонен, несмотря на другое имя

Пример 3: Case-insensitive String Set

Comparator<String> caseInsensitive = String::compareToIgnoreCase;
TreeSet<String> set = new TreeSet<>(caseInsensitive);

set.add("Apple");
set.add("apple");  // Дубликат
set.add("APPLE");  // Дубликат
set.add("banana");

System.out.println(set); // [Apple, banana]
System.out.println(set.size()); // 2

Опасность: неправильная реализация Comparable

❌ Плохо: сравнивает только один элемент

public class BadComparable implements Comparable<BadComparable> {
  private String name;
  private int age;
  
  @Override
  public int compareTo(BadComparable other) {
    // Сравниваем только имя!
    return this.name.compareTo(other.name);
  }
}

TreeSet<BadComparable> set = new TreeSet<>();
set.add(new BadComparable("John", 25));
set.add(new BadComparable("John", 30)); // Отклонен
set.add(new BadComparable("John", 35)); // Отклонен

System.out.println(set.size()); // 1
// Потеряли информацию про людей с тем же именем но разным возрастом

✅ Хорошо: правильная реализация

public class GoodComparable implements Comparable<GoodComparable> {
  private String name;
  private int age;
  
  @Override
  public int compareTo(GoodComparable other) {
    int nameComparison = this.name.compareTo(other.name);
    if (nameComparison != 0) {
      return nameComparison;
    }
    // Если имена одинаковые, сравниваем по возрасту
    return Integer.compare(this.age, other.age);
  }
}

TreeSet<GoodComparable> set = new TreeSet<>();
set.add(new GoodComparable("John", 25));
set.add(new GoodComparable("John", 30)); // Добавлен
set.add(new GoodComparable("John", 25)); // Отклонен (действительный дубликат)

System.out.println(set.size()); // 2

TreeSet vs HashSet

TreeSet

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
treeSet.add(1); // Отклонен

System.out.println(treeSet); // [1, 2, 3] ← отсортирован
System.out.println(treeSet.size()); // 3

HashSet

HashSet<Integer> hashSet = new HashSet<>();
hashSet.add(3);
hashSet.add(1);
hashSet.add(2);
hashSet.add(1); // Отклонен

System.out.println(hashSet); // [1, 2, 3] или [3, 1, 2] ← не гарантирует порядок
System.out.println(hashSet.size()); // 3

Производительность

Типичные операции TreeSet:
add()     → O(log n)
remove()  → O(log n)
contains()→ O(log n)
size()    → O(1)

Типичные операции HashSet:
add()     → O(1) в среднем
remove()  → O(1) в среднем
contains()→ O(1) в среднем

TreeSet медленнее, но элементы всегда отсортированы.

Практические советы

1. Используй TreeSet когда:

• Нужны элементы в отсортированном порядке
• Нужны методы типа first(), last(), headSet(), tailSet()
• Нужна отсортированная итерация

2. Используй HashSet когда:

• Нужна максимальная производительность
• Порядок элементов не важен
• Не нужна навигация (first, last и т.д.)

3. Проверка дубликата

TreeSet<String> set = new TreeSet<>();
String element = "test";

if (set.add(element)) {
  System.out.println("Элемент добавлен");
} else {
  System.out.println("Дубликат, не добавлен");
}

Вывод

Повторяющиеся элементы в TreeSet:

• Не добавляются (отклоняются)
• Определяются через compareTo() или compare()
• add() возвращает false если элемент дубликат
• Размер не увеличивается

Опытный разработчик знает эти нюансы и выбирает правильную коллекцию для задачи.