Java 比较器和equals()

Comparator and equals()

提问by Stan Kurilin

Suppose I need TreeSetwith elements sorted with some domain logic. By this logic it doesn't matter order of some elements that doesn't equal so compare method can return 0, but in this case I couldn't put them in TreeSet.

假设我需要TreeSet使用一些域逻辑对元素进行排序。根据这个逻辑，某些不相等的元素的顺序无关紧要，因此比较方法可以返回 0，但在这种情况下，我无法将它们放入TreeSet.

So, question: what disadvantages I'll have from code like this:

所以，问题：我会从这样的代码中得到什么缺点：

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

Update:

更新：

Ok. If it should always be a consistency between the methods equals(), hashcode()and compareTo(), as @S.P.Floyd - seanizer and others said. If it would be better or even good if I'll remove Comparableinterface and move this logic in Comparator(I can do it without broken encapsulation)? So it will be:

好的。如果它应该始终是方法之间的一致性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;
    }
});

Update 2:

更新2：

Would System.identityHashCode(x)be better than hashCode()if I don't need stable sort?

如果我不需要稳定排序会System.identityHashCode(x)更好hashCode()吗？

采纳答案by Sean Patrick Floyd

While this might work, it is far from being a best practice.

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

From the SortedSet docs:

来自SortedSet 文档：

Note that the orderingmaintained 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 Comparableinterface or Comparatorinterface 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.

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

For objects that implement Comparable, there should always be a consistency between the methods equals(), hashcode()and compareTo().

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

---

---

I'm afraid a SortedSetis just not what you want, nor will a Guava MultiSetbe adequate (because it will not let you independently retrieve multiple equal items). I think what you need is a SortedList. There is no such beast that I know of (maybe in commons-collections, but those are a bit on the legacy side), so I implemented one for you using Guava's ForwardingList as a base class. In short: this List delegates almost everything to an ArrayListit uses internally, but it uses Collections.binarySearch()in it's add()method to find the right insertion position and it throws an UnsupportedOperationExceptionon all optional methods of the Listand ListIteratorinterfaces that add or set values at a given position.

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

The Constructors are identical to those of ArrayList, but for each of them there is also a second version with a custom Comparator. If you don't use a custom Comparator, your list elements need to implement Comparableor RuntimeExceptions will occur during sorting.

构造函数与 的相同ArrayList，但对于它们中的每一个，还有一个带有自定义Comparator. 如果不使用自定义 Comparator，则您的列表元素需要实现，Comparable否则RuntimeException排序时会出现 s。

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

}

回答by Adeel Ansari

hashcode()method doesn't guarantee any less thanor greater than. compare()and equals()should yield the same meaning, but its not necessary, though.

hashcode()方法不保证任何less than或greater than。compare()并且equals()应该产生相同的含义，但它不是必需的。

As far as I can understand from your confusing code (no offence intended :)), you want to add duplicates to the TreeSet. For that reason you came up with this implementation. Here is the reason, you can't put them in the TreeSet, quoting from the docs,

据我从您令人困惑的代码中了解到（无意冒犯:)），您想将重复项添加到TreeSet. 出于这个原因，你想出了这个实现。这就是原因，你不能把它们放在TreeSet，从文档中引用，

The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

集合的行为是明确定义的，即使它的顺序与 equals 不一致；它只是不遵守 Set 接口的一般约定。

So, you need to do something with yor equals()method, so it can never return true whats so ever. The best implementation would be,

所以，你需要用你的equals()方法做一些事情，所以它永远不会返回真实的东西。最好的实现是，

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

By the way, if I am right in my understanding, why not you use Listinstead and sort that.

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

回答by AlexR

Very interesting question. As far as I understand your problem is duplicate elements.

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

I think that if o1.equals(o2) their hash codes might be equal too. It depends on the implementation of hashCode() in your Foo class. So, I'd suggest you to use System.identityHashCode(x) instead.

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

