Java TreeMap contains a key but a containsKey call returns false (even the key is exactly the same unchanged object)

Question

Why is it possible to loop the keySet of a TreeMap and getting a .containsKey == false?

for (Object thisObject : map.keySet()) {
    if (!map.containsKey(thisObject)) {
        System.out.println("This line should be never reached.");
    }
}

After a lot, lot of different iterations and calls this line gets hit. A map.get(thisObject) would return null. But debug shows that the key (same reference, value and hash) and an actual value is in the map. The map is a small (25 elements) TreeMap<Long, Double>

UPDATE:

As guessed by @rgettman theres a custom sort Comparator used at the construction of the TreeMap (Didn't see it because it was constructed from another class). This comparator was just (I guess) copy pasted from here

Changing the Comparator:

  public int compare(Object a, Object b) {

    if((Double)base.get(a) > (Double)base.get(b)) {
      return 1;
    } else if((Double)base.get(a) == (Double)base.get(b)) {
      return 0;
    } else {
      return -1;
    }
  }

to

...
    } else if(base.get(a).equals(base.get(b))) {
      return 0;
...

fixes the problem. The reason why this problem was showing up just after millions of operation was that there were no cases where the map had two similar values for two different keys, as this is very unlikely in the context.

So at:

25151l, 1.7583805400614032
24827l, 1.7583805400614032

it fails.

Thanks for your help!

@RameshK I mean, the OP already confirmed that it's the same ref, so there shouldn't be an issue with `==`, should there? — Dennis Meng, Aug 07 '13 at 17:22
As a sanity check; is this in a single-threaded application? — Dennis Meng, Aug 07 '13 at 17:26
Since it is small can you please add an [SSCCE](http://sscce.org/) with all keys-values so we can run it? — c.s., Aug 07 '13 at 17:30
You definitely need to show the contents of the map to make this answerable. — arshajii, Aug 07 '13 at 17:40
One way to get this to fail is to provide a `Comparator` to the `TreeMap` constructor that breaks the `Comparator` contract, i.e. doesn't return `0` for equal values. — rgettman, Aug 07 '13 at 17:49

score 1 · Answer 1 · answered Aug 07 '13 at 17:47

1

You must have made changes to the backing entrySet()/Map.Entry thereby changing the key orders, thereby having a failed search containsKey.

answered Aug 07 '13 at 17:47

Joop Eggen

107,315
7
83
138

JNL · Answer 2 · 2013-08-07T17:47:08.100

0

I just executed the code, this case did return true to me.

          TreeMap<Long,Double> otm = new TreeMap<Long, Double>();
          otm.put(1L, 1.0);
          otm.put(2L, 2.0);

        for (Object thisObject : otm.keySet()) {
                System.out.println(otm.containsKey(thisObject));
        }

Can you please give us the data that you input in the TreeMap. Thanks

This is the containKey(Object key) implementation from JavaDocs

containsKey

boolean containsKey(Object key)

Returns true if this map contains a mapping for the specified key.

More formally, returns true if and only if this map contains a mapping for a key k such that, (key==null ? k==null : key.equals(k)). (There can be at most one such mapping.)

Parameters:

key - key whose presence in this map is to be tested Returns:
true if this map contains a mapping for the specified key Throws:
ClassCastException - if the key is of an inappropriate type for this map (optional)
NullPointerException - if the specified key is null and this map does not permit null keys (optional

Hope that helps.

edited Aug 07 '13 at 17:47

answered Aug 07 '13 at 17:31

JNL

4,683
18
29

1

What if the problem lies in the specific pair that the OP added that isn't in your example? The point is that the OP *knows* that it should return true, but wants to know why his particular case isn't. Trying out some other random case doesn't answer the question at all. – Dennis Meng Aug 07 '13 at 17:33
@DennisMeng I am curious to learn about such specific pair. My point was OP might have not implemented it correctly. Thats why I wanted to see the specific case. Have you come across such cases? If yes, I would appreciate if you could let me know about the same. – JNL Aug 07 '13 at 17:36
I guess, but there's a difference between "are sure you didn't make x mistake" and "i tried this other case and it worked fine for me" – Dennis Meng Aug 07 '13 at 17:38
Sure but it does after millions of calls return false here. Will try to provide an SSCCE ... – F___ThisToxicCommunityHere Aug 07 '13 at 17:39
That would be awesome. Because if the hashcode is the same in the debugger, I am curious to know about the same too. – JNL Aug 07 '13 at 17:40

score 0 · Answer 3 · answered Aug 08 '13 at 06:16

0

Most of these implementation classes rely on both hashCode() and equals() being supported and correct.

If you truly have same hashcode from objects, try match equality. The answer suggested by me is that they do not match.

Otherwise, the scenario ought to be small enough for you to publish the objects and/or their respective hashcode and equals method.

answered Aug 08 '13 at 06:16

Niels Bech Nielsen

4,777
1
21
44

The hashcode of a Long is based on it's value `public int hashCode() { return (int)(value ^ (value >>> 32)); }` – F___ThisToxicCommunityHere Aug 08 '13 at 09:44

Java TreeMap contains a key but a containsKey call returns false (even the key is exactly the same unchanged object)

3 Answers3