Java TreeMap returns null for key when value exists

Question

I've created a TreeMap like this:

   Map<Date, List<MyInput>> inputsByDate = new TreeMap<>(new Comparator<Date>() {
        @Override
        public int compare(Date lhs, Date rhs) {
            return dateUtil.compareDay(lhs, rhs);
        }


    });

My method in the comparator is not pretty but at least identifies similarity(I'm not using HashMap with equals and hash due to other reasons):

public int compareDay(Date lhs, Date rhs) {
    Calendar cal1 = Calendar.getInstance();
    Calendar cal2 = Calendar.getInstance();
    cal1.setTime(lhs);
    cal2.setTime(rhs);
    boolean sameDay = cal1.get(Calendar.YEAR) == cal2.get(Calendar.YEAR) &&
            cal1.get(Calendar.DAY_OF_YEAR) == cal2.get(Calendar.DAY_OF_YEAR);
    if (sameDay) {
        return 0;
    } else {
        return -1;
    }
}

Anyway, the problem is the snippet below. The last element is null when I retrieve it.

public List<MyType> convert(Map<Date, List<MyInput>> inputByDate, Map<Date, Boolean> isDoneByDate) {
        List<MyType> result = Lists.newArrayList();
        for (Date dateKey : inputByDate.keySet()) {
            boolean isDone = false;
            Boolean res = isDoneByDate.get(dateKey);
            if (res != null) {
                isDone = res;
            }
            List<MyInput> inputs = inputByDate.get(dateKey);

            MyType retrieved=new MyType(dateKey, inputs, isDone);
            result.add(retrieved);
        }
        return result;
    }

When I run the last snippet with the debugger I can clearly see that there are (as an example) 3 keys with values that are not null. I must be missing something here because I cannot see how reports can be null if I have validated that each key is matched with a valid pair before. Any help would be greatly appreciated.

Answer 1

If the dates are different your comparator should return -1 or 1 since it has to be symmetric, i.e. if you return -1 when comparing date1 and date2 you have to return 1 when comparing date2 and date1. Your code is bound to break the map since it can't reliably determine an order for the keys.

So refactor your compare() to something like this:

int result = Integer.compare( cal1.get(Calendar.YEAR), cal2.get(Calendar.YEAR));
if( result == 0 ) { //if the year is equal compare the days
  result = Integer.compare( cal1.get(Calendar.DAY_OF_YEAR), cal2.get(Calendar.DAY_OF_YEAR));
}
return result;

Edit: A small breakdown on what probably happened with your comparator.

If you have a look at the sources you'll see that the map will compare the new key with the already existing keys. Your comparator would thus order them according to insert order, i.e. since you always return -1 for non-equal keys the map will always follow the left branch and thus the last added element will be the "smallest". That's just another problem though.

The problem you're facing is to be found in the getEntryUsingComparator() method which is called indirectly by get(key). The method looks like this:

Comparator<? super K> cpr = comparator;
if (cpr != null) {
  Entry<K,V> p = root;
  while (p != null) {
    int cmp = cpr.compare(k, p.key);
    if (cmp < 0)
      p = p.left;
    else if (cmp > 0)
      p = p.right;
    else
      return p;
  }
}
return null;

As you can see due to always returning -1 the method would always execute the cmp < 0 branch until p = p.left results in p = null because there is no more left element and then the while loop is terminated and you end up at return null;.