LRU缓存与通用循环双链表c#

本文关键字：链表 循环 缓存 LRU | 更新日期: 2023-09-27 18:05:51

我是使用泛型的新手，并试图在c#中使用泛型循环双链表实现LRU缓存。我有几个问题。请帮帮我吧

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

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

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

2)在我的get中，我根据键检查节点是否为空并返回默认值(T)。但我想返回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;
 }
}

LRU缓存与通用循环双链表c#

假设节点中包含的值是包含用作键的属性的类，请尝试如下操作:

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是一个类和一个泛型/参数命名空间，它保存来自第三方库或本地定义的项。

TNodeSupport类被用作单例，它提供了贯穿Node命名空间的三个支持函数。第一个函数接受一个项并返回该项的键。第二个函数从一个项目创建一个TNode。第三个函数创建带有默认空项的默认头节点。

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

在定义子类化的Node的示例中，ItemNode是一个参数化的子类/子名称空间。ItemNode为TNode参数ItemNode指定自己。TNodeSupport参数为NodeSupport, TKey参数为Guid, TValue参数为Item。

Item类是一个人造的类，它包含一些数据以及一个Id，该Id将用作该项的键。

项目。NodeSupport类派生自Node。BaseNodeSupport类并覆盖三个支持函数。在GetKeyFromValue方法中，它返回所提供的Item实例的Id属性。在CreateNodeFromValue方法中，它返回一个用提供的Item实例构造的ItemNode。在CreateHeadNode方法中，它返回一个由包含Guid的新Item构造的新ItemNode。Id和String为空。数据为空

在Program类中，我们实例化了一个ItemNode。
相关文章：