Search for messages from a specific key to a specific key when deleting obsolete keys

Question

My problem

Let's say I want to save my messages in some kind of data structure for an application with a lot of commands:

1. "dude" 2. "where" 3. "is" 4. "my" 5. "car" 

A message request from index [4,5] should return: "my","car" .

Then suppose that after a while I want to clear old messages, because they are no longer useful, and I want to save memory. Say, after time x messages [1-3] became obsolete. I suggest that it would be most effective to just do the deletion once every x seconds. Then my data structure should contain:

 4. "my" 5. "car" 

My decision?

I thought of using a concurrentskiplistset or concurrentskiplist card. I also thought about deleting old messages from inside newSingleThreadScheduledExecutor . I would like to know how you could implement (efficiently / thread safe) this or maybe use a library?

Answer 1

A big concern, as I understand it, is how to allow some elements to expire after a certain period. I had a similar requirement, and I created a message class that implemented the Delayed Interface . This class contained everything I needed for a message, and (via the Delayed interface) told me when it expired.

I used instances of this object in a parallel collection, you could use ConcurrentMap as it will allow you to use these objects with an integer key.

I collected the collection once so often, removing the elements whose delay passed. We test for expiration using the getDelay method of the Delayed interface:

 message.getDelay(TimeUnit.MILLISECONDS); 

I used a regular thread that will sleep for a period and then reaps expired items. It was not important in my requirements that the items be deleted as soon as their delay has expired. It seems like you have the same flexibility.

If you needed to remove items as soon as their delay expired, instead of having a hibernate set period in your harvest stream, you would sleep for delaying the message that will expire first.

Here is my delayed message class:

 class DelayedMessage implements Delayed { long endOfDelay; Date requestTime; String message; public DelayedMessage(String m, int delay) { requestTime = new Date(); endOfDelay = System.currentTimeMillis() + delay; this.message = m; } public long getDelay(TimeUnit unit) { long delay = unit.convert( endOfDelay - System.currentTimeMillis(), TimeUnit.MILLISECONDS); return delay; } public int compareTo(Delayed o) { DelayedMessage that = (DelayedMessage) o; if (this.endOfDelay < that.endOfDelay) { return -1; } if (this.endOfDelay > that.endOfDelay) { return 1; } return this.requestTime.compareTo(that.requestTime); } @Override public String toString() { return message; } } 

Answer 2

I'm not sure if this is what you want, but it looks like I need NavigableMap<K,V> .

 import java.util.*; public class NaviMap { public static void main(String[] args) { NavigableMap<Integer,String> nmap = new TreeMap<Integer,String>(); nmap.put(1, "dude"); nmap.put(2, "where"); nmap.put(3, "is"); nmap.put(4, "my"); nmap.put(5, "car"); System.out.println(nmap); // prints "{1=dude, 2=where, 3=is, 4=my, 5=car}" System.out.println(nmap.subMap(4, true, 5, true).values()); // prints "[my, car]" ^inclusive^ nmap.subMap(1, true, 3, true).clear(); System.out.println(nmap); // prints "{4=my, 5=car}" // wrap into synchronized SortedMap SortedMap<Integer,String> ssmap =Collections.synchronizedSortedMap(nmap); System.out.println(ssmap.subMap(4, 5)); // prints "{4=my}" ^exclusive upper bound! System.out.println(ssmap.subMap(4, 5+1)); // prints "{4=my, 5=car}" ^ugly but "works" } } 

Now , unfortunately, there is no easy way to get a synchronized version of NavigableMap<K,V> , but SortedMap has subMap , but only one overload, where the upper bound is strictly exclusive.

API Links

• SortedMap.subMap
• NavigableMap.subMap
• Collections.synchronizedSortedMap