Java Map between pairs and values

Question

I need to create a map which will cache results of a third party lookup service. The request is made up of two objects for example, time and month. The map needs to map between (time, month) and a result.

My initial idea is to make an object to wrap time and month into effectively a tuple object, so the cache is a map between this object and the result.

Is there a better way of doing this, without needing to wrap the request into the tuple object each time we need to use the cache?

Many thanks.

Answer 1

Excellent question!

First of all, the answer of @dasblinkenlight is correct, let's say, most of the time. Constructing a single object key is the most straight forward and obvious solution. It is easy and clear to understand and quite efficient. If this cache is not the hotspot of your application, no second thought needed.

However, there are alternatives, which may yield better efficiency.

Conceptually there are two possibilities:

• Construct a single key object for the compound keys. That's a common pattern and quite typical if you use compound keys for database access
• Do a two, or multi level hierarchical lookup, e.g.: store.get(month).get(time)

For the hierarchical lookup, no additional object allocation is needed, however, you trade it in for a second hash table access. To be most memory efficient, it is important to put the key with the smallest value space first.

If this is a very central place of your application, the even better approach is to put the first lookup stage, the twelve months, in an array and initialize it on startup:

Cache<Time, Value>[] month2ValueCache = new Cache<Time, Value>[12];
{
  for (int i = 0; i < 12; i++) {
    month2ValueCache[i] = new Cache<Time, Value>(...);
  }
}
Value get(int month, Time, time) {
  return month2ValueCache[month].get(time);
}

I did a comparison benchmark for formatting dates with the DateFromatter. This seams similar to your use case. This has actually three key components: date, format and locale. You can find it here: https://github.com/headissue/cache2k-benchmark/blob/master/zoo/src/test/java/org/cache2k/benchmark/DateFormattingBenchmark.java

My result was, that there is actually not much runtime difference between allocating an object for the compound keys, or the three level cache lookup without object allocation for the key. However, the used benchmark framework does not take into account the garbage collection correctly. I will do a more thorough evaluation after I switched to another benchmark framework.

Answer 2

If you don't want to use an Map of Maps (not very nice, but it works) you still have some choices... for example storing month and time in a String, using something like DateFormat ds = new SimpleDateFormat(MM HH:mm:s), then using to convert a Calendar Object filled with your values

Calendar cal = Calendar.getInstance();
cal.set(Calendar.MONTH, yourmonth);
cal.set(Calendar.HOUR_OF_DAY, yourhours);
cal.set(Calendar.MINUTE, yourminutes);
cal.set(Calendar.SECOND, yoursecs);
String val_to_store=ds.format(cal.getTime());

Or, maybe, you could store the calendar object.

Answer 3

You can create a map of maps:

Map<MonthType, Map<TimeType, Value>> map;

so you'd call:

Value value = map.get(month).get(time);

to retrieve a value (provided you have previously added a value for month).

It's not particularly nice to use directly, however, since you'd need lots of containsKey/null checks. You could wrap it up into a convenience class:

class MapOfMaps {
  final Map<MonthType, Map<TimeType, Value>> map = new HashMap<>();

  void put(MonthType month, TimeType time, Value value) {
    Map<TimeType, Value> timeMap;
    if (map.containsKey(month)) {
      timeMap = map.get(month);
    } else { 
      timeMap = new HashMap<>();
      map.put(month, timeMap);
    }
    timeMap.put(time, value);
  }

  Value get(MonthType month, TimeType time) {
    if (!map.containsKey(month)) {
      return null;
    }
    return map.get(month).get(time);
  }
}

Answer 4

I'll do it this way too, but be careful when defining a Key of an HashMap: it should be immutable, since otherwise changing it could compromise the mapping and hashing, and should implement the two requirements of hash key: hashCode and equals methods. Something like this:

final class YourWrapper {
    private final Integer month;
    private final Integer time;

    public YourWrapper(Integer month, Integer time) {
        this.month = month;
        this.time = time;
    }

    public Integer getMonth() {
        return month;
    }

    public Integer getTime() {
        return time;
    }

    @Override
    public int hashCode() {
        return month.hashCode() ^ time.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof YourWrapper) 
                && ((YourWrapper) obj).month.equals(month)
                && ((YourWrapper) obj).time.equals(time);
    }
}

Answer 5

My initial idea is to make an object to wrap time and month into effectively a tuple object

That's the right idea. Override hashCode() and equals(Object) of your tuple to make it work with HashMap<TimeMonthTuple>, or compareTo(TimeMonthTuple) to make it work with TreeMap<TimeMonthTuple>

Is there a better way of doing this?

This is the most straightforward way, unless you have a class that can replace TimeMonthTuple with something that makes sense. For example, time and date could be combined into a Date object.

In certain cases you could make a key based on a primitive wrapper. For example, if time is expressed as the number of minutes since midnight and month is a number between 1 and 12, inclusive, you could wrap both values into an Integer, and use it as a key:

Integer makeTimeMonthKey(int time, int month) {
    return (time * 12) + (month - 1);
}

Answer 6

You should take a look at Guava Tables if you want to avoid creating a wrapper object.