TreeMap put() silently deletes other entries?

Question

I've experienced some really spooky TreeMap behavior and I've had some trouble narrowing down a small test case, so bear with me.

I want to read a large number of key-value pairs into a Map, from a file provided at runtime. I'm using a custom key class. Later, when I go to pull entries back out, I find that one or more of them are missing. Using a debugger and some test cases, I've determined that the missing entry(ies) are definitely disappearing during the read phase, but I'm not sure what's causing it.

Basically:

Map<MyKey,Double> map = new TreeMap<MyKey,Double>();
map.put(key1,value1);

// ... put another ~500 entries into the map ...

assertTrue(map.containsKey(key1)); // passes
if (!map.containsKey(keyN)) { 
    map.put(keyN, valueN); // this code executes
}
assertTrue(map.containsKey(key1)); // FAILS

...So essentially, adding a brand new key to the map causes an unrelated entry to fall out of it.

• If I just add key1 and keyN alone, key1 remains in the map -- the intervening 500 entries are somehow important
• If I remove one or two arbitrary keys from 2..(N-1), key1 is still booted out when keyN is added
• If I remove a large range of keys from 2..(N-1), key1 remains when keyN is added, but falls out when (say) keyQ is added, ~300 keys further down the line
• Unfortunately the size of the map when keyN kicks out key1 is not the same as the size of the map when keyQ kicks out key1, so it's probably not a limited-size issue
• If I use a HashMap instead, key1 remains in the map
• Custom key class MyKey uses the same logic for Comparable, equals, and hashCode.

I was initially using TreeMap because I expect to be using large datasets, and TreeMap is a little more memory-efficient. HashMap will be a fine alternative, but it's still alarming to see TreeMap behave this way -- anyone have thoughts on what's going on here?

Answer 1

Show us the code for MyKey. My guess is that there's something wrong with your compareTo method. More specifically your compareTo is not consistent with equals.

Answer 2

TreeMap thinks of two entries being equal if, when compared, the result is 0. So if key1 and keyN 'compare to' 0, then key1 will be overwritten by keyN being put(). This is true even if !key1.equals(keyN). So while you may think that those two keys are not equal, and so inserting one should not overwrite the other, the TreeMap will think different if your equals and comparison functions are inconsistent with each other.

Note that this behavior may vary depending on the number of elements in the map, because it depends on actually comparing two elements who's compare method evaluates to 0. Basically, things will act, as you say, 'spooky'.

From the TreeMap javadocs:

...map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal...

and from the Comparable javadocs (thanks @Brian):

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.