java Treeset.contains() 问题

Treeset.contains() problem

提问by Jasper

So I've been struggling with a problem for a while now, figured I might as well ask for help here.

所以我一直在为一个问题苦苦挣扎，我想我不妨在这里寻求帮助。

I'm adding Ticket objects to a TreeSet, Ticket implements Comparable and has overridden equals(), hashCode() and CompareTo() methods. I need to check if an object is already in the TreeSet using contains(). Now after adding 2 elements to the set it all checks out fine, yet after adding a third it gets messed up.

我将 Ticket 对象添加到 TreeSet，Ticket 实现了 Comparable 并覆盖了 equals()、hashCode() 和 CompareTo() 方法。我需要使用 contains() 检查一个对象是否已经在 TreeSet 中。现在，在向集合中添加 2 个元素后，一切检查正常，但是在添加第三个元素后，它变得一团糟。

running this little piece of code after adding a third element to the TreeSet, Ticket temp2 is the object I'm checking for(verkoopLijst).

在向 TreeSet 添加第三个元素后运行这段代码，Ticket temp2 是我正在检查的对象（verkoopLijst）。

    Ticket temp2 = new Ticket(boeking, TicketType.STANDAARD, 1,1);
    System.out.println(verkoop.getVerkoopLijst().first().hashCode());
    System.out.println(temp2.hashCode());

    System.out.println(verkoop.getVerkoopLijst().first().equals(temp2));
    System.out.println(verkoop.getVerkoopLijst().first().compareTo(temp2));
    System.out.println(verkoop.getVerkoopLijst().contains(temp2));

returns this:

返回这个：

22106622
22106622
true
0
false

Now my question would be how this is even possible?

现在我的问题是这怎么可能？

Edit:

编辑：

public class Ticket implements Comparable{

    private int rijNr, stoelNr;
    private TicketType ticketType;
    private Boeking boeking;


    public Ticket(Boeking boeking, TicketType ticketType, int rijNr, int stoelNr){    
        //setters
    }

    @Override
    public int hashCode(){
        return boeking.getBoekingDatum().hashCode();     
    }

    @Override
    @SuppressWarnings("EqualsWhichDoesntCheckParameterClass")    
    public boolean equals(Object o){
       Ticket t = (Ticket) o;

       if(this.boeking.equals(t.getBoeking())
               &&
          this.rijNr == t.getRijNr() &&  this.stoelNr == t.getStoelNr()
               &&
          this.ticketType.equals(t.getTicketType()))
       {
           return true;
       }

       else return false;

    }

    /*I adjusted compareTo this way because I need to make sure there are no duplicate Tickets in my treeset. Treeset seems to call CompareTo() to check for equality before adding an object to the set, instead of equals().


     */
    @Override
    public int compareTo(Object o) {
        int output = 0;
        if (boeking.compareTo(((Ticket) o).getBoeking())==0)
        {
            if(this.equals(o))
            {
                return output;
            }
            else return 1;
        }
        else output = boeking.compareTo(((Ticket) o).getBoeking());
        return output;
    }

    //Getters & Setters

回答by polygenelubricants

On compareTocontract

在compareTo合同

The problem is in your compareTo. Here's an excerpt from the documentation:

问题出在你的compareTo. 这是文档的摘录：

Implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x))for all xand y.

实施者必须确保sgn(x.compareTo(y)) == -sgn(y.compareTo(x))所有x和y.

Your original code is reproduced here for reference:

此处复制您的原始代码以供参考：

// original compareTo implementation with bug marked

@Override
public int compareTo(Object o) {
    int output = 0;
    if (boeking.compareTo(((Ticket) o).getBoeking())==0)
    {
        if(this.equals(o))
        {
            return output;
        }
        else return 1; // BUG!!!! See explanation below!
    }
    else output = boeking.compareTo(((Ticket) o).getBoeking());
    return output;
}

Why is the return 1;a bug? Consider the following scenario:

为什么是return 1;bug？考虑以下场景：

• Given Ticket t1, t2
• Given t1.boeking.compareTo(t2.boeking) == 0
• Given t1.equals(t2)return false
• Now we have both of the following:
  • t1.compareTo(t2)returns 1
  • t2.compareTo(t1)returns 1

• 给定的 Ticket t1, t2
• 给定的 t1.boeking.compareTo(t2.boeking) == 0
• 给定t1.equals(t2)回报false
• 现在我们有以下两个：
  • t1.compareTo(t2)回报 1
  • t2.compareTo(t1)回报 1

That last consequence is a violationof the compareTocontract.

这最后的结果是违反了的compareTo合同。

---

---

Fixing the problem

解决问题

First and foremost, you should have taken advantage of the fact that Comparable<T>is a parameterizable generic type. That is, instead of:

首先，您应该利用Comparable<T>可参数化泛型类型这一事实。也就是说，而不是：

// original declaration; uses raw type!
public class Ticket implements Comparable

it'd be much more appropriate to instead declare something like this:

改为声明如下内容会更合适：

