LRU算法C#实现

为了查询速度快，需要使用字典，为了方便淘汰数据，需要使用链表。

链表根据value来remove时间复杂度是O(n)，根据node来remove时间复杂度是O(1)，所以要记录node。

node节点无论包含key还是value都不合适，所以自定义实体，包含key和value

public class LRUEntity<K, V>
{
    public K LRUKey { get; set; }
    public V LRUValue { get; set; }
}

链表存放该实体，字典存放对应node

private LinkedList<LRUEntity<K, V>> _linkedList;
private Dictionary<K, LinkedListNode<LRUEntity<K, V>>> _dictionary;

存数据，包含了新增和更新操作。

新增操作需要注意是否超过容量，删除链表尾巴数据，这里没有真正删除节点，而是把节点重复利用了。

更新操作修改了对应缓存，并移至链表头部

public void Add(K key, V value)
{
    if (_dictionary.ContainsKey(key))
    {
        LinkedListNode<LRUEntity<K, V>> node = _dictionary[key];
        _linkedList.Remove(node);//O(1)
        _linkedList.AddFirst(node);

        node.Value.LRUValue = value;
    }
    else
    {
        LinkedListNode<LRUEntity<K, V>> newNode = null;

        if (_linkedList.Count >= _capacity)
        {
            newNode = _linkedList.Last;//无需创建新对象
            _linkedList.RemoveLast();
            _dictionary.Remove(newNode.Value.LRUKey);
        }
        else
        {
            newNode = new LinkedListNode<LRUEntity<K, V>>(new LRUEntity<K, V>());
        }

        newNode.Value.LRUKey = key;
        newNode.Value.LRUValue = value;
        _linkedList.AddFirst(newNode);
        _dictionary.Add(key, newNode);
    }
}

取数据，需要将对应缓存移至链表头部。

public V Get(K key)
{
    if (_dictionary.ContainsKey(key))
    {
        LinkedListNode<LRUEntity<K, V>> node = _dictionary[key];
        _linkedList.Remove(node);//O(1)
        _linkedList.AddFirst(node);

        return node.Value.LRUValue;
    }

    return default(V);
}