HashMaps with Comparable keys not working as expected

Question

We're facing weird issues with how HashMap behaves.

When HashMap keys implement Comparable interface but compareTo implementation is inconsistent with equals then HashMaps:

grow much larger then they are supposed to grow
they contain several instances of equal elements
values attached to those elements might differ
get(key) result depends on which key is used (even if the keys are equal according to equals method).

I've created a small test to reproduce the problem (see below).

import java.util.HashMap;
import java.util.Map;

public class HashMapTest {
private static final char MIN_NAME = 'A'; 
private static final char MAX_NAME = 'K'; 
private static final int EXPECTED_NUMBER_OF_ELEMENTS = MAX_NAME - MIN_NAME + 1; 

private HashMap<Person, Integer> personToAgeMap; 

HashMapTest(){
    personToAgeMap = new HashMap(); 
}

public static void main(String[] args){
    HashMapTest objHashMap = new HashMapTest();
    System.out.println("Initial Size of Map: " + objHashMap.getPersonToAgeMap().size());
    objHashMap.whenOverridingEqualElements_thenSizeOfTheMapIsStable();
    objHashMap.whenGettingElementUsingPersonOfAge1_thenOverridenValuesAreReturned();
    objHashMap.whenGettingElementUsingPersonOfAge100_thenOverridenValuesAreReturned();
    objHashMap.whenGettingElementUsingPersonOfAge50_thenOverridenValuesAreReturned();
    objHashMap.whenGettingElementUsingPersonOfAgeMinus1_thenOverridenValuesAreReturned();
}

public HashMap<Person, Integer> getPersonToAgeMap(){
    return personToAgeMap;
}

public void whenOverridingEqualElements_thenSizeOfTheMapIsStable() { 
    System.out.println("Adding elements with age 1..");
    putAllPeopleWithAge(personToAgeMap, 1);
    System.out.println(personToAgeMap);
    System.out.println("Expected Number Of elements: " + EXPECTED_NUMBER_OF_ELEMENTS+ "\nActual Number of elements: "+personToAgeMap.size());

    System.out.println();
    System.out.println("Overwriting map, with value 100..");
    putAllPeopleWithAge(personToAgeMap, 100);
    System.out.println(personToAgeMap);
    System.out.println("Expected Number Of elements: " + EXPECTED_NUMBER_OF_ELEMENTS+ "\nActual Number of elements: "+personToAgeMap.size());
    System.out.println();
} 


public void whenGettingElementUsingPersonOfAge1_thenOverridenValuesAreReturned() {      
    useAgeToCheckAllHashMapValuesAre(1, 100); 
} 


public void whenGettingElementUsingPersonOfAge100_thenOverridenValuesAreReturned() {  
    useAgeToCheckAllHashMapValuesAre(100, 100); 
} 

public void whenGettingElementUsingPersonOfAge50_thenOverridenValuesAreReturned() {  
    useAgeToCheckAllHashMapValuesAre(50, 100); 
} 


public void whenGettingElementUsingPersonOfAgeMinus1_thenOverridenValuesAreReturned() {        
    useAgeToCheckAllHashMapValuesAre(-10, 100); 
}

private void useAgeToCheckAllHashMapValuesAre(int age, Integer expectedValue) { 
    System.out.println("Checking the values corresponding to age = " + age);
    StringBuilder sb = new StringBuilder(); 

    int count = countAllPeopleUsingAge(personToAgeMap, age); 
    System.out.println("Count of People with age " + age+" =" + count);

    if (EXPECTED_NUMBER_OF_ELEMENTS != count) { 
        sb.append("Size of the map ").append(" is wrong: ") 
            .append("expected <").append(EXPECTED_NUMBER_OF_ELEMENTS).append("> actual <").append(count).append(">.\n"); 
    } 

    for (char name = MIN_NAME; name <= MAX_NAME; name++) { 
        Person key = new Person(name, age); 
        Integer value = personToAgeMap.get(key); 
        if (!expectedValue.equals(value)) { 
            sb.append("Unexpected value for ").append(key).append(": ") 
            .append("expected <").append(expectedValue).append("> actual <").append(value).append(">.\n"); 
        } 
     } 

    if (sb.length() > 0) { 
        System.out.println(sb.toString());
    } 
   } 

 void putAllPeopleWithAge(Map<Person, Integer> map, int age) { 
    for (char name = MIN_NAME; name <= MAX_NAME; name++) { 
        map.put(new Person(name, age), age); 
    } 
   } 

 int countAllPeopleUsingAge(Map<Person, Integer> map, int age) { 
    int counter = 0; 
    for (char name = MIN_NAME; name <= MAX_NAME; name++) { 
        if (map.containsKey(new Person(name, age))) { 
            counter++; 
        } 
    } 
    return counter; 
   } 

 String getAllPeopleUsingAge(Map<Person, Integer> map, int age) { 
    StringBuilder sb = new StringBuilder(); 
    for (char name = MIN_NAME; name <= MAX_NAME; name++) { 
        Person key = new Person(name, age); 
        sb.append(key).append('=').append(map.get(key)).append('\n'); 
    } 
    return sb.toString(); 
   } 

 class Person implements Comparable<Person> { 
    char name; 
    int age; 

    public Person(char name, int age) { 
        this.name = name; 
        this.age = age; 
    } 

    //Making sure all elements end up in the very same bucket 
    //Nothing wrong with it except performance... 
    @Override 
    public int hashCode() { 
        return 0; 
    } 

    //equals is only by name 
    @Override 
    public boolean equals(Object other) { 
        Person otherPerson = (Person)other; 
        return this.name == otherPerson.name; 
     } 

