Может ли TreeSet содержать дубликаты?

Не спешите давать ответ, а лучше запустите код, приведенный ниже.

Возможно вы подумаете, что это надуманный пример, но это лишь немного упрощенная версия того кода, с которым мне пришлось столкнуться на практике. Для начала о проблеме, которую был призван решить этот код. В списке объектов надо было оставить объекты с различными именами, причем неважно какой объект из всего набора с таким же именем останется. Сразу же уточню, что на практике в проекте используется Java 7 и класс объектов, добавляемых в TreeSet, не вложен в какой-либо другой, а приведенный здесь вариант использован для краткости.

Может возникнуть вопрос почему выбрано именно такое решение. Давайте разберемся, чтобы не повторять ошибку. Первое, что приходит в голову, когда из списка надо удалить дубликаты, - использовать Set. В данной ситуации HashSet не подходит, потому что он использует equals метод для сравнения и отсеивания дубликатов. Но наш программист не сдаётся и вспоминает, что есть же еще TreeSet, в документации по которому явно написано, что для сравнения (в том числе при вставке) используется метод compare переданного в конструктор компаратора и в TreeSet не добавляются объекты равные с уже добавленными по определению компаратора, хотя и не равные по определению метода equals, что вообще-то нарушает контракт интерфейса Set (sic!). Это же то, что надо, - решает наш программист и приступает к написанию компаратора. Для начала пишется интересующее нас сравнение и тут все ок. Так, а что возвращать для объектов, у которых имена разные? Ну, нам же порядок неважен, так что пускай будет 1, - думает программист (sic!). Осталось превратить Set обратно в список и всё, решение готово. А спустя некоторое время выясняется, что дубликаты как были так и остались, а значит надо разобраться что же пошло не так. Предлагаю сделать это вместе.

Для начала скажем, что в данном случае метод addAll просто вызывает метод add в цикле. А метод add выглядит следующим образом: где переменная m имеет тип TreeMap (для некоторых это сюрприз :) ).

Не будем спешить и почитаем документацию по TreeMap, в которой написано, что данный класс является реализацией интерфейса NavigableMap, в основе которой красно-чёрное дерево (вспоминаем, что это одно из самобалансирующихся двоичных деревьев поиска). Теперь смотрим реализацию метода put и видим, что аргумент метода сравнивается с уже имеющимися объектами, начиная с корня дерева и дальше по направлению, зависящему от знака сравнения (вправо, если + и влево, если -). После каждой вставки дерево перебалансируется, в результате чего корень может измениться, что и происходит в рассматриваемом примере. В нашем случае корень (первый добавленный объект) в итоге оказывается слева и добавляемый 4-й объект, идентичный ему, с ним уже не сравнивается (из-за особенностей реализации компаратора) и успешно добавляется. В итоге TreeSet содержит дубликат.

Вывод простой: знайте то, что используете.