回答by Andreas Dolk

You have a Fooclass wich is comparable but want to use a different sorting in a TreeSet<Foo>structure. Then your idea is the correct way to do it. Use that constructor to "overrule" the natural sorting of Foo.

您有一个Foo可比较的类，但想在TreeSet<Foo>结构中使用不同的排序。那么你的想法就是正确的做法。使用该构造函数来“否决” Foo.

回答by Buhake Sindi

int res = o1.compareTo(o2);

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

Can be problematic, since if 2 objects are equal (i.e. in your res == 0) then these 2 objects return the same hashcode. Hashcodes are not unique for every object.

可能有问题，因为如果 2 个对象相等（即在您的 中res == 0），那么这 2 个对象返回相同的哈希码。哈希码对于每个对象都不是唯一的。

---

---

Edit@Stas, The System.identityHashCode(Object x);still won't help you. The reason is described on the javadoc:

编辑@Stas，System.identityHashCode(Object x);仍然无济于事。原因在javadoc上有描述：

Returns the samehash code for the given object as would be returned by the default method hashCode(), whether or not the given object's class overrides hashCode(). The hash code for the null reference is zero.

为给定对象返回与默认方法返回的相同哈希码hashCode()，无论给定对象的类是否覆盖hashCode()。空引用的哈希码为零。

回答by Thomas

Beware: even for two Foos f1,f2with f1 != f2you could get f1.hashCode() == f2.hashCode()! That means you won't get a stable sorting with your compareMethod.

请注意：即使两个FOOS f1，f2与f1 != f2你可以得到f1.hashCode() == f2.hashCode()！这意味着你不会用你的compare方法获得稳定的排序。

回答by Aaron Digulla

There is no rule in Java which says that the hash codes of two objects must be different just because they aren't equal (so o1.hashCode() - o2.hashCode()could return 0in your case).

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

Also the behavior of equals()shouldbe consistent with the results from compareTo(). This is not a mustbut if you can't maintain this, it suggests that your design has a big flaw.

的行为也equals()应该与 的结果一致compareTo()。这不是必须的，但如果你不能保持这个，就表明你的设计有很大的缺陷。

I strongly suggest to look at the other fields of the objects and use some of those to extend your comparison so you get a value != 0for objects were equals() == false.

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

回答by Joachim Sauer

If you have no specific expected ordering for any two given elements, but still want to consider them un-equal, then you have to return some specified ordering anyway.

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

As others have posted, hashCode()isn't a good candidate, because the hashCode()values of both elements can easily be equal. System.identityHashCode()might be a better choice, but still isn't perfect, as even identityHashCode()doesn't guarantee unique values either

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

The Guavaarbitrary()Orderingimplements a Comparatorusing System.identityHashCode().

该番石榴arbitrary()订购实现了一个Comparator使用System.identityHashCode()。

回答by morja

Yes, as others said above, hashCode() is not secure to use here. But if you dont care about the ordering of objects that are equal in terms of o1.compareTo(o2) == 0, you could do something like:

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

回答by Tom Hawtin - tackline

There are a couple of problems here:

这里有几个问题：

• Hash codes are not generally unique, and in particular System.identityHashCodewill not be unique on vaguely modern JVMs.

• This is not a question of stability. We are sorting an array, but creating a tree structure. The hash code collisions will cause compareto return zero, which for TreeSetmeans one object wins and the other is discarded - it does not degrade to a linked-list (the clue is having "Set" in the name).

• There is generally an integer overflow issue with subtracting one hash code from another. This means the comparison wont be transitive (i.e. it is broken). As luck would have it, on the Sun/Oracle implementation, System.identityHashCodealways returns positive values. This means that extensive testing will probably not find this particular sort of bug.

• 哈希码通常不是唯一的，尤其System.identityHashCode是在模糊的现代 JVM 上也不是唯一的。

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

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

I don't believe there is a good way to achieve this using TreeSet.

我不相信使用TreeSet.