题目描述

请为LRU缓存设计一个数据结构。支持两种操作：get和set。

• get(key) - 如果key在缓存中，则返回key对应的值（保证是正的）；否则返回-1；
• set(key, value) - 如果key在缓存中，则更新key对应的值；否则插入(key, value)，如果缓存已满，则先删除上次使用时间最老的key。

进一步：
能否使用两个操作都是 $O(1)$ 时间复杂度的算法？

样例

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 删除 key 2
cache.get(2);       // 返回 -1 (没找到)
cache.put(4, 4);    // 删除 key 1
cache.get(1);       // 返回 -1 (没找到)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

算法

(双链表+哈希) $O(1)$

使用两个双链表和一个哈希表：

• 第一个双链表存储未被使用的位置；
• 第二个双链表存储已被使用的位置，且按最近使用时间从左到右排好序；
• 哈希表存储key对应的链表中的节点地址；

初始化：

• 第一个双链表插入 $n$ 个节点，$n$ 是缓存大小；
• 第二个双链表和哈希表都为空；

get(key)：
首先用哈希表判断key是否存在：

• 如果key存在，则返回对应的value，同时将key对应的节点放到第二个双链表的最左侧；
• 如果key不存在，则返回-1；

set(key, value)：
首先用哈希表判断key是否存在：

• 如果key存在，则修改对应的value，同时将key对应的节点放到第二个双链表的最左侧；
• 如果key不存在：
  • 如果缓存已满，则删除第二个双链表最右侧的节点（上次使用时间最老的节点），同时更新三个数据结构；
  • 否则，插入(key, value)：从第一个双链表中随便找一个节点，修改节点权值，然后将节点从第一个双链表删除，插入第二个双链表最左侧，同时更新哈希表；

时间复杂度分析：双链表和哈希表的增删改查操作的时间复杂度都是 $O(1)$，所以get和set操作的时间复杂度也都是 $O(1)$。

C++ 代码

class LRUCache {
public:
    struct Node
    {
        int val, key;
        Node *left, *right;
        Node() : key(0), val(0), left(NULL), right(NULL) {}
    };
    Node *hu, *tu; // hu: head_used, tu: tail_used; head在左侧，tail在右侧
    Node *hr, *tr; // hr: head_remains, tr: tail_remains; head在左侧，tail在右侧
    int n;
    unordered_map<int, Node*> hash;

    void delete_node(Node *p)
    {
        p->left->right = p->right, p->right->left = p->left;
    }

    void insert_node(Node *h, Node *p)
    {
        p->right = h->right, h->right = p;
        p->left = h, p->right->left = p;
    }

    LRUCache(int capacity) {
        n = capacity;
        hu = new Node(), tu = new Node();
        hr = new Node(), tr = new Node();
        hu->right = tu, tu->left = hu;
        hr->right = tr, tr->left = hr;

        for (int i = 0; i < n; i ++ )
        {
            Node *p = new Node();
            insert_node(hr, p);
        }
    }

    int get(int key) {
        if (hash[key])
        {
            Node *p = hash[key];
            delete_node(p);
            insert_node(hu, p);
            return p->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (hash[key])
        {
            Node *p = hash[key];
            delete_node(p);
            insert_node(hu, p);
            p->val = value;
            return;
        }

        if (!n)
        {
            n ++ ;
            Node *p = tu->left;
            hash[p->key] = 0;
            delete_node(p);
            insert_node(hr, p);
        }

        n -- ;
        Node *p = hr->right;
        p->key = key, p->val = value, hash[key] = p;
        delete_node(p);
        insert_node(hu, p);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */