java - 为什么 TreeSet 在添加新元素之前不比较所有元素?
问题描述
我尝试编写一个程序来存储不相等的对对象,由 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
解决方案
一:回答你的问题: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合同:
实现者必须确保所有 x 和 y 的 sgn(x.compareTo(y)) == -sgn(y.compareTo(x))。
推荐阅读
- php - FOREACH 循环返回双重结果
- c# - ComboBox 上的不同部分
- mysql - Haproxy根据请求中的域名对Mysql Connections进行负载均衡
- java - 在奥利奥,我无法获得拨出号码
- regex - 使用惰性正则表达式从 Google 文档中提取所有标签
- java - 具有无效字符的java xml
- visual-studio-2017 - 无法在 Visual Studio 2017 中调试
- windows - 批处理文件查找连接的 Citrix 服务器
- python-3.x - 使用 wForms 在 0x07808D68 处获取输出 .lazy_gettext 的 make_lazy_gettext>
- c# - c# 展平二维数组,获取二维,不循环