I need data structure for effective handling with dates

Question

What I need is something like Hashtable which I will fill with prices that were actual at desired days.

For example: I will put two prices: January 1st: 100USD, March 5th: 89USD.

If I search my hashtable for price: hashtable.get(February 14th) I need it to give me back actual price which was entered at Jan. 1st because this is the last actual price. Normal hashtable implementation won't give me back anything, since there is nothing put on that dat.

I need to see if there is such implementation which can find quickly object based on range of dates.

Answer 1

Off the top of my head, there are a couple ways, but I would use a TreeMap<Date> (or Calendar, etc).

When you need to pull out a Date date, try the following:

1. Attempt to get(date)
2. If the result is null, then the result is in headMap(date).lastKey()

One of those will work. Of course, check the size of headMap(date) first because lastKey() will throw an Exception if it is empty.

Answer 2

You could use a DatePrice object that contains both and keep those in a list or array sorte by date, then use binary search (available in the Collections and Arrays classes) to find the nearest date.

This would be significantly more memory-effective than using TreeMap, and it doesn't look like you'll want to insert or remove data randomly (which would lead to bad performance with a array).

Answer 3

Create a Tree Map with Date,String. If some one calls for a date then convert the string to date and call map.get(date), if you find then take the previous key than the current element.

Answer 4

You have all your tools already at hand. Consider a TreeMap. Then you can create a headmap, that contains only the portion of the map that is strictly lower that a given value. Implementation example:

TreeMap<Date,Double> values = new TreeMap<Date,Double>();
...fill in stuff...
Date searchDate = ...anydate...
// Needed due to the strictly less contraint:
Date mapContraintDate = new Date(searchDate.getTime()+1); 
Double searchedValue = values.get(values.headMap(mapContraintData).lastKey);

This is efficient, because the headMap is not create by copying the original map, but returns only a view.