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

There is nothing in the base class libraries that does this.

On the free side, maybe something like C5's HashedLinkedList would work.

If you're willing to pay, maybe check out this C# toolkit. It contains an implementation.

Answer 2

I don't believe so. I've certainly seen hand-rolled ones implemented several times in various unrelated projects (which more or less confirms this. If there was one, surely at least one of the projects would have used it).

It's pretty simple to implement, and usually gets done by creating a class which contains both a Dictionary and a List.

The keys go in the list (in-order) and the items go in the dictionary.
When you Add a new item to the collection, the function checks the length of the list, pulls out the last Key (if it's too long) and then evicts the key and value from the dictionary to match. Not much more to it really

Answer 3

The Caching Application Block of EntLib has an LRU scavenging option out of the box and can be in memory. It might be a bit heavyweight for what you want tho.

Answer 4

If it's an asp.net app you can use the cache class[1] but you'll be competing for space with other cached stuff, which may be what you want or may not be.

[1] http://msdn.microsoft.com/en-us/library/system.web.caching.cache.aspx

Answer 5

Antonello, this a very simple an fast implementation we developed for a WebSite we own (its a site related to descuentos www.misdescuentos.com).

We try to improve the code as much as possible but 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.

Cheers

using System;
using System.Collections.Generic;
using System.Text;
using System.Runtime.CompilerServices;

namespace LRUCache
{
    public class LRUCache<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))
            {
                //System.Console.WriteLine("Cache HIT " + key);
                V value = node.Value.value;

                lruList.Remove(node);
                lruList.AddLast(node);
                return value;
            }
            //System.Console.WriteLine("Cache MISS " + key);
            return default(V);
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public void add(K key, V val)
        {
            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);
        }


        protected void removeFirst()
        {
            // Remove from LRUPriority
            LinkedListNode<LRUCacheItem<K,V>> node = lruList.First;
            lruList.RemoveFirst();
            // Remove from cache
            cacheMap.Remove(node.Value.key);
        }

        int capacity;
        Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>> cacheMap = new Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>>();
        LinkedList<LRUCacheItem<K, V>> lruList = new LinkedList<LRUCacheItem<K, V>>();
    }


    internal class LRUCacheItem<K,V>
    {
        public LRUCacheItem(K k, V v)
        {
            key = k;
            value = v;
        }
        public K key;
        public V value;
    }
}