Is it there any LRU implementation of IDictionary?

Question

I would like to implement a simple in-memory LRU cache system and I was thinking about a solution based on an IDictionary implementation which could handle an hashed LRU mechanism. Coming from java, I have experiences with LinkedHashMap, which works fine for what I need: I can't find anywhere a similar solution for .NET.

Has anyone developed it or has anyone had experiences like this?

Answer 1

This a very simple and fast implementation we developed for a web site we own.

We tried to improve the code as much as possible, while keeping it thread safe. I think the code is very simple and clear, but if you need some explanation or a guide related to how to use it, don't hesitate to ask.

namespace LRUCache {     public class LRUCache<K,V>     {         private int capacity;         private Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>> cacheMap = new Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>>();         private LinkedList<LRUCacheItem<K, V>> lruList = new LinkedList<LRUCacheItem<K, V>>();          public LRUCache(int capacity)         {             this.capacity = capacity;         }          [MethodImpl(MethodImplOptions.Synchronized)]         public V get(K key)         {             LinkedListNode<LRUCacheItem<K, V>> node;             if (cacheMap.TryGetValue(key, out node))             {                 V value = node.Value.value;                 lruList.Remove(node);                 lruList.AddLast(node);                 return value;             }             return default(V);         }          [MethodImpl(MethodImplOptions.Synchronized)]         public void add(K key, V val)         {             if (cacheMap.TryGetValue(key, out var existingNode))             {                 lruList.Remove(existingNode);             }             else if (cacheMap.Count >= capacity)             {                 RemoveFirst();             }              LRUCacheItem<K, V> cacheItem = new LRUCacheItem<K, V>(key, val);             LinkedListNode<LRUCacheItem<K, V>> node = new LinkedListNode<LRUCacheItem<K, V>>(cacheItem);             lruList.AddLast(node);             // cacheMap.Add(key, node); - here's bug if try to add already existing value             cacheMap[key] = node;         }          private void RemoveFirst()         {             // Remove from LRUPriority             LinkedListNode<LRUCacheItem<K,V>> node = lruList.First;             lruList.RemoveFirst();              // Remove from cache             cacheMap.Remove(node.Value.key);         }     }      class LRUCacheItem<K,V>     {         public LRUCacheItem(K k, V v)         {             key = k;             value = v;         }         public K key;         public V value;     } }