LRU算法

前言

简单的刷了刷题， LRU在计算机中使用的还是比较多，于是自己写了一个玩玩。

参考：路径

思路

• 哈希表和双向链表的结合
• 存在MoveToFirst
• 不存在AddToFirst

遇到的坑

在C#中使用结构体会有陷阱 （用Class不会造成如此问题）
值拷贝惹的祸 （脏数据问题）
造成链表形成环 （环的判别）

扩展

判断链表环算法 、 LFU算法

---

C#代码

using System;
using System.Collections.Generic;

class NewLRU
{
    struct Node
    {
        public int key;
        public int value;
        public int preKey;
        public int backKey;
        public Node(int a,int b,int c,int d)
        {
            key = a;
            value = b;
            preKey = c;
            backKey = d;
        }
    }

    public NewLRU()
    {
        capacity = 2;
        Init();
    }

    public NewLRU(int cap)
    {
        capacity = cap;
        Init();
    }

    private int capacity;
    private Dictionary<int,Node> keyMapNode;

    private int firstKey;
    private int lastKey;

    private void Init()
    {
        firstKey = -1;
        lastKey = -1;
        keyMapNode = new Dictionary<int,Node>();
    }

    //加入
    public void Put(int key,int value)
    {
        Node curNode;
        if(keyMapNode.TryGetValue(key, out curNode))
        {
            curNode.value = value;
            MoveToFirst(curNode);
        }
        else
        {
            curNode = new Node(key, value, -1, -1);
            AddToFirst(curNode);
        }
    }

    //访问
    public int Get(int key)
    {
        Node curNode;
        if(keyMapNode.TryGetValue(key,out curNode))
        {
            MoveToFirst(curNode);
            return curNode.value;
        }
        return -1;
    }

    private void MoveToFirst(Node curNode)
    {
        if(curNode.key != firstKey)
        {
            if(curNode.key == lastKey)
            {
                Node newLastNode = keyMapNode[curNode.preKey];
                newLastNode.backKey = curNode.backKey;
                lastKey = newLastNode.key;
                keyMapNode[newLastNode.key] = newLastNode;
            }
            else
            {
                Node preNode = keyMapNode[curNode.preKey];
                Node backNode = keyMapNode[curNode.backKey];
                preNode.backKey = backNode.key;
                backNode.preKey = preNode.key;
                keyMapNode[preNode.key] = preNode;
                keyMapNode[backNode.key] = backNode;
            }
            Node firstNode = keyMapNode[firstKey];
            curNode.preKey = firstNode.preKey;
            firstNode.preKey = curNode.key;
            curNode.backKey = firstNode.key;
            firstKey = curNode.key;
            keyMapNode[firstNode.key] = firstNode;
            keyMapNode[curNode.key] = curNode;
        }
    }

    private void AddToFirst(Node curNode)
    {
        if(firstKey!=-1)
        {
            if(keyMapNode.Count>=capacity)
            {
                Node lastNode = keyMapNode[lastKey];
                keyMapNode.Remove(lastKey);
                Node newLastNode = keyMapNode[lastNode.preKey];
                newLastNode.backKey = lastNode.backKey;
                lastKey = newLastNode.key;
            }
            Node firstNode = keyMapNode[firstKey];
            curNode.preKey = firstNode.preKey;
            firstNode.preKey = curNode.key;
            curNode.backKey = firstNode.key;
            keyMapNode[firstNode.key] = firstNode;
        }
        else
        {
            lastKey = curNode.key;
        }
        firstKey = curNode.key;
        keyMapNode.Add(curNode.key,curNode);
    }

}

C++代码

Python代码