Почему TreeSet не сравнивает все элементы перед добавлением нового элемента? - PullRequest
Новая
       75

Почему TreeSet не сравнивает все элементы перед добавлением нового элемента?

0 голосов
/ 05 апреля 2019

Я пытаюсь написать программу, которая хранит неравные парные объекты, состоящие из 2 строк.В этом отношении пара (Джон, Боб) считается равной (Боб, Джон).Мои сравнения и сравнения должны работать нормально.Чтобы проверить, что не так, я позволил моей программе выводить сравнения, сделанные для каждой новой пары, которую я пытаюсь добавить.Выглядит это так: 

@Override
public boolean equals(Object o){
    if (o==null){
        return false;
    }
    final Pair other = (Pair) o;
    return (this.compareTo(other)==0);
}



@Override
public int compareTo (Pair o){
  if (this.first.equals(o.first)){
      if (this.second.equals(o.second)){
          System.out.println("equal: "+this.first+" "+this.second+" and  " + o.first+" "+o.second);
          return 0;
      }
  }
  else if (this.first.equals(o.second)){
        if (this.second.equals(o.first)){
            System.out.println("equal: "+this.first+" "+this.second+" and  " + o.first+" "+o.second);
            return 0;
        }
  }
    System.out.println(" not equal " +this.first+" "+this.second+" and  " + o.first+" "+o.second);
  return -1;

Пример ввода: 

 bob john
 john john
 john john
 john bob
 bob will
 john hohn

Если я позволю выполнить этот прогон, он будет распечатывать размер TreeSat после каждой попытки, чтобы добавить новый элемент.Он также напечатает то, что написано в методе CompareTo.Я добавил комментарии, чтобы уточнить мою проблему. 

   equal: bob john and  bob john    //Why comparing the first element at  
                                      all?
1
 not equal john john and  bob john
2
 not equal john john and  bob john
equal: john john and  john john
2
equal: john bob and  bob john
2
 not equal bob will and  bob john
 not equal bob will and  john john
3

 not equal john hohn and  john john    //no comparision of (john hohn) and                                       
 not equal john hohn and  bob will     //(bob john) why?
4

1 Ответ

1 голос
/ 05 апреля 2019

ONE : Чтобы ответить на ваш вопрос: TreeSet не нужно сравнивать все элементы, поскольку существует определенный порядок для элементов.Рассмотрите словарь: откройте его посередине, и вы сразу узнаете, нужно ли вам слово до или после этой страницы.Вам не нужно проверять обе половины словаря.

TWO : ваш compareTo () метод неисправен.Рассмотрим два объекта: 

Pair a = Pair.of(1, 2);
Pair b = Pair.of(3, 4);

Ваш compareTo () вернет -1 в обоих случаях, которые не должны: 

a.compareTo(b) == -1
b.compareTo(a) == -1

Математически произнесенные ваши отношения "compareTo "не определяет порядок и, таким образом, нарушает API контракт:

Разработчик должен обеспечить sgn (x.compareTo (y)) == -sgn (y.compareTo)(х)) для всех х и у.

...