Компаратор и равные()

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

Итак, вопрос: какие недостатки я буду иметь от такого кода: 

class Foo implements Comparable<Foo>{}
new TreeSet<Foo>(new Comparator<Foo>(){
    @Override
    public int compare(Foo o1, Foo o2) {
        int res = o1.compareTo(o2);
        if(res == 0 || !o1.equals(o2)){
            return o1.hashCode() - o2.hashCode();
        }
        return res;
    }
});

Обновление :

Хорошо. Если это всегда должно быть согласованием между методами equals(), hashcode() и compareTo(), Как сказал @S. P. Floyd-seanizer и другие. Если бы это было так будет лучше или даже хорошо, если я удалю интерфейс Comparable и перенесу эту логику в Comparator (я могу сделать это без нарушенной инкапсуляции)? Так и будет: 

class Foo{}
new TreeSet<Foo>(new Comparator<Foo>(){
    @Override
    public int compare(Foo o1, Foo o2) {
        //some logic start
        if(strictliBigger(o1, o2)){ return 1;}
        if(strictliBigger(o2, o1)){ return -1;}
        //some logic end
        if(res == 0 || !o1.equals(o2)){
            return o1.hashCode() - o2.hashCode();
        }
        return res;
    }
});

Обновление 2:

Будет ли System.identityHashCode(x) лучше, чем hashCode(), если мне не нужна стабильная сортировка?

11 10
equals comparator treeset

11 ответов:

Хотя это может сработать, это далеко не лучшая практика.

Из SortedSet docs :

Обратите внимание, что порядок, поддерживаемый сортированным набором (независимо от того, предусмотрен ли явный компаратор) , должен быть согласован с равными, если сортированный набор правильно реализует интерфейс набора. (Смотрите интерфейсComparable или интерфейсComparator для точного определения непротиворечивости с равными.) Этот это так, потому что интерфейс множества определяется в терминах операции equals, но сортированное множество выполняет все сравнения элементов с помощью своего метода compareTo (или compare), поэтому два элемента, которые считаются равными этим методом, с точки зрения сортированного множества равны. Поведение отсортированного множества хорошо определено, даже если его порядок не соответствует равенствам; оно просто не подчиняется общему контракту интерфейса множества.

Для объектов, реализующих Comparable, должно быть всегда соблюдайте последовательность между методами equals(), hashcode() и compareTo().

Боюсь, что SortedSet - это просто не то, что вы хотите, и гуава MultiSet не будет адекватной (потому что она не позволит вам независимо извлекать несколько одинаковых элементов). Я думаю, что то, что вам нужно, это SortedList. Я не знаю такого зверя (может быть, в коллекциях commons, Но они немного на стороне наследия), поэтому я реализовал один для вас, используя Guava ForwardingList в качестве базового класса. Короче говоря: этот список делегатов почти все до ArrayList он использует внутренне, но он использует Collections.binarySearch() в своем методе add(), чтобы найти правильную позицию вставки, и он бросает UnsupportedOperationException на все необязательные методы интерфейсов List и ListIterator, которые добавляют или устанавливают значения в данной позиции.

Конструкторы идентичны конструкторам ArrayList, но для каждого из них есть и вторая версия с заказом Comparator. Если вы не используете пользовательский компаратор, элементы списка должны реализовать Comparable или RuntimeExceptions произойдет во время сортировки.

public class SortedArrayList<E> extends ForwardingList<E> implements
    RandomAccess{

    private final class ListIteratorImpl extends ForwardingListIterator<E>{
        private final int start;
        public ListIteratorImpl(final int start){
            this.start = start;
        }

        @Override
        public void set(E element){throw new UnsupportedOperationException();}

        @Override
        public void add(E element){throw new UnsupportedOperationException();}

        @Override
        protected ListIterator<E> delegate(){return inner.listIterator(start);};

    }

    private Comparator<? super E> comparator;

    private List<E> inner;

    public SortedArrayList(){this(null, null, null);}

    @SuppressWarnings("unchecked")
    private SortedArrayList(
        final List<E> existing,
        final Collection<? extends E> values,
        final Comparator<? super E> comparator
    ){
        this.comparator =
            (Comparator<? super E>)
               (comparator == null
                   ? Ordering.natural()
                   : comparator   );
        inner = (
            existing == null
                ? (values == null
                      ? new ArrayList<E>(values)
                      : new ArrayList<E>()
                   )
                : existing;
    }

    public SortedArrayList(final Collection<? extends E> c){
        this(null, c, null);
    }

    public SortedArrayList(final Collection<? extends E> c,
        final Comparator<? super E> comparator){
        this(null, c, comparator);
    }

    public SortedArrayList(final Comparator<? super E> comparator){
        this(null, null, comparator);
    }

    public SortedArrayList(final int initialCapacity){
        this(new ArrayList<E>(initialCapacity), null, null);
    }

    public SortedArrayList(final int initialCapacity,
        final Comparator<? super E> comparator){
        this(new ArrayList<E>(initialCapacity), null, comparator);
    }

    @Override
    public boolean add(final E e){
        inner.add(
            Math.abs(
                Collections.binarySearch(inner, e, comparator)
            ) + 1,
            e
        );
        return true;
    }

    @Override
    public void add(int i, E e){throw new UnsupportedOperationException();}

    @Override
    public boolean addAll(final Collection<? extends E> collection){
        return standardAddAll(collection);
    }

    @Override
    public boolean addAll(int i,
        Collection<? extends E> es){
        throw new UnsupportedOperationException();
    }

    @Override
    protected List<E> delegate(){ return inner; }

    @Override
    public List<E> subList(final int fromIndex, final int toIndex){
        return new SortedArrayList<E>(
            inner.subList(fromIndex, toIndex),
            null,
            comparator
        );
    }

    @Override
    public ListIterator<E> listIterator(){ return new ListIteratorImpl(0); }

    @Override
    public ListIterator<E> listIterator(final int index){
        return new ListIteratorImpl(index);
    }

    @Override
    public E set(int i, E e){ throw new UnsupportedOperationException(); }

}
9

Осторожно: даже для двух Фоу f1,f2 с помощью f1 != f2 Вы можете получить f1.hashCode() == f2.hashCode()! Это означает, что вы не получите стабильную сортировку с вашим методом compare.

2

В Java нет правила, которое говорит, что хэш-коды двух объектов должны быть разными только потому, что они не равны (поэтому o1.hashCode() - o2.hashCode() может вернуть 0 в вашем случае).

Также поведение equals() должно быть согласовано с результатами из compareTo(). Это не является обязательным , но если вы не можете поддерживать это, это предполагает, что ваш дизайн имеет большой недостаток.

Я настоятельно рекомендую посмотреть на другие поля объектов и использовать некоторые из них для расширения вашего сравнения. таким образом, вы получаете значение != 0 для объектов were equals() == false.
2

hashcode() метод не гарантирует никаких less than или greater than. compare() и equals() должны давать одно и то же значение, но это не обязательно.

Насколько я могу понять из вашего запутанного кода (без обид :)), вы хотите добавить дубликаты в TreeSet. По этой причине вы и придумали эту реализацию. Вот причина, вы не можете поместить их в TreeSet, цитируя из документов,

