0

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.

Community
  • 1
  • 1
Skyzer
  • 584
  • 3
  • 11
  • 27

2 Answers2

5

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.

ColinD
  • 108,630
  • 30
  • 201
  • 202
0

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.

LeleDumbo
  • 9,192
  • 4
  • 24
  • 38
  • n would be up to 100k. `Simply do backward iteration of each 5 minutes from the point where the asked date isn't found.` but how can i get in hashmap to the point where the asked date is not found? the key/values are hashed and they are not in precise order – Skyzer Mar 04 '12 at 15:50
  • yes, but you know that they're in 5 minutes range. just loop while `get` returns null. – LeleDumbo Mar 05 '12 at 02:09