LRU缓存机制

发表于 | 分类于 | 阅读次数：
本文字数： 3.1k | 阅读时长 ≈ 8 分钟

题目

#146 LRU Cache

运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制。它应该支持以下操作：获取数据get和写入数据put。

获取数据get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

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

示例：
LRUCache cache(2);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解题思路

本题的难点在如何在O(1)的时间内完成get和put操作。

先考虑get操作。我们很容易能想到使用map，它能够在O(1)时间内完成get操作（严格的说是O(log n)，使用unsorted_map可以达到O(1)的时间复杂度）。但是单纯使用map会使得put的时间复杂度大大增加。

为了使得put操作能在O(1)内完成，便可以使用双向链表，每当插入一个新元素或访问其中某个元素时，将其移到链表头。这样链表尾便是“最近最少使用”的元素。但如果单纯使用双向链表，又无法满足get操作的时间复杂度要求。

因此，我采用了map+双向链表的方法。map以key为键，以(value, 链表节点)为值，可以迅速的找到某个元素，同时维护的链表可以在O(1)的时间内找出被替换的元素。

值得说明的优化点

  1. 使用unsorted_map而不是map，可以加快查找速率。在内部实现上，unsorted_map是哈希表，map是红黑树。在诸如此类不需要有序的情况下应该优先考虑unsorted_map
  2. 使用循环列表和dummy node可以大大简化代码，不需要维护链表尾的指针，也可以少讨论很多NULL的情况。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class LRUCache {
private:
    int capacity;
    int size;

    typedef struct Node {
        int key;
        int value;
        Node *prev;
        Node *next;

        Node(int k, int v): key(k), value(v), prev(NULL), next(NULL) {}
    } Node;

    Node *head;

    typedef struct Value {
        int value;
        Node *node;

        Value(int v, Node *p): value(v), node(p) {}
        Value() {}

    } tValue;

    unordered_map<int, tValue> data;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        size = 0;

        head = new Node(0, 0);
        head->prev = head;
        head->next = head;
    }
    
    int get(int key) {
        if (data.find(key) != data.end()) {
            Node *targetNode = data[key].node;
            targetNode->prev->next = targetNode->next;
            targetNode->next->prev = targetNode->prev;
            targetNode->next = head->next;
            targetNode->prev = head;
            head->next = targetNode;
            targetNode->next->prev = targetNode;
            return data[key].value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (data.find(key) != data.end()) {
            data[key].value = value;
            data[key].node->value = value;
            get(key);
            return;
        }

        Node *newNode = new Node(key, value);
        if (size == capacity) {
            Node *tail = head->prev;
            head->prev = tail->prev;
            tail->prev->next = head;
            data.erase(tail->key);
            delete tail;
            size--;
        }
        newNode->next = head->next;
        newNode->prev = head;
        head->next->prev = newNode;
        head->next = newNode;
        tValue tv(value, newNode);
        data[key] = tv;
        size++;
    }
};