比较器和 equals()

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() 之间的一致性，如 @SPFloyd - 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()更好吗？

Answer 1

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

来自 SortedSet 文档：

请注意，排序集维护的顺序（无论是否提供显式比较器）如果排序集要正确实现 Set 接口，则必须与 equals 一致。 （请参阅 Comparable 界面或 Comparator接口，用于与equals一致的精确定义。）之所以如此，是因为 Set 接口是根据 equals 操作定义的，但是有序集合使用其compareTo（或compare）方法执行所有元素比较，因此从有序集，相等。即使排序集的顺序与 equals 不一致，排序集的行为也是明确定义的；它只是没有遵守 Set 接口的一般契约。

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

---

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

构造函数与 ArrayList，但对于每个版本，还有带有自定义 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(); }

}

Answer 2

注意：即使对于两个 Foos f1,f2 和 f1 != f2，你也可能得到 f1.hashCode() == f2。哈希码（）！这意味着您将无法使用 compare 方法获得稳定的排序。

Answer 3

Java 中没有规则规定两个对象的哈希码必须不同，因为它们不相等（因此 o1.hashCode() - o2.hashCode() 可能返回 0 在你的情况下）。

此外，equals() 的行为应该与compareTo() 的结果一致。这不是必须，但如果您无法维持这一点，则表明您的设计存在很大缺陷。

我强烈建议查看对象的其他字段并使用其中一些字段来扩展您的比较，以便您获得对象的值 != 0 为 equals() == false.

Answer 4

hashcode() 方法不保证任何小于或大于。 compare() 和 equals() 应该产生相同的含义，但这不是必需的。

据我从您令人困惑的代码中可以理解（无意冒犯:)），您想向 TreeSet 添加重复项。出于这个原因，您提出了这个实现。原因如下，您不能将它们放入 TreeSet 中，引用文档，

集合的行为是明确定义的
即使它的顺序不一致
与平等；它只是不遵守
Set接口的通用契约。

因此，您需要使用您的 equals() 方法做一些事情，这样它就永远不会返回 true 。最好的实现是，

public boolean equals(Object o) {
    return false;
}

顺便说一句，如果我的理解是正确的，为什么不使用 List 来代替并对其进行排序。

Answer 5

非常有趣的问题。
据我了解，您的问题是重复元素。

我认为如果 o1.equals(o2) 它们的哈希码也可能相等。这取决于 Foo 类中 hashCode() 的实现。因此，我建议您改用 System.identityHashCode(x)。

Answer 6

您有一个具有可比性的 Foo 类，但希望在 TreeSet 结构中使用不同的排序。那么你的想法就是正确的做法。使用该构造函数“否决”Foo 的自然排序。

Answer 7

如果您对任何两个给定元素没有特定的预期顺序，但仍然希望将它们视为不相等，那么无论如何您都必须返回一些指定的顺序。

正如其他人所发布的， hashCode() 不是一个好的候选者，因为两个元素的 hashCode() 值很容易相等。 System.identityHashCode() 可能是一个更好的选择，但仍然不完美，因为即使 identityHashCode() 也不能保证唯一值

番石榴 Arbitration() Ordering 使用 Comparator >System.identityHashCode()。

Answer 8

是的，正如上面其他人所说，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;
}

Answer 9

int res = o1.compareTo(o2);

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

可能会出现问题，因为如果两个对象相等（即在您的 res == 0 中），那么这两个对象将返回相同的哈希码。哈希码对于每个对象来说并不是唯一的。

---

编辑 @Stas，System.identityHashCode(Object x); 仍然无法帮助您。 javadoc上描述了原因：

返回相同的哈希码
给定的对象将返回
默认方法hashCode()，
是否给定对象的
类重写hashCode()。哈希值
空引用的代码为零。

Answer 10

这里有几个问题：

• 哈希码通常不是唯一的，特别是 System.identityHashCode 在模糊现代的 JVM 上不会是唯一的。

• 这不是稳定性问题。我们正在对数组进行排序，但创建一个树结构。哈希码冲突将导致 compare 返回零，这对于 TreeSet 意味着一个对象获胜，另一个对象被丢弃 - 它不会降级为链表（线索名称中带有“Set”）。

• 从一个哈希码中减去另一个哈希码时通常会出现整数溢出问题。这意味着比较不会是传递的（即它被破坏）。幸运的是，在 Sun/Oracle 实现上，System.identityHashCode 始终返回正值。这意味着广泛的测试可能不会发现这种特定类型的错误。

我不认为有一个好的方法可以使用TreeSet来实现这一点。

Answer 11

有两点可能相关，即一种情况下的返回显示为 -1，这取决于函数参数变量或相关使用国家/地区是否允许负值，以及您使用的方法是否为允许的。有标准的数据排列方法，例如选择器或选择排序，并且如果您的工作场所没有副本，通常可以从国家当局获得论文描述或代码。使用大于或小于之类的比较可以加快代码速度，并通过隐式删除到后面的脚本或代码来避免使用直接比较相等性。