Storing objects addressable by id and sorted by timestamp

I'm building an application and I need help finding a data structure to do what I want.

Background

that gets about 100 events per second. These events have 3 pieces, a String session uuid, a long timestamp (Unix time) and, possibly, a json String. The session uuid is used to tie events from the same session together. The first event we receive with a given sets the TTL for the session.

Requirements

I'm t开发者_JAVA百科rying to store these sessions which are, essentially, sorted collections of events which are sorted by their event time. The two criteria I'm having a problem simultaneously meeting are:

1. I need to be able to quickly look up a Session based on its UUID.
2. I need to be able to determine which sessions have expired based on their TTL stamp, which is an attribute of the session.

What I'm thinking of is a Map where I can key off of the UUID but the values are kept in a sorted order. I can make the EventSession objects comparable by time, but it seems like SortedMap only sorts the keys. I'm not sure if there are fundamental issues with what I'm asking for, but I'm open for ideas.

It sounds like you need two structures: a Map to look up Session objects by UUID and a PriorityQueue for storing the same Session objects ordered by TTL.

I have done the same thing. You need 2 datastructures:

• a List containing time-sessionID-pairs, keep a pointer to beginning and end so you can insert and delete in constant time.

• a Map sessionID->JSonString implemented by a red-black tree of sorted sessionIDs

The red-black tree is automatically balanced, easier to implement that AVL and will give you log(n) inserts, look-ups and deletes. So when deleting from your list you take the ID that's store there and the entry in the map in log(n) time.