TreeSet正在向集合中添加重复的值。

Question

TreeSet正在向集合中添加重复的值。

5

我正在解决一个问题。我必须创建一个自定义员工对象的TreeSet，按照薪水排序，但员工ID需要唯一。我了解到 TreeSet 不适用 equals() 和 hashCode() 方法，我们需要在 compareTo() 方法中编写对象是否相等的逻辑。我检查如果两个员工ID相等，则返回0，意味着不应添加对象。

但实际运行结果与预期不符，相同员工ID的员工也被添加进来了。我尝试调试代码，但没有得到正确的答案。

这是代码：

public class Employee implements Comparable<Employee>{
    int empId;
    String empName;
    double salary;
    
    public Employee() {
        super();
    }

    public Employee(int empId, String empName, double salary) {
        super();
        this.empId = empId;
        this.empName = empName;
        this.salary = salary;
    }
    
    @Override
    public int hashCode() {
        return empId;
    }
    
    @Override
    public boolean equals(Object o) {
        if(this == o) return true;
        if(o == null || this.getClass() != o.getClass()) return false;
        
        Employee e = (Employee) o;
        return (this.empId == e.empId);
    }
    
    @Override
    public String toString() {
        return empId + " " + empName + " " + salary;
    }
    
    @Override
    public int compareTo(Employee e) {
        if(empId == e.empId) 
            return 0;
        
        if(this.salary < e.salary) {
            return -1;
        }
        else {
            return 1;
        }
    }
}

程序的主方法

public static void main(String[] args) {
        
        TreeSet<Employee> eSet = new TreeSet<>();
        
        eSet.add(new Employee(1, "john", 20000));
        eSet.add(new Employee(2, "jim", 10000));
        eSet.add(new Employee(9, "mike", 50000));
        eSet.add(new Employee(3, "jack", 30000));
        eSet.add(new Employee(3, "david", 40000));
        eSet.add(new Employee(9, "liam", 80000));
        eSet.add(new Employee(9, "brad", 89000));
        eSet.add(new Employee(3, "jason", 85000));
        eSet.add(new Employee(2, "ted", 35000));
        
        for(Employee e: eSet) {
            System.out.println(e);
        }
    }

以上程序的输出结果如下：

2 jim 10000.0
1 john 20000.0
3 jack 30000.0
2 ted 35000.0
9 mike 50000.0
3 jason 85000.0

在这里，您可以看到具有相同员工ID的员工被添加到TreeSet中，这是不应该发生的。如果我使用HashSet，则问题可以得到解决，但我必须使用TreeSet来获得排序行为。

请问有人能指导我错在哪里吗？

- scarletspeedster

@AlexanderIvanchenko 这不是问题所在。Comparable 接口的实现与 equals() 实现一致。问题在于排序，因为添加时（我认为是由于二进制搜索），未找到按顺序排列到与“jim”不同位置的“ted”。 - Turing85

@Turing85 嗯，我现在明白了，你是对的，实现是一致的。 - Alexander Ivanchenko

@AlexanderIvanchenko 的问题在于 Comparable 实现违反了传递性。 - Turing85

@Turing85，但具体怎么做呢？compareTo的实现如何才能通过if（empId == e.empId）测试呢？基于第一个if测试，TreeSet应该始终拒绝重复项，永远不会到达比较salary的部分。显然，我在某些方面是错误的，因为我运行了问题的代码-我也发现了重复的"2 ted"和"3 jason"。 - Basil Bourque

1

@BasilBourque 设置了一个断点。问题在于 jim 和 ted 从未被比较。 - Turing85

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Turing85 · Accepted Answer

Comparable 的实现违反了 Comparable::compareTo 的契约, 特别是这部分:

最后，实现者必须确保对于所有的 z，x.compareTo(y)==0 意味着 signum(x.compareTo(z)) == signum(y.compareTo(z))。

我们可以使用以下代码证明此违规：

final Employee jim = new Employee(2, "jim", 10_000);
final Employee ted = new Employee(2, "ted", 35_000);
final Employee john = new Employee(9, "john", 20_000);

System.out.println("jim compare to ted: " + jim.compareTo(ted));
System.out.println("john compare to jim: " + john.compareTo(jim));
System.out.println("john compare to ted: " + john.compareTo(ted));

导致以下输出：

jim compare to ted: 0
john compare to jim: 1
john compare to ted: -1

Ideone演示

我们可以通过从compareTo方法中删除薪水并仅按empId排序来解决此问题:

@Override
public int compareTo(Employee e) {
  return Integer.compare(empId, e.empId);
}

Ideone演示