c# - 这个算法实现是LRU还是MRU？

Question

我正在使用 C# 在我的项目中实现 MRU(最近使用)缓存。

我在谷歌上搜索了一些关于 MRU 及其相反的 LRU(最近最少使用)的概念和实现，并找到了这篇文章 http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626描述了C#中MRU集合的实现。

让我困惑的是，我认为这个实现是 LRU 而不是 MRU。谁能帮我确认一下这个集合类是不是MRU？

以下代码块是整个 MRUCollection 类。谢谢。

class MruDictionary<TKey, TValue>
{
    private LinkedList<MruItem> items;
    private Dictionary<TKey, LinkedListNode<MruItem>> itemIndex;
    private int maxCapacity;
    public MruDictionary(int cap)
    {
        maxCapacity = cap;
        items = new LinkedList<MruItem>();
        itemIndex = new Dictionary<TKey, LinkedListNode<MruItem>>(maxCapacity);
    }
    public void Add(TKey key, TValue value)
    {
        if (itemIndex.ContainsKey(key))
        {
            throw new ArgumentException("An item with the same key already exists.");
        }
        if (itemIndex.Count == maxCapacity)
        {
            LinkedListNode<MruItem> node = items.Last;
            items.RemoveLast(); //Why do we move the last than first here? The node accessed recently is moved to the front of list.
            itemIndex.Remove(node.Value.Key);
        }
        LinkedListNode<MruItem> newNode = new LinkedListNode<MruItem>(new MruItem(key, value));
        items.AddFirst(newNode);
        itemIndex.Add(key, newNode);
    }
    public bool TryGetValue(TKey key, out TValue value)
    {
        LinkedListNode<MruItem> node;
        if (itemIndex.TryGetValue(key, out node))
        {
            value = node.Value.Value;
            items.Remove(node);
            items.AddFirst(node);
            return true;
        }
        value = default(TValue);
        return false;
    }
}

class MruItem
{
    private TKey _key;
    private TValue _value;
    public MruItem(TKey k, TValue v)
    {
        _key = key;
        _value = v;
    }
    public TKey Key
    {
        get { return _key; }
    }
    public TValue Value
    {
        get { return _value; }
    }
}

---

http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used
最近使用 (MRU):与 LRU 不同，首先丢弃最近使用的项目。

根据我的理解，由于最近访问的节点被移动到列表的前面，如果缓存已满，我们应该删除列表的第一个节点而不是最后一个。

Answer 1

在我看来它就像一个 MRU 实现。请注意搜索是如何从链表的开头开始并返回的，每当访问一个节点时，它就会移到链表的前面。在 Add() 中，使用 AddFirst() 添加节点，在 TryGetValue() 中，删除节点并将其添加到列表的前面。