Is it a bug that Java 8's HashMap misbehaves if the keys implement Comparable in a way that isn't consistent with equals?

Question

I know that since Java 8, if a HashMap has enough hash collisions, and the keys implement Comparable, it will use a balanced tree instead of a linked list for the bin. But from what I can see, the Comparable interface does not require that compareTo() be "consistent with equals()" (though it is strongly recommended).

Did I miss something? It seems like the new implementation allows HashMap to violate the requirements of the Map interface if the keys happen to have a compliant, but non-recommended Comparable implementation.

The following JUnit test exposes this behaviour on OpenJDK 8u72:

import static org.junit.Assert.*;

import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

class Foo
        implements Comparable<Foo> // Comment this out to fix the test case
{
    private final int bar;
    private final int baz;

    Foo(int bar, int baz) {
        this.bar = bar;
        this.baz = baz;
    }

    public boolean equals(Object obj) {
        // Note that this ignores 'baz'
        return obj instanceof Foo && bar == ((Foo) obj).bar;
    }

    public int hashCode() {
        return 0;
    }

    public int compareTo(Foo o) {
        // Inconsistent with equals(), but seems to obey the requirements of
        // Comparable<Foo>
        return Integer.compare(baz, o.baz);
    }
}

public class FooTest {
    @Test
    public void test() {
        Set<Foo> set = new HashSet<>();
        for (int i = 0; i < 128; ++i) {
            set.add(new Foo(i, 0));
        }

        // This fails if Foo implements Comparable<Foo>
        assertTrue(set.contains(new Foo(64, 1)));
    }
}

Answer 1

It's not a bug anywhere IMO, in that the code is behaving as the implementor expected - but this is a known result of an unusual Comparable implementation. From the Comparable documentation:

It is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals. In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

Now while this isn't a sorted set or map in the normal sense, there's a clear relationship to the issue.

I agree that it's a possible issue though, and a really subtle one, particularly as it'll be hard to reproduce in simple situations. I would update your documentation to draw very strong attention to the fact that your class implements Comparable in a way which is inconsistent with equals, and specifically refer to this as a potential issue.

Answer 2

First, let’s recall what consistency between equals and compareTo implies:

(Comparable)

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C.

So one scenario for a natural ordering not being consistent with equals is an ordering where e1.compareTo(e2) might return zero despite e1.equals(e2) returns false. An example would be a case insensitive ordering combined with a case sensitive equality. Another example is BigDecimal which has a natural ordering where new BigDecimal("1.0").compareTo(BigDecimal.ONE) returns zero but new BigDecimal("1.0").equals(BigDecimal.ONE) returns false.

Note that the new HashMap implementation handles these cases. The natural ordering only helps to find a candidate, but a candidate will only considered equal, if the equals method returns true. This implies that when you have a lot of keys with the same hashcode and being equal according to their natural ordering but not regarding equals, you again end up with a linear search amongst these keys like in the old implementation.

In contrast, your example in an entirely different case. Your compareTo implementation may tell that two objects are not equal despite an equals test would return true. This would never happen with BigDecimal or any other practical example of a natural ordering not consistent with equals, I know of.

Your case is not supported by the current implementation, but as you might have noticed, still will only break if the objects also have the same hash code. I doubt that this scenario has a practical relevance. All examples I have seen so far are just constructed after learning about the new HashMap implementation.

Answer 3

No, it is a documented implementation constraint, and a bug in the implementation of Comparable.