Java 8 Hash Map not working properly

Question

We're facing weird issues with how HashMap behaves since java 8.

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). The test always passes with Java 7 (and probably previous versions). The test always fails with Java 8 (unless I remove Comparable interface from the class).

I'm not sure how fixable this is and if it's not would it be possible to explicitly underline in javadoc that compareTo MUST be consistent with equals if the objects are to be used in hash-collections.

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 + "]";
    }

    // compareTo is inconsistent with equals which should be OK in
    // non-sorted collections
    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }
   }
}

Answer 1

The HashMap documentation says:

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

So if one uses Comparable elements with an inconsistent comparison order, one has to expect odd behavior like this.

The behavior is also explicitly mentioned in the implementation notes of HashMap in Java 8:

/*
 * Implementation notes.
 *
 ...
 * Tree bins (i.e., bins whose elements are all TreeNodes) are
 * ordered primarily by hashCode, but in the case of ties, if two
 * elements are of the same "class C implements Comparable<C>",
 * type then their compareTo method is used for ordering. (We
 * conservatively check generic types via reflection to validate
 * this -- see method comparableClassFor). 
 ...

This was introduced in the following change in the OpenJDK: http://hg.openjdk.java.net/jdk8/jdk8/jdk/diff/d62c911aebbb/src/share/classes/java/util/HashMap.java#l1.73

Answer 2

I think this would be the real problem

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

You are comparing strings with ==, what about this?

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