Java 8: Map does not look up keys which obviously contains!

We have experienced strange bug in our application: Map::keySet() returned keys which was not possible lookup using Map::get(T key) even during iteration over its result. Strange, right?

map.keySet().foreach (key->{ 
    if (!map.containsKey(key)) { 
        throw new RuntimeException("Huh?");   //this actually happens! 
    } 
});

Debugging of that was hard. We had to  exclude factors like other threads, broken build, etc. But in the end we started to be suspicious about implementation of hashCode() and equals() method of object used as key in map. Close but not hit.

Method hashCode was implemented in the way that it returned same hashCode for most of possible values of key. That put most of values into single bucket in internal Map structure. It was hard to calculate reliable hashCode in this case so programmers intention was to focus on equals() method. Of course that means that often many values should be tested by equals() method, but for small data it is no issue.

But for case when many items fall into same bucket was introduced new optimization in Java8. If programmer delivers poor hashCode() implementation AND key class implements Comparable interface then Java tries to use tree instead of list in bucket. See comment in source code.

Therefore it is really necessary to correctly implement Comparable interface. And, you are right, our was implemented poorly:

int compareTo(T o) { 
    if (o.equals(this)) { 
        return 0; 
    } 
    
    return 1; 
}

Therefore it depends on “this” object during compareTo() call. When compareTo() was called on A then B was considered as bigger.When compareTo() was called on B then A was considered as bigger. Although they still are same two objects. So our implementation broke compareTo() contract. When during inserting into bucket tree was compareTo() called on A but during lookup on B then lookup failed.

Solution was to correctly implement compareTo().