java - 为什么 TreeSet 在添加新元素之前不比较所有元素？

Question

我尝试编写一个程序来存储由 2 个字符串组成的不等对对象。就此而言， (john, bob) 对被认为等于 (bob, john)。我的 equals 和 CompareTo 实现应该可以正常工作。为了检查出了什么问题，我让程序输出对我尝试添加的每个新对进行的比较。看起来像这样:

@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

Answer 1

一个: 回答你的问题:TreeSet不需要比较所有元素，因为元素有一个定义的顺序。考虑一本字典:在中间打开它，您会立即知道您需要的单词是在该页之前还是之后。您不需要检查字典的两半部分。

两个: 您的 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契约(Contract):

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y.