Компаратор подходит для TreeSet, когда нет отличительного поля

Если у вас нет абсолютно большого количества фиктивных объектов и действительно не повезло, вы можете использовать System.identityHashCode() для разрыва связей:

Comparator.<Dummy>comparingInt(d -> map.get(d))
          .thenComparingInt(System::identityHashCode)

Ваш компаратор неприемлем, поскольку он нарушает контракт: у вас есть d1> d2 и d2> d1 одновременно, если они не равны и не имеют одинакового значения на карте.

Этот ответ охватывает только первый пример вопроса. На оставшуюся часть вопроса и различные правки, я думаю, лучше ответить в виде отдельных конкретных вопросов.

Первый пример устанавливает 12 экземпляров Dummy, создает карту, которая сопоставляет каждый экземпляр с Integer в диапазоне [0, 3], а затем добавляет 12 экземпляров Dummy к TreeSet. Этот TreeSet снабжен компаратором, который использует карту Dummy-to-Integer. В результате TreeSet содержит только четыре экземпляра Dummy. Пример завершается следующим утверждением:

Результат явно неудовлетворительный (содержит меньше элементов, чем исходная коллекция). Это связано с тем, что такой компаратор несовместим с равенством, т.е. иногда возвращает 0 для неравных элементов.

Последнее предложение неверно. Результат содержит меньше элементов, чем было вставлено, потому что компаратор считает многие экземпляры дубликатами, и поэтому они не вставляются в набор. Метод equals вообще не обсуждается. Следовательно, концепция согласованности с равными не имеет отношения к этому обсуждению. TreeSet никогда не звонит equals. Компаратор - единственное, что определяет принадлежность к TreeSet.

Это кажется неудовлетворительным результатом, но только потому, что мы знаем, что существует 12 различных Dummy экземпляров. Однако TreeSet не знает, что они различны. Он знает только, как сравнивать Dummy экземпляры с помощью компаратора. Когда он это делает, он обнаруживает, что некоторые из них являются дубликатами. То есть компаратор иногда возвращает 0, даже если он вызывается с Dummy экземплярами, которые мы считаем разными. Вот почему только четыре Dummy экземпляра попадают в TreeSet.

Я не совсем уверен, каков желаемый результат, но похоже, что результат TreeSet должен содержать все 12 экземпляров, упорядоченных по значениям на карте фиктивного преобразования в целое число. Мое предложение состояло в том, чтобы использовать Guava _ 19_, который предоставляет компаратор, который различает отдельные, но в остальном равные элементы, но делает это способом, который удовлетворяет общему соглашению Comparator. Если вы создадите TreeSet следующим образом:

SortedSet<Dummy> sorted = new TreeSet<>(Comparator.<Dummy>comparingInt(map::get)
                                                  .thenComparing(Ordering.arbitrary()));

в результате TreeSet содержит все 12 Dummy экземпляров, отсортированных по Integer значению на карте, и с Dummy экземплярами, которые сопоставляются с одним и тем же значением, упорядоченным произвольно.

В комментариях вы заявили, что Ordering.arbitrary документ недвусмысленно предостерегает от его использования в SortedSet. Это не совсем так; этот документ говорит,

Поскольку упорядочение основано на идентичности, оно не согласуется с Object.equals (Object), как определено Comparator. Будьте осторожны при построении SortedSet или SortedMap из него, поскольку результирующая коллекция не будет вести себя в точном соответствии со спецификацией.

Фраза не в точности соответствует спецификации означает, что она будет вести себя странно, как описано в документе класса _ 28_:

Упорядочение, наложенное компаратором c на набор элементов S, называется согласованным с equals тогда и только тогда, когда c.compare(e1, e2)==0 имеет то же логическое значение, что и e1.equals(e2) для каждого e1 и e2 в S.

Следует проявлять осторожность при использовании компаратора, способного устанавливать порядок, несовместимый с равенством, для упорядочивания отсортированного набора (или отсортированной карты). Предположим, что отсортированный набор (или отсортированная карта) с явным компаратором c используется с элементами (или ключами), взятыми из набора S. Если порядок, наложенный c на S, несовместим с equals, отсортированный набор (или отсортированная карта) будет вести себя странно. В частности, отсортированный набор (или отсортированная карта) нарушит общий договор для набора (или карты), который определен в терминах equals.

Например, предположим, что кто-то добавляет два элемента a и b так, что (a.equals(b) && c.compare(a, b) != 0) к пустому TreeSet с компаратором c. Вторая операция добавления вернет true (и размер набора деревьев увеличится), потому что a и b не эквивалентны с точки зрения набора деревьев, даже если это противоречит спецификации метода Set.add.

Вы, кажется, указали, что это странное поведение недопустимо, поскольку Dummy элементы, которые equals не должны появляться в TreeSet. Но класс Dummy не отменяет equals, поэтому кажется, что здесь скрывается дополнительное требование.

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

ОБНОВЛЕНИЕ 22 декабря 2018 г.

