【lintcode】LRU缓存策略

古城微笑少年丶 2022-06-01 03:08 139阅读 0赞

为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据（get）和写入数据（set）。
    
    获取数据get(key)：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。
    写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。

![这里写图片描述][SouthEast]  
思路：  
使用如上图所示的双链表与hash表结合的数据结构来缓存信息。  
**哈希表**中存放key值与指向双链表节点的指针，故可以通过key值快速查找对应的链表节点。  
**双链表**中缓存数据，每命中一个数据或新增一个数据，就将其移动或添加到链表头部，这样可以保证链表尾部的节点就是最近最少用的数据，当缓存已满时若添加新数据即可将尾部节点从链表中删除。  
**使用双链表的目的**是：对于链表中的任意一个节点，我们都能够方便地找到它的前驱。

代码

struct Node{
        int key;
        int value;
        Node *pre;
        Node *next;
        Node(int _key, int _value){key = _key; value = _value, pre = next = NULL;};
    };
    class LRUCache {
        int size;
        int capacity;
        Node *head;
        Node *tail;
        unordered_map<int, Node*> hash;
    public:
        /*
        * @param capacity: An integer
        */
        LRUCache(int capacity) {
            // do intialization if necessary
            this->capacity = capacity;
            size = 0;
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head->next = tail;
            head->pre = NULL;
            tail->next = NULL;
            tail->pre = head;
        }
    
        /*
         * @param key: An integer
         * @return: An integer
         */
        int get(int key) {
            // write your code here
            Node *p;
            if(hash.find(key) == hash.end())
                return -1;
            else{
                p = hash[key];
                //从原位置删除p
                p->next->pre = p->pre;
                p->pre->next = p->next;
                //将p加到链表头部
                p->next = head->next;
                p->pre = head;
                head->next = p;
                p->next->pre = p;
    
                return p->value;
            }
        }
    
        /*
         * @param key: An integer
         * @param value: An integer
         * @return: nothing
         */
        void set(int key, int value) {
            // write your code here
            Node *p;
            if(hash.find(key) != hash.end()){
                p = hash[key];
                p->value = value;
                //从原位置删除p
                p->next->pre = p->pre;
                p->pre->next = p->next;
                //将p加到链表头部
                p->next = head->next;
                p->pre = head;
                head->next = p;
                p->next->pre = p;
            }
            else{
                p = new Node(key, value);
                //将p加到链表头部
                p->next = head->next;
                p->pre = head;
                head->next = p;
                p->next->pre = p;
                //加入hash表
                hash[key] = p;
                size++;
            }
    
            if(size > capacity){
                    p = tail->pre;
                    //从hash表中删除对应项
                    hash.erase(hash.find(p->key));
                    //删除尾部节点p
                    p->next->pre = p->pre;
                    p->pre->next = p->next;
                    delete p;
                    size--;
            }
        }
    };

[SouthEast]: /images/20220601/495a6541cfd643c79840eecfc576b527.png