Key in TreeMap returning null

Dennis Sullivan picture Dennis Sullivan · Feb 24, 2012 · Viewed 8.4k times · Source

So I have a very odd bug. I stumbled across it when I was originally using a keySet() to iterate over the first 10 keys of a large TreeMap. One of the keys was returning null, which should not be possible as far as my understanding goes. So I wrote the test code below:

int i = 0;
        for (Map.Entry<String, Integer> es : sortedMap.entrySet()){
            if (i >= 10) {
                break;
            }

            if (sortedMap.containsKey(es.getKey())){
                System.out.println(es.getKey() + ":" + sortedMap.get(es.getKey()));
            } else {
                System.out.println("Key " + es.getKey() + " does not exist, yet...");
                System.out.println("This does work: " + es.getKey() + ":" + es.getValue());
                System.out.println("This does NOT work: " + es.getKey() + ":" + sortedMap.get(es.getKey()));
            }
            i++;
        }

And get the following results:

SOAP:967
'excerpt'::679
'type'::679
Key 'author_url': does not exist, yet...
This does work: 'author_url'::679
This does NOT work: 'author_url'::null
'date'::679
Android:437
TLS:295
message:283
server:230
monthly:215
<<<<<<<<<<<<<<<<<<<<DUMPING MAP!
{SOAP=967, 'excerpt':=679, 'type':=679, 'author_url':=679, 'date':=679, Android=437, TLS=295, message=283, server=230, monthly=215...

I cut off the map after the top ten as there is a lot more in there, but all of it is a key with a value.

So my question is this: Why am I getting a null when using the key to directly get(key) from the TreeMap, but the EntrySet returns the correct key and value?

Here is my comparator since I am ordering on Integer:

class ValueComparator implements Comparator<Object> {

  Map<String, Integer> base;
  public ValueComparator(Map<String, Integer> base) {
      this.base = base;
  }

  public int compare(Object a, Object b) {

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

And the TreeMap is built as following:

ValueComparator bvc =  new ValueComparator(allMatches);
TreeMap<String, Integer> sortedMap = new TreeMap<String, Integer>(bvc);
//Sort the HashMap
sortedMap.putAll(allMatches);

Where allMatches is a HashMap<String, Integer>

Answer

amit picture amit · Feb 24, 2012

From the order of iteration your TreeMap shows, it is definetly the case that you used a custom Comparator. [Otherwise the iteration would have been in lexicographical order]

Note that according to the javadocs:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementer must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

If your Comparator does not apply these rules - the behavior is not defined, as might show strange results - as you see.

EDIT: [as response to the editted question]
Your compartor uses identity [operator==] to check two Integers.
Note that Integer is an object - and thus operator== will return true only if it is the same object.
You should use equals() to check if two integers are identical - or even better - use Integer.compareTo()