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

Question

我尝试编写一个存储非相等对对象的程序，由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

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））。