Java TreeMap Duplicate Keys

Question

I think I may have found a bug in Java.

I have a TreeMap in which I use a custom comparator. However, it seems when I put(key, value), on a key that already exists, it does not override the key, thus creating duplicate keys. I think I have verified this because I tried:

System.out.println(testMap.firstKey().equals(testMap.lastKey()));

And this prints out true. Anyone know why this is happening?

This is the comparator code:

private class TestComp implements Comparator<String> {
    @Override
    public int compare(String s1, String s2){

        if (s1.equals(s2)) {
            return 0;
        }
        int temp = otherMap.get(s1).compareTo(otherMap.get(s2));
        if (temp > 0) {
            return 1;
        }
        return -1;

    }

how many entries do you have in the `TreeMap`? If it's only one, first and last have to be the same ^^ — Alexander, Mar 12 '15 at 08:33
Please show your complete code. From this line one can not evaluate what your are doing. — Uwe Allner, Mar 12 '15 at 08:34
There is more than one entry and I have verfied this by printing out the size? What do you mean by transitive and consistent? Also, does it really matter what the comparator code is? Shouldn't Java automatically not allow duplicate keys in the entrySet? — bkmoney, Mar 12 '15 at 08:34
Do the object in the map correctly implement `equals()` **and** `hashCode()`? — Alexander, Mar 12 '15 at 08:35
Check here for more info http://stackoverflow.com/questions/21749386/duplicate-key-in-treemap — arados, Mar 12 '15 at 08:36
The keys are Strings so shouldn't equals and hashCode work fine? — bkmoney, Mar 12 '15 at 08:37
@bkmoney: from the javadoc of TreeMap: "Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals[...]" so you need to show you comparator that we can decide if it is. — piet.t, Mar 12 '15 at 08:40
@bkmoney TreeMap does not use equals or hashcode - it uses the Comparator you give it... So that's where the problem is. — assylias, Mar 12 '15 at 08:40

score 6 · Accepted Answer · edited May 23 '17 at 11:56

6

A comparator always needs to return consistent results, and when used in a TreeMap, be consistent with equals.

In this case your comparator violates the first constraint since it does not necessarily give consistent results.

Example: If for instance otherMap maps

"a" -> "someString"
"b" -> "someString"

then both compare("a", "b") and compare("b", "a") will return -1.

Note that if you change the implementation to

if (s1.equals(s2)) {
    return 0;
}
return otherMap.get(s1).compareTo(otherMap.get(s2));

you break the other criteria of being consistent with equals, since otherMap.get(s1).compareTo(otherMap.get(s2)) might return 0 even though s1 does not equal s2.

I've elaborated on this in a self-answered follow up question here.

From the comments:

Even if a comparator gives inconsistent results, shouldn't the Java language still not allow duplicate keys?

No, when you insert a key, the TreeMap will use the comparator to search the data structure to see if the key already exists. If the comparator gives inconsistent results, the TreeMap might look in the wrong place and conclude that the key does not exist, leading to undefined behavior.

edited May 23 '17 at 11:56

Community

1
1

answered Mar 12 '15 at 08:35

aioobe

413,195
112
811
826

Updated my answer a couple of seconds before your comment. – aioobe Mar 12 '15 at 08:37
One more possibility: the comparator is not consistent with equals(). there are really tons of things that can go wrong, and it is impossible to know without more code. – amit Mar 12 '15 at 08:37
"Mutable keys can lead to undefined behaviour". This may not be the solution for OP's problem, but is definitely something to be taken into account when using `Map` and deserves a +1 – antonio Mar 12 '15 at 08:40
The keys are of type String so they are immutable correct? Even if a comparator gives inconsistent results, shouldn't the Java language still not allow duplicate keys? – bkmoney Mar 12 '15 at 08:42
@bkmoney No. It has specific example in java docs if the Comparator is inconsistent with equals(): – amit Mar 12 '15 at 08:43
`Caution should be exercised when using a comparator capable of imposing an ordering inconsistent with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an explicit comparator c is used with elements (or keys) drawn from a set S. If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave "strangely." In particular the sorted set (or sorted map) will violate the general contract for set (or map), which is defined in terms of equals.` – amit Mar 12 '15 at 08:43
ok I posted the code and I'm pretty sure that this is "consistent with equals()" because it returns 0 if the two strings equal each other – bkmoney Mar 12 '15 at 08:51
@bkmoney as pointed out, your code may return the same result for comparing `b` to `a` and `a` to `b` and it isn't `0`, this means that the comparator imposes an inconsistent ordering. This case is explicitly covered in the documentation. TL;DR if you think you have found a bug in Java, you have a misunderstanding of the JDK. – Boris the Spider Mar 12 '15 at 08:57
@bkmoney, you're right. It is consistent with equals. But it has another problem. Answer updated. – aioobe Mar 12 '15 at 08:58
I changed it to `if (s1.equals(s2)) { return 0; } return otherMap.get(s1).compareTo(otherMap.get(s2))` This still doesn't work even though it seems to be consistent? – bkmoney Mar 12 '15 at 09:01
@bkmoney this seems to be an XY problem. Why don't you explain what you actually want to do, and we will see if there is a solution using a `TreeMap` or some other `Map`. The main issue with your current approach is that if your `otherMap` changes then your `TreeMap` becomes completely broken... – Boris the Spider Mar 12 '15 at 09:05
@BoristheSpider, this should have been a comment on the question, not on the answer. – aioobe Mar 12 '15 at 09:07
@BoristheSpider I've fixed my problem by using a different data structure (ArrayList) but I just posted this because I was curious why it didn't work. I think what you said is correct, since otherMap changed, this comparator becomes completely broken and there's no good way to write it. – bkmoney Mar 12 '15 at 09:14
@bkmoney, I posted a self-answered follow up question [here](http://stackoverflow.com/questions/29005998/how-to-create-a-treemap-with-a-comparator-based-on-external-values/29005999) with a working implementation. – aioobe Mar 12 '15 at 09:31

Java TreeMap Duplicate Keys

1 Answers1

Linked