Treeset.contains () проблема - PullRequest
Новая
       8

Treeset.contains () проблема

9 голосов
/ 08 августа 2010

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

Я добавляю объекты Ticket в TreeSet, Ticket реализует Comparable и имеет переопределенные методы equals (), hashCode () и CompareTo (). Мне нужно проверить, есть ли уже объект в TreeSet, с помощью функции contains (). Теперь, после добавления 2 элементов в набор, все в порядке, но после добавления третьего все портится.

Запуская этот маленький кусочек кода после добавления третьего элемента в 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));

возвращает это: 

22106622
22106622
true
0
false

Теперь мой вопрос: как это вообще возможно?

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

Ответы [ 3 ]

18 голосов
/ 08 августа 2010

на compareTo контракт

Проблема в вашем compareTo. Вот выдержка из документации :

Исполнитель должен обеспечить sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) для всех x и y.

Ваш оригинальный код воспроизводится здесь для справки: 

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

Почему return 1; ошибка? Рассмотрим следующий сценарий:

  • Дано Ticket t1, t2
  • Дано t1.boeking.compareTo(t2.boeking) == 0
  • Дано t1.equals(t2) Возврат false
  • Теперь у нас есть оба из следующих:
    • t1.compareTo(t2) возвращает 1
    • t2.compareTo(t1) возвращает 1

Последнее последствие - это нарушение контракта compareTo.

Исправление проблемы

Прежде всего, вы должны были воспользоваться тем, что Comparable<T> является параметризуемым универсальным типом. То есть вместо: 

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

было бы гораздо уместнее объявить что-то вроде этого: 

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

Теперь мы можем написать наш 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;
   }
}

Теперь мы можем также определить equals(Object) в терминах compareTo(Ticket), а не наоборот: 

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

Обратите внимание на структуру compareTo: она имеет несколько операторов return, но на самом деле поток логики вполне читабелен. Обратите также внимание на то, что приоритет критериев сортировки является явным и легко переставляемым, если вы имеете в виду различные приоритеты.

Смежные вопросы

4 голосов
/ 08 августа 2010

Это может произойти, если ваш метод CompareTo не соответствует. То есть если a.compareTo(b) > 0, то b.compareTo(a) должно быть <0. А если <code>a.compareTo(b) > 0 и b.compareTo(c) > 0, то a.compareTo(c) должно быть> 0. Если это не так, TreeSet может запутать все.

3 голосов
/ 08 августа 2010

Во-первых, если вы используете TreeSet, фактическое поведение ваших hashCode методов не повлияет на результаты.TreeSet не зависит от хеширования.

На самом деле нам нужно увидеть больше кода;например, фактические реализации методов equals и compareTo и код, который создает экземпляр TreeSet.

Однако, если бы я догадался, у вас будет перегружен метод equals, объявив его с подписью boolean equals(Ticket other).Это привело бы к поведению, которое вы видите.Чтобы получить требуемое поведение, вы должны переопределить метод;например, 

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

(Рекомендуется добавить аннотацию @Override, чтобы было ясно, что метод переопределяет метод в суперклассе или реализует метод в интерфейсе. Если ваш метод нена самом деле это не переопределение, тогда вы получите ошибку компиляции ... что было бы хорошо.)

EDIT

На основе кода, который выдобавили в вопрос, проблема не в перегрузке, а в переопределении.(Как я уже сказал, я только догадывался ...)

Скорее всего, compareTo и equals неверны.До сих пор не совсем ясно, где именно ошибка, потому что семантика обоих методов зависит от методов compareTo и equals класса Boeking.

Первое выражение if из Ticket.compareTo выглядит крайне подозрительно.Похоже, что return 1; может заставить t1.compareTo(t2) и t2.compareTo(t1) оба возвращать 1 для некоторых билетов t1 и t2 ... и это определенно будет неправильным.

...