Поведение множества хорошо определено даже если его упорядочение непоследовательно с равными; он просто не в состоянии повиноваться генеральный контракт установленного интерфейса.

Итак, вам нужно что-то сделать с yor equals() методом, чтобы он никогда не возвращал true whats so ever. Наилучшей реализацией было бы, 

public boolean equals(Object o) {
    return false;
}
Кстати, если я прав в своем понимании, почему бы вам не использовать List вместо этого и не отсортировать это.
2

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

Я думаю, что если o1.equals (o2) их хэш-коды тоже могут быть одинаковыми. Это зависит от реализации hashCode () в вашем классе Foo. Итак, я предлагаю вам использовать систему.identityHashCode (x) вместо этого.

1

У вас есть класс Foo, который сопоставим, но вы хотите использовать другую сортировку в структуре TreeSet<Foo>. Тогда ваша идея-это правильный способ сделать это. Используйте этот конструктор, чтобы" отменить " естественную сортировку Foo.

1

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

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

Гуава arbitrary() упорядочение реализует a Comparator используя System.identityHashCode().

1

Да, как уже говорилось выше, hashCode () не является безопасным для использования здесь. Но если вы не заботитесь о порядке объектов, которые равны с точки зрения o1.compareTo (o2) == 0, вы можете сделать что-то вроде:

public int compare(Foo o1, Foo o2) {
        int res = o1.compareTo(o2);
        if (res == 0 && !o1.equals(o2)) {
            return -1;
        }
        return res;
}
1
int res = o1.compareTo(o2);

if(res == 0 || !o1.equals(o2)){
    return o1.hashCode() - o2.hashCode();
}

Может быть проблематичным, так как если 2 объекта равны (то есть в вашем res == 0), то эти 2 объекта возвращают один и тот же хэш-код. Хэш-коды не уникальны для каждого объекта.

Edit @Stas, System.identityHashCode(Object x); все равно не поможет вам. Причина описана на javadoc:

Возвращает тот же самый хэш-код для данный объект как бы возвращается метод по умолчанию hashCode(), независимо от того, является ли данный объект переопределяет класс hashCode(). Хэш код ибо нулевая ссылка равна нулю.

1

Здесь есть пара проблем:

  • Хэш-коды обычно не уникальны, и в частности System.identityHashCode не будет уникальным на неопределенно современных JVMs.

  • Это не вопрос стабильности. Мы сортируем массив, но создаем древовидную структуру. Коллизии хэш-кода приведут к тому, что compare вернет ноль, что для TreeSet означает, что один объект выигрывает, а другой отбрасывается - он не деградирует до связанного списка (ключ имеет "набор" в имя).

  • Обычно возникает проблема переполнения целого числа при вычитании одного хэш-кода из другого. Это означает, что сравнение не будет транзитивным (то есть оно нарушено). Как назло, в реализации Sun / Oracle System.identityHashCode всегда возвращает положительные значения. Это означает, что обширное тестирование, вероятно, не найдет этот конкретный вид ошибки.

Я не думаю, что есть хороший способ достичь этого, используя TreeSet.
1

Два момента могут быть релевантными, и они заключаются в том, что возврат в одной ситуации отображается как -1, и это зависит от того, разрешено ли отрицательное значение в переменной параметра функции или в соответствующей стране использования, а также если разрешен метод, который вы используете. Существуют стандартные методы упорядочения данных, такие как селектор или сортировка выборки, и описание или код бумаги обычно доступны в Национальном органе, если копия не находится на вашем рабочем месте. Использование сравнений типа больше, чем или меньше, чем может ускорить код и избежать использования прямого сравнения для равенства путем подразумеваемого перехода к более позднему сценарию или коду.

1