Перечитав правки вопросов и комментарии, я думаю, что наконец понял, что вы ищете. Вам нужен компаратор для любого объекта, который обеспечивает первичное упорядочение на основе некоторой функции с целым значением, которая может приводить к дублированию значений для неравных объектов (как определено методом equals объектов). Следовательно, требуется вторичный порядок, который обеспечивает полное упорядочение по всем неравным объектам, но возвращает ноль для объектов, которые являются equals. Это означает, что компаратор должен быть совместим с равными.

Ordering.arbitrary Guava приближается к нему в том смысле, что он обеспечивает произвольное полное упорядочение по любым объектам, но возвращает ноль только для идентичных объектов (то есть ==), но не для объектов, которые являются equals. Таким образом, это несовместимо с равными.

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

static Comparator<Object> arbitraryUnequal() {
    Map<Object, Integer> map = new HashMap<>();
    return (o1, o2) -> Integer.compare(map.computeIfAbsent(o1, x -> map.size()),
                                       map.computeIfAbsent(o2, x -> map.size()));
}

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

(Если вы намереваетесь использовать этот компаратор одновременно, например, при параллельной сортировке, HashMap следует заменить на ConcurrentHashMap, а трюк с размером следует изменить, чтобы использовать AtomicInteger, который увеличивается при добавлении новых записей.)

Обратите внимание, что карта в этом компараторе создает записи для каждого неравного объекта, который он когда-либо видел. Если это присоединено к TreeSet, объекты будут сохраняться на карте компаратора даже после того, как они были удалены из TreeSet. Это необходимо для того, чтобы при добавлении или удалении объектов они сохранили постоянный порядок с течением времени. Ordering.arbitrary Guava использует слабые ссылки, позволяющие собирать объекты, если они больше не используются. Мы не можем этого сделать, потому что нам нужно сохранить порядок неидентичных, но равных объектов.

Вы бы использовали это так:

SortedSet<Dummy> sorted = new TreeSet<>(Comparator.<Dummy>comparingInt(map::get)
                                                  .thenComparing(arbitraryUnequal()));

Вы также спросили, что означает следующее:

Поведение набора четко определено, даже если его порядок несовместим с равенством

Предположим, вы использовали TreeSet, используя компаратор, несовместимый с равными, например, тот, который использует Ordering.arbitrary Гуавы, показанный выше. TreeSet по-прежнему будет работать, как ожидалось, в соответствии с самим собой. То есть он будет поддерживать объекты в полном порядке, он не будет содержать никаких двух объектов, для которых компаратор возвращает ноль, и все его методы будут работать, как указано. Однако может существовать объект, для которого contains возвращает истину (поскольку это вычислено с использованием компаратора), но для которого equals ложно, если вызывается с объектом, фактически находящимся в наборе.

Например, BigDecimal это Comparable, но его метод сравнения несовместим с равенством:

> BigDecimal z = new BigDecimal("0.0")
> BigDecimal zz = new BigDecimal("0.00")
> z.compareTo(zz)
0
> z.equals(zz)
false
> TreeSet<BigDecimal> ts = new TreeSet<>()
> ts.add(z)
> HashSet<BigDecimal> hs = new HashSet<>(ts)
> hs.equals(ts)
true
> ts.contains(zz)
true
> hs.contains(zz)
false

Это то, что имеет в виду спецификация, когда говорится, что вещи могут вести себя странно. У нас есть два равных набора. Тем не менее, они сообщают о разных результатах для contains одного и того же объекта, а TreeSet сообщает, что он содержит объект, даже если этот объект не равен объекту в наборе.

Вот компаратор, который у меня получился. Это одновременно надежно и эффективно с точки зрения памяти.

public static <T> Comparator<T> uniqualizer() {
    return new Comparator<T>() {
        private final Map<T, Integer> extraId = new HashMap<>();
        private int id;

        @Override
        public int compare(T o1, T o2) {
            int d = Integer.compare(o1.hashCode(), o2.hashCode());
            if (d != 0)
                return d;
            if (o1.equals(o2))
                return 0;
            d = extraId.computeIfAbsent(o1, key -> id++)
              - extraId.computeIfAbsent(o2, key -> id++);
            assert id > 0 : "ID overflow";
            assert d != 0 : "Concurrent modification";
            return d;
        }
    };
}

Он создает полное упорядочение для всех объектов данного класса T и, таким образом, позволяет различать объекты, не различимые данным компаратором, путем присоединения к нему следующим образом:

Comparator<T> partial = ...
Comparator<T> total = partial.thenComparing(uniqualizer());

В примере, приведенном в вопросе, T равно Dummy и

partial = Comparator.<Dummy>comparingInt(map::get);

Обратите внимание, что вам не нужно указывать тип T при вызове uniqualizer(), компилятор автоматически определяет его через вывод типа. Вам нужно только убедиться, что hashCode() в T соответствует equals(), как описано в генеральный договор hashCode(). Затем uniqualizer() предоставит вам компаратор (total), соответствующий equals(), и вы можете использовать его в любом коде, который требует сравнения объектов типа T, например. при создании TreeSet:

TreeSet<T> sorted = new TreeSet<>(total);

или сортировка списка:

List<T> list = ...
Collections.sort(list, total);