为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

天涯尽头无女友 2022-09-22 19:56:59

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

?
慕妹3242003

TA贡献1486条经验 获得超6个赞

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


查看完整回答
反对 回复 2022-09-22

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信