CODEWITHSUNDEEP
javadata-structureshashmap
user2088834
user2088834

Reputation: 31

HashMap with date ranges

I need to find some values very fast based on a multi-key. The key is composed by: < Int userId, String measureName, Date startDate, Date endDate > and the value is a double.

The problem is that I have to ask for the value indicating a day, and not a date range. So if I'll ask for a userId, a measureName and a day, the data structure has to answer with the value where the day is between startDate and endDate (there are no overlap between date ranges).

I cannot understand which is the better data structure to implement this. HashMap? TreeMap? MultiKeyMap? RangeMap? Help! :)

Upvotes: 3

Views: 4725

Answers (4)

Arne Burmeister
Arne Burmeister

Reputation: 20604

What about a combination of Map and ordered List? The map has a compound key of userId and measureName, the value is a sorted list of date range and double value:

Map<Key,List<Entry>> data = new HashMap<>();
List<Entry> entries = data.get(new Key(userId, measureName));
int i = Collections.binarySearch(entries, new Entry(searchDate,searchDate, 0.0));
double value = i < 0 ? 0.0 : entries.get(i).value;

Key has to implement hashCode() and equals() using its members userId and measureName. Entry has to implement Comparable<Entry> where compareTo() has to return 0 if one range is part of the other (startDate comparison is <= 0 and endDate comparison is >= 0 or 0 if startDate comparison is >= 0 and endDate comparison is <= 0) else compare startDate+(endDate-startDate)/2 (middle of the range) regardless of the double value.

If you mostly read and not modify this structure, it should be fast. The comparison will be compiled to native if used much. If the function works on a single user and measure only, you can use the sorted list only, if only on a single user, you may create a Map<UserId<Map<MeasureName,List<Entry>>>> like structure instead.

Try a simple solution first, measure before and after, do performance optimizations only if needed.

Upvotes: 0

Ingo
Ingo

Reputation: 36349

I recommend some Map for the User/Measurement partial key. The value would be a sorted array of tuples (date range, floatval). In this array you perform binary search for a date range that contains the day.

Upvotes: 0

kkonrad
kkonrad

Reputation: 1262

I think you should use TreeMap and methods like: http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#floorEntry(K) http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#higherEntry(K) but use in comparison function only one date - startDate or endDate. As those ranges don't overlap this shouldn't be a problem and make mentioned methods from TreeMap usable.

For example: if you decide to use in comparison endDate (and other fields except other dates) than you should use method floorEntry

Upvotes: 3

CodeBlind
CodeBlind

Reputation: 4569

TreeMap with a custom key object would be best. You'd have something like:

...
TreeMap<MyMultiKey,Double> map = ...

class MyMultiKey implements Comparable<MyMultiKey>{
...
}

Assuming MyMultiKey's compareTo method was implemented to order your multi-keys properly, you could create a new MyMultiKey instance each time you wanted to search for a specific day by using map.floorKey(MyMultiKey m) and map.higherKey(MyMultiKey m) to make sure you found a key with a start and end time that contained the day you specified in your new key instance.

Upvotes: 0

Related Questions