在 C# 当中实现 LRU Cache

在常用的缓存设计模式当中,LRU是比较简单且常见的一种缓存设计方案,简单说来就是在缓存队列当中,使用频率越低的对象,越会被踢出队列。
原理的话很简单,我们有一个字典容器,还有一个双向链表。
字典容器则是我们缓存对象真正存储的地方,双向链表的作用则是用来记录当前缓存队列的使用频率情况,当用户命中一个缓存对象的时候,双向链表就回将这个对象的键ID放在最前面,这样就能够保证使用率最低的对象是存放在最末位。如果当我们添加了一个新的缓存对象的时候,但是字典容器满了,这个时候我们只需要找到双向链表当中最末位的那个缓存对象将其踢出队列,之后再将新的缓存对象存放到字典容器当中。

说了这么多,还是上代码吧:

public class LRUCache<TKey,TValue>
{
    private Dictionary<TKey,TValue> m_cache;
    private LinkedList<TKey> m_list;
    private ReaderWriterLockSlim m_locker;

    private int m_cacheSize;
    private const int Default_Size = 255;
    
    public LRUCache() : this(Default_Size){}
    public LRUCache(int cacheSize)
    {
        m_cache = new Dictionary<TKey,TValue>();
        m_list = new LinkedList<TKey>();
        m_locker = new ReaderWriterLockSlim();
        m_cacheSize = cacheSize > 0 ? cacheSize : Default_Size;
    }

    public void Set(TKey key,TValue value)
    {
        m_locker.EnterWriteLock();
        try
        {
            m_cache[Key] = value;
            m_list.Remove(key);
            m_list.AddFirst(key);
            
            if(m_list.Count > m_cacheSize)
            {
                m_cache.Remove(m_list.Last.Value);
                m_list.RemoveLast();
            }
        }finally
        {
            m_locker.ExitWriteLock();
        }
    }
    
    public bool TryGetValue(TKey key,out TValue value)
    {
        m_locker.EnterUpgradeableReadLock();
        try
        {
            bool _b = m_cache.TryGetValue(key,out value);
            if(_b)
            {
                m_locker.EnterWriteLock();
                try
                {
                    m_list.Remove(key);
                    m_list.AddFirst(key);
                }finally{ m_locker.ExitWriteLock();}
            }
            return _b;
        }finally
        {
            m_locker.ExitUpgradeableReadLock();
        }
    }
    
    public bool ContainKey(TKey key)
    {
        m_locker.EnterReadLock();
        try
        {
            retrun m_cache.ContainKey(key);
        }finally
        {
            m_locker.ExitReadLock();
        }
    }

    public int Count
    {
        get
        {
            m_lokcer.EnterReadLock();
            try
            {
                return m_cache.Count;
            }finllay
            {
                m_locker.ExitReadLock();
            }
        }
    }

    public int CacheSize
    {
        get
        {
            m_locker.EnterReadLock();
            try
            {
                return m_cacheSize;
            }finally
            {
                m_locker.EnterReadLock();
            }
        }
        set
        {
            m_locker.EnterUpgradeableReadLock();
            try
            {
                if(value > 0 && m_cacheSize != value)
                {
                    m_locker.EnterReadLock();
                    try
                    {
                        m_cacheSize = value;
                        while(m_list.Count > m_cacheSize)
                        {
                            m_list.RemoveLast();
                        }
                    }finally
                    {
                        m_locker.ExitReadLock();
                    }
                }
            }finally{m_locker.ExitUpgradeableReadLock();}
        }
    }
    
    public ICollection<TKey> Keys
    {
        get
        {
            m_locker.EnterReadLock();
            try
            {
                return m_cache.Keys;
            }finally{m_locker.ExitReadLock();}
        }
    }

    public ICollection<TValue> Values
    {
        get
        {
            m_locker.EnterReadLock();
            try
            {
                return m_cache.Values;
            }finally{m_locker.ExitReadLock();}
        }
    }
}

关于缓存基础和更多的认识,可以参考以下文章:
http://blog.jobbole.com/30940/