CODEWITHSUNDEEP
javadata-structuresdictionary
Skyzer
Skyzer

Reputation: 592

search previous closest date/string in (hash)map

I've run into a problem where I need to probably redesign my data-structure.

Right now I have lots of info in chronological order and keeping it in Hashmap with key being the date that is also a member of new Info().

hashMap.put(date.toString(), new Info(date, ...))

dates are with 5 minutes interval

2012-02-15 22:45:00.0
2012-02-15 22:50:00.0
2012-02-15 22:55:00.0
2012-02-15 23:00:00.0
...
2012-02-25 12:10:00.0
2012-02-25 12:15:00.0

So far it was easy to get info by getting the key and the speed is constant time
hashMap.get(date.toString())

So far so good when i'm getting the date from hashmap that is there. But now there could be gaps in info chronological order. In the example below there is missing 2012-02-15 22:50:00.0 so when searching for that date i'd get NPE.
In that case I must find the previous closest time.

2012-02-15 22:45:00.0
2012-02-15 22:55:00.0
2012-02-15 23:00:00.0 ...

if (hashMap.get(date.toString()) != null) {
   // found it
} else {
   return previousTime(date.toString())
}

I could make a LinkedHashMap and previousTime could just iterate over the collection until i find the closest previous date. But the worst case would be O(n) complexity. Could there be a better data structure for that kind of task or just use LinkedHashMap? A SortedMap like here? But the initial put would be costly and it will take more memory.

Upvotes: 0

Views: 618

Answers (2)

LeleDumbo
LeleDumbo

Reputation: 9340

But the worst case would be O(n) complexity

How big would this n be? I don't think it's a problem even if it's a million. More than that might be a problem though, but before you worry about speed I guess you'll run out of memory first. Simply do backward iteration of each 5 minutes from the point where the asked date isn't found.

Upvotes: 0

ColinD
ColinD

Reputation: 110054

It sounds to me like a NavigableMap such as TreeMap is exactly what you're looking for. Though you really shouldn't be using the String form of a date as your keys... use the Date itself.

Upvotes: 5

Related Questions