Как происходит сравнение объектов в TreeSet

Что проверяют

Понимаете ли вы, что TreeSet вообще не смотрит на equals() и hashCode(), а решает всё через сравнение. Следом обычно дают пример: два разных объекта с одинаковым полем сравнения, сколько элементов окажется в сете.

Как отвечать

TreeSet это обёртка над TreeMap, то есть над красно-чёрным деревом, где элементы лежат ключами. Порядок и уникальность задаёт одно из двух:

• Comparable: естественный порядок, класс сам реализует compareTo(). Так устроены String, Integer, LocalDate;
• Comparator: внешнее правило, передаётся в конструктор и имеет приоритет над compareTo().

При add() дерево спускается от корня и на каждом узле вызывает сравнение: отрицательный результат ведёт влево, положительный вправо. Ноль значит «такой элемент уже есть»: add() вернёт false, в сете останется старый объект. Тем же сравнением работают contains() и remove(), всё за O(log n).

Главное следствие: сравнение должно быть согласовано с equals(). Если Comparator сравнивает людей только по возрасту, два разных человека одного возраста станут одним элементом. Пример из JDK: BigDecimal("1.0") и BigDecimal("1.00") в HashSet дают два элемента, в TreeSet один.

В Android-проекте на Kotlin сет обычно создают через sortedSetOf(compareBy<User> { it.age }.thenBy { it.id }), под капотом это тот же java.util.TreeSet. Последнее поле цепочки делайте уникальным, тогда ровесники не склеятся.

Ещё два поведения: объект без Comparable и без компаратора падает с ClassCastException уже на первом add(), а null при естественном порядке даёт NullPointerException.

Где спотыкаются

Пишут compareTo как this.age - other.age. На больших значениях разность переполняет int, знак меняется, и дерево ломается. Правильно Integer.compare(a, b) или compareBy.

Меняют поле, по которому идёт сравнение, у объекта, уже лежащего в сете. Дерево не перестраивается, и contains() перестаёт его находить.

Ожидают, что переопределённые equals() и hashCode() защитят от дублей. TreeSet их не вызывает.