TreeSet is adding duplicate values to the Set

Question

I am solving a problem. I have to create a TreeSet of custom Employee objects where data should be sorted by salary but employee Id needs to be unique. I understand that equals() and hashCode() method doesn't work for TreeSet and we need to write our object are equal or not logic inside the compareTo() method. I am checking if both employee Id are equal then return 0, means object should not be added.

But the output is not coming as desired as employees with same employee Id are also getting added. I tried to debug this but I am not getting the right answer.

This is the code.

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;
        }
    }
}   

The main method of program

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);
        }
    }

The output of above program comes out as

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

Here as you can see employees with same employee Id are being added to the TreeSet which should not happen. If I am using a HashSet the problem is resolved, but I have to implement it using TreeSet to get the sorted behaviour.

Can someone please guide me where am I going wrong?

Answer 1

The implementation of Comparable violates the contract of Comparable::compareTo, in particular this part:

Finally, the implementor must ensure that x.compareTo(y)==0 implies that signum(x.compareTo(z)) == signum(y.compareTo(z)), for all z.

We can demonstrate this violation with the following code:

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

leading to the following output:

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

Ideone demo

We can fix this issue by dropping the salary from the compareTo-method and only order by empId:

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

Ideone demo