java - 比较器和等于()

Question

假设我需要 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 接口(interface)并将此逻辑移动到 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() 更好吗？

Answer 1

虽然这可能有效，但远不是最佳实践。

来自SortedSet docs :

Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

对于实现Comparable的对象，方法equals()、hashcode()和之间应该始终保持一致compareTo().

---

恐怕 SortedSet 不是您想要的，Guava MultiSet 也不够(因为它不会让您独立检索多个相等的项目) .我认为您需要的是 SortedList。据我所知，没有这样的野兽(也许在 commons-collections 中，但那些在遗留方面有点)，所以我使用 Guava 的 ForwardingList 作为基类为你实现了一个。简而言之:此列表几乎将所有内容委托(delegate)给它在内部使用的 ArrayList，但它在其 add() 方法中使用了 Collections.binarySearch()找到正确的插入位置，它会在 List 和 ListIterator 接口(interface)的所有可选方法上抛出 UnsupportedOperationException，这些方法在给定位置添加或设置值位置。

构造函数与 ArrayList 的构造函数相同，但对于它们中的每一个，还有一个带有自定义 Comparator 的第二个版本。如果您不使用自定义 Comparator，您的列表元素需要实现 Comparable 否则 RuntimeException 将在排序期间发生。

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(); }

}