LRU 算法实现

一、题目:

LeetCode 146题:

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制 。


实现 LRUCache 类,类内操作的说明:

    LRUCache(int capacity) :以正整数作为容量 capacity 初始化 LRU 缓存。
    int get(int key) : 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
    void put(int key, int value):  如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?

二、设计说明:

LRU就是 Least Recently Used,最近最少使用 的缓存淘汰机制。缓存的两个要素是 大小 和 替换策略

LRU设计实现 和 运行的机制:

1、首先初始化,整个缓存空间 ; 

 2、然后 访问某个关键字,如果存在于缓存中,需要返回关键字的值,并且将该关键字置为最新访问,否则返回 -1;

3、插入数据,如果关键字已经存在,变更其对应的数据值;如果关键字不存在,插入该组 [关键字— 值]。在插入之前,要判断数据是否 已达到最大容量。 如果达到最大容量,删除最久未使用的关键字,从而为新插入的数值腾出空间。

题目关键信息:

因为要保留节点的数据,想到使用 链表 保存数据。 那么是使用单链表还是双链表呢?

单向链表只能从头向尾部遍历,只能找到节点的后继节点,不能找到前驱节点。因为要 按时间顺序 保存数据插入和删除的时候,既需要知道前节点,又需要知道后节点,因此使用双向链表。

题目要求 O(1)时间 内完成 查询 和 插入 操作,可以使用 哈希表 来存数据的 key-value。

哈希表 + 双向链表:

双向链表:      用于按时间顺序保存数据

哈希表:        用于把key映射到链表节点

LRU 算法实现

代码实现:

//使用双向链表 + 哈希表 实现
class LRUCache {
public:
    class Node
    {
        public:
            int key;
            int val;
            Node* pre;
            Node* next;
            Node(){}
            Node(int mkey, int mvalue):key(mkey),val(mvalue),pre(NULL),next(NULL)
            { }
    };

    //构造函数
    LRUCache(int capacity) {
        this->size = capacity;

        //头尾保护节点
        head = new Node();
        tail = new Node();
        //初始化双链表关系
        head->next = tail;
        tail->pre = head;
    }

    Node* delete_currentnode(Node* current)
    {
        current->pre->next = current->next;
        current->next->pre = current->pre;
        return current;
    }

    //移动到最前面
    //相当于在链表中一个insert操作,在head 和 head的next之间插入一个节点
    void move_to_head(Node* current)
    {
        Node* next = head->next;
        head->next = current;
        current->pre = head;
        next->pre = current;
        current->next = next;
    }

    void make_recently(Node* current)
    {
        Node* temp = delete_currentnode(current);

        move_to_head(temp);
    }
    
    int get(int key) {
        int ret = -1;
        //get 到key的value,要进行将key的对值从存储结构中删除,然后重新排列前后的数据
        if(map.find(key)!= map.end())
        {
            Node* temp = map[key];
            make_recently(temp);
            ret = temp->val;
        }
        return ret;
    }
    
    void put(int key, int value) {
        if(map.find(key) != map.end())
        {
            //关键字存在,修改key,对应的值
            Node* temp = map[key];
            temp->val= value;

            //将key变为最近使用
            make_recently(temp);
        }
        else
        {
            //关键字不存在,插入,(key,value)
            Node* cur = new Node(key,value);
            if( map.size()==size )
            {
                //链表尾部就是最久未使用的key
                Node* temp = delete_currentnode(tail->pre);
                map.erase(temp->key);
            }
            move_to_head(cur);
            map[key] = cur;
        }
    }

public:
    //类内共享容量值
    int size;

    unordered_map<int, Node*> map;
    Node* head;
    Node* tail;
};

上一篇:缓存算法之LRU与LFU


下一篇:操作系统学习笔记 页面置换算法(一)