Краткий ответ

В TreeSet уникальность определяется результатом сравнения: если компаратор возвращает 0, коллекция считает элементы одинаковыми, даже когда их equals возвращает false. Второй элемент не будет добавлен как отдельный элемент.

Исторический контекст

SortedSet предназначен для хранения элементов в упорядоченном виде и быстрого поиска по порядку. Для этого коллекция должна уметь не только сравнивать элементы, но и определять, достигнут ли уже элемент с тем же положением в порядке.

В Java эту роль выполняет естественный порядок элементов или переданный Comparator. Поэтому в отсортированных коллекциях сравнение является основой не только сортировки, но и операций поиска, вставки и удаления.

Постановка проблемы

Предположим, компаратор сравнивает пользователей только по электронной почте, а идентификатор пользователя игнорирует. Два разных пользователя с одинаковой электронной почтой будут считаться одним элементом для TreeSet.

Неверный выбор компаратора может привести к потере элементов при добавлении, неожиданному результату contains и удалению не того объекта, который вызывающий код мысленно связывает с операцией. Ошибка особенно опасна, когда разработчик ожидает семантику HashSet, где главным критерием являются equals и hashCode.

Подробное решение

При добавлении элемента TreeSet спускается по внутреннему упорядоченному дереву и использует сравнение, чтобы выбрать направление поиска. Если сравнение с уже существующим элементом возвращает 0, коллекция считает, что нужная позиция занята, и новый элемент отдельно не добавляет.

То же правило применяется к contains и remove: они ориентируются на результат сравнения, а не обязательно на equals. Поэтому поиск объекта, который не равен хранящемуся объекту по equals, всё равно может вернуть true, если компаратор считает их эквивалентными.

Минимальный пример:

import java.util.Comparator;
import java.util.TreeSet;

record User(int id, String email) {}

TreeSet<User> users = new TreeSet<>(
    Comparator.comparing(User::email)
);

users.add(new User(1, "a@example.com"));
users.add(new User(2, "a@example.com"));

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

Компаратор здесь согласовывает порядок только по email. Записи с идентификаторами 1 и 2 различаются по equals, но сравниваются как 0, поэтому размер множества равен 1.

Желательно, чтобы порядок был согласован с equals: сравнение должно возвращать 0 тогда, когда объекты логически равны по equals. Если нужно сохранить обоих пользователей, в компаратор следует добавить идентификатор как второй критерий. Альтернативой может быть HashSet, если сортировка не нужна и уникальность должна определяться через equals и hashCode.

Основные операции TreeSet — добавление, поиск и удаление — имеют гарантированную логарифмическую сложность по числу элементов. Использование дополнительных критериев сравнения сохраняет эту сложность, но меняет понятие уникальности. Компаратор также должен быть транзитивным и детерминированным; нарушение этих свойств делает порядок и результаты операций непредсказуемыми.

Ситуация из практики

В сервисе нужно было хранить активные заказы в отсортированном виде. Разработчик создал TreeSet с компаратором только по времени создания. При одинаковом времени два заказа считались одним, и часть заказов исчезала из набора.

Рассматривались варианты:

заменить TreeSet на HashSet — сохраняет все логически различные заказы, но не поддерживает сортировку;
оставить сравнение только по времени — сохраняет простоту, но допускает потерю заказов с одинаковой временной меткой;
добавить к времени уникальный идентификатор — сохраняет сортировку и различает заказы.

Выбрали третий вариант: сначала сравнивать время, а при равенстве — идентификатор заказа. В результате операции остались логарифмическими, порядок сохранился, а разные заказы перестали сливаться. Дополнительно зафиксировали в документации, что идентификатор является частью порядка коллекции.

Что кандидаты часто упускают

Обращается ли TreeSet к equals при добавлении элемента?

Нет, для определения позиции и совпадения TreeSet использует естественный порядок или Comparator. equals может вообще не вызываться в этом сценарии. Поэтому совпадение по equals не гарантирует, что два объекта будут храниться отдельно: если компаратор вернул 0, второй объект считается дубликатом.

Обязан ли компаратор возвращать именно -1, 0 или 1?

Нет. Важен знак результата: отрицательное значение означает порядок «меньше», положительное — «больше», ноль — эквивалентность в рамках порядка. Например, значения -15 и 7 корректны как результаты сравнения, если они не переполняются при вычислении и сохраняют требуемые свойства порядка.

Нарушает ли TreeSet контракт Set, если порядок не согласован с equals?

Такое использование не рекомендуется, потому что поведение перестаёт соответствовать интуитивной семантике общего контракта Set. Формально TreeSet всё равно применяет свой порядок, но методы add, contains и remove начинают работать с понятием эквивалентности, отличным от equals.

Из-за этого два объекта, не равные по equals, могут считаться одним элементом, а contains может вернуть true для объекта, которого фактически нет в коллекции по смыслу equals. Поэтому при проектировании компаратора нужно заранее определить, какую именно логическую уникальность должна обеспечивать коллекция.