Sorted Dictionary sorted on value in C# (LRU cache)

Question

I want to implement an LRU cache , where least recently used elements will be evicted asynchronously . My current idea is to use a Dictionary to store the <key,value> pairs , and to keep track of the times of accesses of the objects, to keep a SortedDictionary <key, timestamp>. The idea is for the async thread to get the LRU items from the SortedDictionary and remove from the cache . But for this to work, SortedDictionary needs to sort by value, which it does not.

I could have used a separate SortedList instead of the SortedDictionary for keeping the {key and timestamp} sorted on the timestamp , but then I'll have to do a "linear" lookup for finding the key from the list (when I have to UPDATE the timestamp, when the same key is accessed again) - I am looking for a better than linear way if possible. Can someone share ideas to deal with this problem?

So, my problem boils down to this:

I've to lookup keys in <= logn time for UPDATING the timestamp while at the same time able to get the keys sorted based on the timestamp .

One way thought of was to keep a SortedDictionary of <{key,timestamp},null> which orders the keys based on the timestamp part of {key,timestamp} . While this is fine , the problem is hashcode() will just have to return key.hashcode() (for lookup while updating timestamp) , while equals() should also use timestamp . So , equals() and hashcode() are in conflict , so felt that this is not a good idea ...

Answer 1

What you should do is keep two dictionaries, one sorted by time and one by keys.

Remember that dictionaries are only holding references to your actual objects, so which dictionary you use to update the object doesn't matter.

To update the object create a function that will update both the dictionaries

var oldObj = keyedObject[key];
timedObjects.Remove(oldObj.LastUpdateTime);
timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject);
keyedObject[key] = myUpdatedObject;

Now you have track of the same object by both time and key.

I am keeping only one reference to an object in timedObjects. This helps while removing.

You can keep trimming your timedObjects dictionary as required.

Ofcource, while trimming you must bear in mind that there is another dictionary keyedObject that has reference to the same object. Merely calling Remove will not be enough.

Your remove code will have to be like this:

removeObject = timedObjects[timeToRemove];
timedObjects.Remove(timeToRemove);
keyedObject.Remove(removeObject.key);

timeToRemove will mostly come from a for loop, where you decide which object to remove