CODEWITHSUNDEEP
javahashmaptimestamp
J. Doe
J. Doe

Reputation: 81

How to use Timestamp in a Map as key

I am working on a coding challenge on a banking application where I need to fetch number of transactions in last 60 seconds. For that I am using java.sql.Timestamp as a key of a map like below:

Map<Timestamp, List<Transaction>> transactions1 = new HashMap<>();

Here value is the list of transactions done at that time. I can't use DB. I know how to iterate through the map and fetch the data but for that I need to iterate the whole map which will be time consuming.

1) My question is is Map the right data structure for this problem?

2) If so then how can I reduce it(may be by NavigableMap)?

I am not asking for coding solution but the proper design/ data structure that I should use.

Upvotes: 4

Views: 4894

Answers (2)

GhostCat
GhostCat

Reputation: 140525

A HashMap solely considers mapping (based on hash code and equality).

This means: you have to get() all keys of your map, to ensure you correctly identify those within a certain interval. No shortcuts possible, always a full O(n) scanning of all keys in your map.

Thus you are correct: any efficient strategy must allow you to search that map (in an array/random access based approach), so maps implementing the NavigableMap, such as TreeMap will be a better choice. TreeMaps are also sorted, so you could implement some way of "binary search" to identify timestamps from the last n seconds. Meaning: you need O(log n) to determine the first timestamp within the interval, and then you just keep fetching the following keys, until you reach the upper bound of the interval.

Beyond that, it could be helpful to invest in your own implementation of some sort of index. Like a list that remembers the first timestamp of 1/5/n minute intervals.

Meaning: the low hanging fruit is to simply change from HashMap to TreeMap, with clever searching for interval boundaries. But for a "real world" scenario, where you might have to deal with hundreds of thousands or millions of entries, that approach is still not sufficient. Then you would have to very carefully design a solution that optimizes on your most important requirements. But that is something that only you can do.

Upvotes: 3

Roshana Pitigala
Roshana Pitigala

Reputation: 8806

One way to increase performance is to dump the inner for loop. By adding a List<Transaction> in the HashMap you'll have to use a loop inside another loop to access the Transaction object.

Use,

HashMap<Long, Transaction> transactions = new HashMap<>();

And use Nanoseconds as the key.

System.nanoTime();

So when iterating you have the Transaction object right away. If you want to get the Timestamp,

new Timestamp(nanoseconds/1000000);

Upvotes: 1

Related Questions