为什么树集在添加新元素之前不比较所有元素？

Question

我尝试编写一个存储非相等对对象的程序，由2个字符串组成。就此而言，这对（约翰，鲍勃）被认为是等于（鲍勃，约翰）。我的等价和比较到实现应该工作正常。为了检查出了什么问题，我让我的程序输出为我尝试添加的每个新对所做的比较。看起来像这样：@Overridepublic boolean equals(Object o){    if (o==null){        return false;    }    final Pair other = (Pair) o;    return (this.compareTo(other)==0);}@Overridepublic 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 john2 not equal john john and  bob johnequal: john john and  john john2equal: john bob and  bob john2 not equal bob will and  bob john not equal bob will and  john john3 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

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

二：你的比较To（）方法有问题。考虑两个对象：

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

在这两种情况下，您的 compareTo（） 都将返回 -1，它不能：

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

从数学上讲，您的关系“compareTo”没有定义订单，因此违反了API合约：

实现者必须确保所有 x 和 y 的 sgn（x.比较到 y）） == -sgn（y.比较到（x））。