LRU缓存实现-创新互联

LRU(Least Recently Used)最近最少使用算法，通过淘汰最久为使用的缓存使缓存容量满足一致性
(1) LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
(2) int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
(3)void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
(4)函数 get 和 put 必须以 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)使用双向链表，从虚拟头节点插入时，尾节点就是最久未使用的节点，头节点就是最新插入的节点。由于双向链表的特性，删除链表中的节点的时间复杂度是O(1)。
(2)构建一个key-value结构，可以记录put()方法插入的键值，以及对应的节点地址，从而方便找到双向链表中的对应节点，此hash表结构为key(键)-value(值，对应节点地址)
(3)对于get(key)方法，需要满足获取到get(key)的值后，将双向链表的对应节点删除，并且重新从虚拟头节点后加入，然后维护hash表结构，记录key(键)-value(值，对应节点地址)
(4)对于put(key,value)方法，需要分类讨论
1)容量未满时，key值已经存在时，删除双向链表中对应节点，从虚拟头节点后再次加入，然后维 护hash表结构
key值不存在(新的key，value)，创建新的节点，直接从双向链表中的虚拟头节点后加入，维护hash表结构
2）容量已满，key值已经存在时，删除双向链表中对应节点，从虚拟头节点后再次加入，然后维 护hash表结构
key值不存在(新的key，value)，需要将双向链表尾节点删除，维护hash表中的信息(删除过期系欸但信息)，然后创建新节点，直接从双向链表中的虚拟头节点后加入，维护hash表结构(增加新节点信息)

class LRUCache {private:
    struct Node{//双向链表的节点信息
        int key = -1;
        int val = -1;
        Node* pre = NULL;
        Node* next = NULL;
    };

    struct element{// hash表中的元素信息
        int val = -1;
        Node* addr = NULL;
    };

    Node* VirtualNode;// 链表的虚拟头节点
    Node* tailNode; // 链表的尾节点

    int size = 0;// 记录链表长度
    int capacity;// 容量
    
    unordered_mapmp; // hash表
    
public:
    LRUCache(int capacity) {
        this->capacity = capacity; // 初始化容量
        this->VirtualNode = new Node(); // 初始化虚拟头节点
        this->tailNode = this->VirtualNode;
    }

    void addLinkedList(Node* node){//从头插入节点
        if(VirtualNode->next == NULL){VirtualNode->next = node;
            node->pre = VirtualNode;
        }else{Node* temp = VirtualNode->next;
            node->next = temp;
            node->pre = VirtualNode;

            VirtualNode->next = node;
            temp->pre = node;

        }
   
        // 维护尾指针，第一次插入的节点为尾指针
        if(size == 0){tailNode = node;
        }
        size++;   
    }

    void removeLinkedList(Node* node){//删除某个节点，使用双向链表可以找到该节点的前一个和后一个节点

        Node* preNode = node->pre;
        Node* nextNode = node->next;

        // 需要删除的节点是尾节点
        if(node == tailNode){preNode->next = NULL;
            tailNode = preNode;// 维护尾节点
        }else{preNode->next = nextNode;
            nextNode->pre = preNode;
        }
        size--;
    }
    
    int get(int key) {// 没有节点或需要查询的节点已经过期
        if( size == 0 || mp[key].val == -1){return -1;
        } 
        else{// 如果节点过期，需要将hash表中的val值置为-1，此时链表中已经不存在该节点，无法完成删除操作
            // 更新链表，使得尾节点是最近最少使用的节点，头节点是最近使用过的节点
            // 删除mp[key].addr节点，并且从头插入此节点
            removeLinkedList(mp[key].addr);
            addLinkedList(mp[key].addr);
            return mp[key].val;
        }
    }
    
    void put(int key, int value) {
        // 链表长度小于capacity
        if(this->size< this->capacity){// 如果key值存在过了
            if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
                removeLinkedList(mp[key].addr);
                addLinkedList(mp[key].addr);
                // 维护hash表，更新val
                mp[key].val = value;
            }else{//key值之前未添加过，添加新的key值
                // 创建新节点
                Node* node =  new Node;
                node->key = key;
                node->val = value;
                //向链表中添加新节点node
                addLinkedList(node);
                //维护hash表
                mp[key].val = value; 
                mp[key].addr = node;
            }  
        }else{//链表长度超过容量

            // 如果之前key值存在过了，不产生新节点
            if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
                removeLinkedList(mp[key].addr);
                addLinkedList(mp[key].addr);
                //维护hash表
                mp[key].val = value; 

            }else{// 如果之前key值不存在，产生新节点

                // 维护hash表,节点过期
                mp[tailNode->key].val = -1;
                
                // 删除链表尾部节点（最近最少使用）
                removeLinkedList(tailNode);

                // 创建新节点
                Node* node = new Node;
                node->key = key;
                node->val = value;
                
                // 添加新节点
                addLinkedList(node);

                // 维护hash表
                mp[key].val = value; 
                mp[key].addr = node;

            }
        }
    }
};

可见在向LinkedList中加入元素后，都需要维护hash表，所以代码可以调整，并且使用stl中的list结构代替自己编写的双向链表，从而减少代码量

class LRUCache {private:
    struct element{// hash表中的元素信息
        int val = -1;
        list::iterator addr;
    };

    listLinkedList;//使用双向链表
    // int size = 0;// 记录链表长度，由于list.size()函数的时间复杂度是O(N),可以通过维护一个size()值减少此处的时间消耗
    int capacity;// 容量
    unordered_mapmp; // hash表
    
public:
    LRUCache(int capacity) {this->capacity = capacity; // 初始化容量
    }
    
    int get(int key) {// 没有节点或需要查询的节点已经过期
        if( LinkedList.size() == 0 || mp[key].val == -1){return -1;
        } 
        else{// 如果节点过期，需要将hash表中的val值置为-1，此时链表中已经不存在该节点，无法完成删除操作
            // 更新链表，使得尾节点是最近最少使用的节点，头节点是最近使用过的节点
            // 删除mp[key].addr节点，并且从头插入此节点
            LinkedList.erase(mp[key].addr);
            LinkedList.push_front(key);
            mp[key].addr = LinkedList.begin();
            return mp[key].val;
        }
    }
    
    void put(int key, int value) {// 链表长度小于capacity
        if(LinkedList.size()< this->capacity){// 如果key值存在过了
            if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
                LinkedList.erase(mp[key].addr);
                LinkedList.push_front(key);
            }else{//key值之前未添加过，添加新的key值
                //向链表中添加新节点node
                LinkedList.push_front(key);
            } 

        }else{//链表长度超过容量
            // 如果之前key值存在过了，不产生新节点
            if(mp[key].val != -1){// 将链表中的mp[key].addr节点删除，重新添加
                LinkedList.erase(mp[key].addr);
                LinkedList.push_front(key);
            }else{// 如果之前key值不存在，产生新节点
                // 维护hash表,节点过期
                mp[LinkedList.back()].val = -1;
                // 删除链表尾部节点（最近最少使用）
                LinkedList.pop_back();
                // 添加新节点
                LinkedList.push_front(key);
            }
        }
        // 维护hash表，更新val
        mp[key].val = value;
        mp[key].addr = LinkedList.begin();
    }
};

注：list结构的list.size()方法的时间复杂度为O(n)，因为其内部调用了distance()方法计算了所有元素的个数，因此可以使用size变量得到双向链表得长度

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