1

This is a follow-up question from my previous question.

I'm trying to implement a NavigableMap defined as NavigableMap<Timestamp, Event>. I would need this map to be like a cache for me. Every 5 minutes I refresh this NavigableMap.

One thread updates this NavigableMap, and another one reads from it, so it needs to be thread-safe. Whenever I have a request, I would need to grab a subset list of Events whose timestamps are within a given start and end time.

What is the most efficient way to convert a NavigableMap to this subset list, say ArrayList? And what's the thread-safe implementation of this interface?

Apparently NavigableMap has a sub-map method as well as floor and ceiling, but I don't see anything to convert to a list with a start and end time.

Tina J
  • 4,983
  • 13
  • 59
  • 125

1 Answers1

2

To extract a key-range from the NavigableMap, call subMap(K fromKey, K toKey) or subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive).

If you just want the values, as a list, do this:

List<Event> list = new ArrayList<>(map.subMap(start, end).values());

what's the thread-safe implementation of this interface?

According to the javadoc: ConcurrentSkipListMap

Andreas
  • 154,647
  • 11
  • 152
  • 247
  • 1
    `subMap` is just a *view* of the underlying map, so its time complexity is just `O(1)`. Fetching its first element would be `O(logN)`, though. Then, it's just a traversal. So, copying the submap to i.e. an `ArrayList` would be `O(logN + M)`, with `N` being the total number of entries in the map and `M` the number of elements within the given range. Be careful with `ConcurrentSkipListMap`, as bulk operations require external synchronization, and especially because its `size()` method has `O(N)` time complexity. @TinaJ – fps Jan 24 '19 at 02:01
  • Thanks. Is there any difference if I use `ConcurrentSkipListMap` or `synchronized{treeMap}`?! – Tina J Jan 24 '19 at 02:49
  • Yes. `synchronized{treeMap}` does not synchronize iterations, so you have to do that yourself, i.e. during the `new ArrayList<>(submap)` call, and `synchronized` is likely slower than `ConcurrentSkipListMap` – Andreas Jan 24 '19 at 05:03