// improved declaration! uses parameterized Comparable<T>
public class Ticket implements Comparable<Ticket>

Now we can write our compareTo(Ticket)(no longer compareTo(Object)). There are many ways to rewrite this, but here's a rather simplistic one that works:

现在我们可以编写我们的compareTo(Ticket)（不再是compareTo(Object)）。有很多方法可以重写它，但这里有一个相当简单的方法：

@Override public int compareTo(Ticket t) {
   int v;

   v = this.boeking.compareTo(t.boeking);
   if (v != 0) return v;

   v = compareInt(this.rijNr, t.rijNr);
   if (v != 0) return v;

   v = compareInt(this.stoelNr, t.stoelNr);
   if (v != 0) return v;

   v = compareInt(this.ticketType, t.ticketType);
   if (v != 0) return v;

   return 0;
}
private static int compareInt(int i1, int i2) {
   if (i1 < i2) {
     return -1;
   } else if (i1 > i2) {
     return +1;
   } else {
     return 0;
   }
}

Now we can also define equals(Object)in terms of compareTo(Ticket)instead of the other way around:

现在我们也可以定义equals(Object)为，compareTo(Ticket)而不是相反：

@Override public boolean equals(Object o) {
   return (o instanceof Ticket) && (this.compareTo((Ticket) o) == 0);
}

Note the structure of the compareTo: it has multiple returnstatements, but in fact, the flow of logic is quite readable. Note also how the priorityof the sorting criteria is explicit, and easily reorderable should you have different priorities in mind.

注意 : 的结构，compareTo它有多个return语句，但实际上，逻辑流程是相当可读的。还要注意排序标准的优先级是如何明确的，如果你有不同的优先级，很容易重新排序。

Related questions

相关问题

• What is a raw type and why shouldn't we use it?
• How to sort an array or ArrayList ASC first by x and then by y?
• Should a function have only one return statement?

• 什么是原始类型，为什么我们不应该使用它？
• 如何先按 x 然后按 y 对数组或 ArrayList ASC 进行排序？
• 一个函数应该只有一个 return 语句吗？

回答by Paul Tomblin

This could happen if your compareTo method isn't consistent. I.e. if a.compareTo(b) > 0, then b.compareTo(a)must be < 0. And if a.compareTo(b) > 0and b.compareTo(c) > 0, then a.compareTo(c)must be > 0. If those aren't true, TreeSet can get all confused.

如果您的 compareTo 方法不一致，则可能会发生这种情况。即 if a.compareTo(b) > 0, then b.compareTo(a)must be < 0. If a.compareTo(b) > 0and b.compareTo(c) > 0, then a.compareTo(c)must be > 0. 如果这些都不是真的， TreeSet 可能会混淆。

回答by Stephen C

Firstly, if you are using a TreeSet, the actual behavior of your hashCodemethods won't affect the results. TreeSetdoes not rely on hashing.

首先，如果您使用的是TreeSet，则hashCode方法的实际行为不会影响结果。 TreeSet不依赖散列。

Really we need to see more code; e.g. the actual implementations of the equalsand compareTomethods, and the code that instantiates the TreeSet.

我们真的需要看到更多的代码；例如equals和compareTo方法的实际实现，以及实例化TreeSet.

However, if I was to guess, it would be that you have overloadedthe equalsmethod by declaring it with the signature boolean equals(Ticket other). That would lead to the behavior that you are seeing. To get the required behavior, you must overridethe method; e.g.

但是，如果我猜测，那将是您通过使用签名声明方法来重载该equals方法boolean equals(Ticket other)。这将导致您所看到的行为。要获得所需的行为，您必须覆盖该方法；例如

@Override
public boolean equals(Object other) { ...

(It is a good idea to put in the @Overrideannotation to make it clear that the method overrides a method in the superclass, or implements a method in an interface. If your method isn't actually an override, then you'll get a compilation error ... which would be a good thing.)

（最好在@Override注解中明确该方法覆盖超类中的方法，或实现接口中的方法。如果您的方法实际上不是覆盖，那么您将获得编译错误......这将是一件好事。）

EDIT

编辑

Based on the code that you have added to the question, the problem is not overload vs override. (As I said, I was only guessing ...)

根据您添加到问题中的代码，问题不在于重载与覆盖。（正如我所说，我只是猜测......）

It is most likely that the compareToand equalsare incorrect. It is still not entirely clear exactly where the bug is because the semantics of both methods depends on the compareToand equalsmethods of the Boekingclass.

很可能compareTo和equals是不正确的。仍然不完全清楚错误在哪里，因为这两种方法的语义都取决于类的compareTo和equals方法Boeking。

The first if statement of the Ticket.compareTolooks highly suspicious. It looks like the return 1;could cause t1.compareTo(t2)and t2.compareTo(t1)to both return 1for some tickets t1and t2... and that would definitelybe wrong.

第一个 if 语句Ticket.compareTo看起来非常可疑。看起来这return 1;可能会导致t1.compareTo(t2)并t2.compareTo(t1)同时返回1一些门票t1和t2......这肯定是错误的。