     public String toString() { 
        return name + "[age=" + age + "]"; 
     } 

    //comparing by age 
    //NOTE: compareTo is inconsistent with equals which should be OK in non-sorted collections 
    //https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html 
    @Override 
    public int compareTo(Person other) { 
        return this.age - other.age; 
      } 
   } 
   }

Expected Output

  Initial Size of Map: 0
 Adding elements with age 1..
{K[age=1]=1, J[age=1]=1, I[age=1]=1, H[age=1]=1, G[age=1]=1, F[age=1]=1,    E[age=1]=1, D[age=1]=1, C[age=1]=1, B[age=1]=1, A[age=1]=1}
Expected Number Of elements: 11
Actual Number of elements: 11

Overwriting map, with value 100..
{K[age=1]=100, J[age=1]=100, I[age=1]=100, H[age=1]=100, G[age=1]=100,  F[age=1]=100, E[age=1]=100, D[age=1]=100, C[age=1]=100, B[age=1]=100, A[age=1]=100}
 Expected Number Of elements: 11
 Actual Number of elements: 11

 Checking the values corresponding to age = 1
 Count of People with age 1 =11
 Checking the values corresponding to age = 100
 Count of People with age 100 =11
 Checking the values corresponding to age = 50
 Count of People with age 50 =11
 Checking the values corresponding to age = -10
 Count of People with age -10 =11

Actual OutPut

Initial Size of Map: 0
Adding elements with age 1..
{I[age=1]=1, A[age=1]=1, B[age=1]=1, C[age=1]=1, D[age=1]=1, E[age=1]=1,  F[age=1]=1, G[age=1]=1, H[age=1]=1, J[age=1]=1, K[age=1]=1}
Expected Number Of elements: 11
Actual Number of elements: 11

Overwriting map, with value 100..
{I[age=1]=100, A[age=1]=1, B[age=1]=100, C[age=1]=1, D[age=1]=100, A[age=100]=100, C[age=100]=100, E[age=100]=100, H[age=100]=100, J[age=100]=100, K[age=100]=100, F[age=100]=100, G[age=100]=100, E[age=1]=1, F[age=1]=1, G[age=1]=1, H[age=1]=1, J[age=1]=1, K[age=1]=1}
  Expected Number Of elements: 11
  Actual Number of elements: 19

  Checking the values corresponding to age = 1
  Count of People with age 1 =11
  Unexpected value for E[age=1]: expected <100> actual <1>.
  Unexpected value for F[age=1]: expected <100> actual <1>.
 Unexpected value for G[age=1]: expected <100> actual <1>.
 Unexpected value for J[age=1]: expected <100> actual <1>.
  Unexpected value for K[age=1]: expected <100> actual <1>.

  Checking the values corresponding to age = 100
 Count of People with age 100 =10
 Size of the map  is wrong: expected <11> actual <10>.
 Unexpected value for B[age=100]: expected <100> actual <null>.

 Checking the values corresponding to age = 50
 Count of People with age 50 =5
 Size of the map  is wrong: expected <11> actual <5>.
 Unexpected value for B[age=50]: expected <100> actual <null>.
 Unexpected value for E[age=50]: expected <100> actual <null>.
 Unexpected value for F[age=50]: expected <100> actual <null>.
 Unexpected value for G[age=50]: expected <100> actual <null>.
 Unexpected value for J[age=50]: expected <100> actual <null>.
 Unexpected value for K[age=50]: expected <100> actual <null>.

 Checking the values corresponding to age = -10
 Count of People with age -10 =4
 Size of the map  is wrong: expected <11> actual <4>.
 Unexpected value for A[age=-10]: expected <100> actual <1>.
 Unexpected value for B[age=-10]: expected <100> actual <null>.
 Unexpected value for C[age=-10]: expected <100> actual <1>.
 Unexpected value for D[age=-10]: expected <100> actual <null>.
 Unexpected value for E[age=-10]: expected <100> actual <1>.
 Unexpected value for F[age=-10]: expected <100> actual <null>.
 Unexpected value for G[age=-10]: expected <100> actual <null>.  
 Unexpected value for H[age=-10]: expected <100> actual <null>.
 Unexpected value for J[age=-10]: expected <100> actual <null>.
  Unexpected value for K[age=-10]: expected <100> actual <null>.

compareTo implementation is inconsistent with equals if you implement boolean compareTo(Object o) incorrectly, you may run the risk of something behind the scenes attempting to sort based on compareTo and ending up sorting incorrectly/duplicating elements in sets — phflack
Comparable should be consistent with Equals and Hashcode... It's a bad practice if they are not and can lead to strange results. If you have to compare your objects with another value, use a Comparator instead. — Guillaume F.
Also note that in general incorrect implementations of interfaces will probably lead to incorrect results from things using that interface — phflack
//NOTE: compareTo is inconsistent with equals which should be OK in non-sorted collections //docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html — Sachin Sachdeva
Can you create an MCVE? (Minimal, Complete, and Verifiable example, with the emphasis on "Minimal", you can make a much shorter test than this) stackoverflow.com/help/mcve — Erwin Bolwidt

chrylis -cautiouslyoptimistic- chrylis -cautiouslyoptimistic- · Accepted Answer · 2015-12-16T07:41:09

As of Java 8, an optimization was added to HashMap to deal with collisions when keys are Comparable:

To ameliorate impact, when keys are java.lang.Comparable, this class may use comparison order among keys to help break ties.

If your keys have a natural ordering that is inconsistent with equals(), any number of odd things may happen, and in this case it looks like the map is trying to keep track of keys using the natural ordering.

HashMaps with Comparable keys not working as expected

2 Answers