具有通用循环双向链表 C# 的 LRU 缓存

Question

我刚开始使用泛型，并尝试在 C# 中使用泛型循环双向链表实现 LRU 缓存。我有几个问题。请帮帮我

1) 在我的 LRUCache 构造函数中正在这样做

    head = new Node<T>(default(T), default(T));

这是不对的，我想用一些默认键值对（-1，-1）数据而不是类型默认值来初始化我的头。

2) 在我的 get 中，我根据密钥和 returning default(T) 检查节点是否为空。但我想 return null 本身。

这是我的代码

 public class Node<T>
{
    public KeyValuePair<T, T> KeyValue { get; set; }
    public Node<T> Next { get; set; }
    public Node<T> Previous { get; set; }
    public Node(T key, T value)
    {
        this.KeyValue = new KeyValuePair<T, T>(key, value);
        Next = null;
        Previous = null;
    }
}
public class LRUCache<T>
{
    private readonly int capacity;
    private int count;
    private readonly Node<T> head;
    private readonly Dictionary<T, Node<T>> myDictionary;
    public LRUCache(int capacity)
    {
        head = new Node<T>(default(T), default(T));
        head.Next = head;
        head.Previous = head;
        this.capacity = capacity;
        myDictionary = new Dictionary<T, Node<T>>();
    }
 public void set(T key, T value)
  {
   Node<T> node;
        myDictionary.TryGetValue(key, out node);
        if (node == null)
        {
            if (this.count == this.capacity)
            {
                // remove the last element
                myDictionary.Remove(head.Previous.KeyValue.Key);
                head.Previous = head.Previous.Previous;
                head.Previous.Next = head;
                count--;
            }
            // create new node and add to dictionary
            var newNode = new Node<T>(key, value);
            myDictionary[key] = newNode;
            this.InsertAfterTheHead(newNode);
            // increase count
            count++;
        }
        else
        {
            node.KeyValue = new KeyValuePair<T, T>(key, value);
            this.MoveToFirstElementAfterHead(node);
        }
  }
 public T get(T key)
 {
        Node<T> node;
        myDictionary.TryGetValue(key, out node);
        if (node == null)
        {
            return default(T);

        }
        this.MoveItToFirstElementAfterHead(node);
        return node.KeyValue.Value;
 }
}

Answer 1

假设节点中包含的值是 classes，其中包含用作键的属性，试试这个：

public abstract class Node<TNode, TNodeSupport, TKey, TValue>
    where TNode : Node<TNode, TNodeSupport, TKey, TValue>
    where TNodeSupport : Node<TNode, TNodeSupport, TKey, TValue>.BaseNodeSupport, new()
    where TValue : class
{
    protected static readonly TNodeSupport Support = new TNodeSupport();

    public KeyValuePair<TKey, TValue> KeyValue { get; set; }
    public TNode Next { get; set; }
    public TNode Previous { get; set; }
    protected Node(TValue value)
    {
        this.KeyValue = new KeyValuePair<TKey, TValue>(Support.GetKeyFromValue(value), value);
        Next = null;
        Previous = null;
    }

    public class LRUCache
    {
        private readonly int capacity;
        private int count;
        private readonly TNode head;
        private readonly Dictionary<TKey, TNode> myDictionary;
        public LRUCache(int capacity)
        {
            head = Support.CreateHeadNode();
            head.Next = head;
            head.Previous = head;
            this.capacity = capacity;
            myDictionary = new Dictionary<TKey, TNode>();
        }
        public void set(TValue value)
        {
           TKey key = Support.GetKeyFromValue(value);
           TNode node;
           myDictionary.TryGetValue(key, out node);
           if (node == null)
           {
              if (this.count == this.capacity)
              {
                    // remove the last element
                   myDictionary.Remove(head.Previous.KeyValue.Key);
                   head.Previous = head.Previous.Previous;
                   head.Previous.Next = head;
                   count--;
               }
               // create new node and add to dictionary
               var newNode = Support.CreateNodeFromValue(value);
               myDictionary[key] = newNode;
               this.InsertAfterTheHead(newNode);
               // increase count
               count++;
           }
           else
           {
               node.KeyValue = new KeyValuePair<TKey, TValue>(key, value);
                this.MoveToFirstElementAfterHead(node);
           }
        }
        public TValue get(TKey key)
        {
            TNode node;
            myDictionary.TryGetValue(key, out node);
            if (node == null)
            {
                return null;

            }
            this.MoveItToFirstElementAfterHead(node);
            return node.KeyValue.Value;
        }
    }

    public abstract class BaseNodeSupport
    {
        public abstract TKey GetKeyFromValue(TValue value);
        public abstract TNode CreateNodeFromValue(TValue value);
        public abstract TNode CreateHeadNode();
    }

}

像这样定义您的节点和项目：

public class Item
{
    public Guid Id;
    public String Data;
}
public class ItemNode : Node<ItemNode, ItemNode.Support, Guid, Item>
{
    public class NodeSupport : BaseNodeSupport
    {
        public override Guid GetKeyFromValue(Item value) { return value.Id; }
        public override ItemNode CreateNodeFromValue(Item value) {return new ItemNode(value)
        public override ItemNode CreateHeadNode() { return new ItemNode(new Item(){Id = Guid.Empty, Data = String.Empty}); }
    }
    public ItemNode(Item item) : base(item) {}
}

这样使用：

public class Program
{
    static void Main()
    {
        var cache = new ItemNode.LRUCache(100);
    }
}

在此解决方案中，Node 是一个 class 和一个 generic/parametric 命名空间，用于保存来自第三方库或本地定义的项目。

TNodeSupport class 用作单例，提供在整个 Node 命名空间中使用的三个支持函数。第一个函数接受一个项目和 returns 来自该项目的键。第二个函数从项目创建 TNode。第三个函数使用默认的空项创建默认头节点。

LRUCache 包含在 Node 泛型命名空间中，因此它可以访问运行所需的泛型类型参数。 LRUCache 逻辑实现与作者的原始实现基本相同。

在定义subclassed Node的例子中，ItemNode是一个参数化的subclass/subnamespace。 ItemNode 为 TNode 参数指定自身，ItemNode.NodeSupport 为 TNodeSupport 参数，Guid 为 TKey 参数和 Item 为 TValue 参数。

项目 class 是人为设计的 class 包含一些数据以及将用作项目键的 ID。

Item.NodeSupport class 派生自 Node.BaseNodeSupport class 并覆盖三个支持函数。在 GetKeyFromValue 方法中，它 returns 提供了 Item 实例的 Id 属性。在 CreateNodeFromValue 方法中，它 returns 使用提供的 Item 实例构造的 ItemNode。在 CreateHeadNode 方法中，它 returns 一个新的 ItemNode 使用一个新的 Item 构造，其中包含一个 Guid.Empty 作为 Id 和一个 String.Empty 作为数据。

在程序 class 中，我们实例化一个 ItemNode.LRUCache 以包含包含 Items 的 ItemNode 实例。

具有通用循环双向链表 C# 的 LRU 缓存

LRU cache with Generic Circular doubly linked list C#

c#

generics

doubly-linked-list