实现 LRU 缓存机制

发布于 2021-03-10 10:49:15   阅读量 27  点赞 0  

 LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。

 LRU 缓存机制常借助双向链表实现,以下通过一道 LeetCode 算法题介绍一种 LRU 机制的实现。



问题描述

 原题地址:https://leetcode-cn.com/problems/lru-cache/

 实现LRUCache类:

  • LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存;

  • int get(int key)如果关键字key存在于缓存中,则返回关键字的值,否则返回 -1 。

  • void put(int key, int value)如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶
 在 O(1) 时间复杂度内完成这两种操作。

示例

输入:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出:
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示

  • 1 <= capacity <= 3000

  • 0 <= key <= 3000

  • 0 <= value <= 104

  • 最多调用 3 * 10^4getput


实现:双向链表+哈希表

 使用双向链表来保存具体的数据,每次访问数据时都会将当前数据移到链表表头,这样靠近头部的数据是最近使用的,而靠近尾部的数据是最久未使用的,每次淘汰数据都从尾部淘汰。

 使用哈希表保存双向链表节点指针,以在常数时间内访问节点以获取对应数据且操作双向链表。

其中使用双向链表而非单向链表的原因是:能够通过尾节点方向的前向指针淘汰尾部节点。

 对于具体的数据操作逻辑,有:

  • get,首先判断key是否存在:

    • 若不存在,则返回 -1;
    • 若存在,而对应节点是最近被使用的节点,通过哈希表获取到节点指针,将该节点移动到双向链表的头部,最后返回该节点的值。

  • put,首先判断key是否存在:
    • 若不存在,使用keyvalue新建节点,将该节点添加到双向链表头部与哈希表。然后判断双向链表的节点数是否超出容量,若超出,则删除双向链表的尾部节点,并删除哈希表中对应项;
    • 若存在,则覆盖对应值,并通过哈希表获取节点指针,将该节点移动到双向链表的头部。

优化
 可引入一个伪头部伪尾部标记界限,这样在操作节点时就不需要检查边界情况。


代码

struct DListNode {  // 双向链表节点
    int key, value;
    DListNode *prev, *next;
    DListNode(): key(0), value(0), prev(nullptr), next(nullptr){}
};

class LRUCache {
private:
    std::map<int, DListNode*> cache;
    DListNode* head;
    DListNode* tail;
    int size;
    int capacity;
    void move2Head(DListNode* node){    // 将当前指向的节点换到第一个
        node->prev->next = node->next;
        node->next->prev = node->prev;
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    void addNode(DListNode* node){     // 将新键的节点添加到双向链表头
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    int removeTail(){   // 移除最后一个节点,且返回 key
        DListNode* lastOne = tail->prev;
        int key = lastOne->key;

        lastOne->prev->next = tail;
        tail->prev = lastOne->prev;

        delete lastOne;
        return key;
    }
public:
    explicit LRUCache(int _capacity){
        capacity = _capacity;
        size = 0;
        head = new DListNode();
        tail = new DListNode();
        head->next = tail;
        tail->prev = head;
    }
    ~LRUCache(){
        DListNode* ptr = head;
        while(ptr){
            DListNode* tmp = ptr->next;
            delete ptr;
            ptr = tmp;
        }
    }
    void put(int key, int value){
        if(cache.find(key)==cache.end()){
            // 若不存在,新建 [关键字-值]
            DListNode* newNode = new DListNode();
            newNode->key = key;
            newNode->value = value;
            cache[key] = newNode;
            addNode(newNode);

            // 检查容量,若此时 size==capacity,则移除最后一个节点,否则递增size
            if(size==capacity){
                cache.erase(removeTail());
            }else{
                size++;
            }
        }else{
            // 若存在,覆盖原值,更新缓存
            DListNode* node = cache[key];
            node->value = value;
            move2Head(node);
        }

    }
    int get(int key){
        // 若不存在,返回 -1
        if(cache.find(key)==cache.end()){
            return -1;
        }

        // 若存在,获取双向链表节点指针,并将该节点移到第一个
        DListNode* node = cache[key];
        move2Head(node);
        return node->value;
    }
};


Last Modified : 2021-03-10 15:25:32