MET19-J. Ensure that keys used in comparison operations cannot be changed

Objects that serve as keys in ordered sets and maps should be immutable. When some fields must be mutable, the equals(), hashCode() and compareTo() methods must consider only immutable state when comparing objects. Violations of this rule can produce inconsistent orderings in collections. The documentation of java.util.Interface Set<E> and java.util.Interface Map<K,V> warn against this [[API 2006]]:

Note: great care must be exercised [when] mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a map.

Noncompliant Code Example

This noncompliant code example defines a mutable class Employee that consists of the fields name and salary, whose values can be changed using the respective setters. The equals() method is overridden to provide a comparison facility by employee name.

// Mutable class Employee
class Employee {
  private String name;
  private double salary;
 
  Employee(String empName, double empSalary) {
    this.name = empName;
    this.salary = empSalary;
  }
  
  public void setEmployeeName(String empName) {
    this.name = empName;   
  }

  // ... including a hashCode implementation

  @Override public boolean equals(Object o) {
    if (!(o instanceof Employee)) {
      return false;
    }
      
    Employee emp = (Employee)o;
    return emp.name.equals(name);
  } 
}

// Client code
Map<Employee, Calendar> map = new ConcurrentHashMap<Employee, Calendar>();
// ...

Use of the Employee object as a key for the map is insecure because the properties of the object may change after an ordering has been established. For example, a client may modify the name field when the last name of an employee changes. Consequently, clients may observe non-deterministic behavior.

Compliant Solution

This compliant solution adds a final field employeeID that is immutable after initialization. The equals() method compares Employee objects on the basis of this field.

// Mutable class Employee
class Employee {
  private String name;
  private double salary;
  private final long employeeID;  // Unique for each Employee

  Employee(String name, double salary, long empID) {
    this.name = name;
    this.salary = salary;
    this.employeeID = empID;
  }
 
  // ... including a hashCode implementation

  @Override public boolean equals(Object o) {
    if (!(o instanceof Employee)) {
      return false;
    }
      
    Employee emp = (Employee)o;
    return emp.employeeID == employeeID;
  } 
}

// Client code remains same
Map<Employee, Calendar> map = new ConcurrentHashMap<Employee, Calendar>();
// ... 

The Employee class can now be safely used as a key for the map in the client code.

Risk Assessment

Failure to ensure that the keys used in a comparison operation are immutable can lead to non-deterministic behavior.

Automated Detection

The Coverity Prevent Version 5.0 MUTABLE_COMPARISON checker can detect the instances where compareTo method is reading from a non constant field. If the non-constant field is modified, the value of compareTo might change, which may break program invariants.

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this guideline on the CERT website.

Bibliography

[[API 2006]] java.util.Interface Set<E> and java.util.Interface Map<K,V>

MET18-J. Do not use finalizers      05. Methods (MET)      MET21-J. Do not invoke equals() or hashCode() on URLs