Key in TreeMap returning null

Question

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 1

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()

Answer 2

Your biggest problem is that your use of == instead of .equals in your value comparator is breaking things, because different keys are getting mapped to different Integer objects with the same intValue(), which is throwing off even more things unpredictably.

But if you fixed that, then your TreeMap wouldn't let you insert multiple keys with the same value, which is almost certainly also causing subtle breakages.

A better solution would be something like this, but basically, you should fill in a map without sorting by values, sort the entrySet, and then copy the entries (in order) to a map like LinkedHashMap that doesn't need a comparator, but just keeps entries in the order of insertion.

You might be able to change your comparator so that if the values are the same, it'll compare the keys as well. This would at least let you insert multiple keys with the same value...but it's still a really hacky solution that's much riskier than a LinkedHashMap-based solution as described above.

Answer 3

Problem solved:

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)).intValue() < ((Integer) base.get(b)).intValue()) {
        return 1;
    } else if ( ((Integer) base.get(a)).intValue() == ((Integer) base.get(b)).intValue()) {
        return ((String)a).compareTo(((String)b));
    } else {
        return -1;
    }
}
}

This comes with the additional benefit of bringing back keys with the same value in alphabetical order.

Answer 4

You should simply have:

class ValueComparator implements Comparator<Integer> {


  public int compare(Integer a, Integer b) {
      return a.compareTo(b);
  }
}

Next you need to initialize your treemap with the comparator and add all your items:

Treemap