LRU 缓存

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值（允许你插入和检索特定键对应的值）， 并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

思路

哈希表 + 双向链表

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
  • 哈希表即为普通的哈希映射，通过缓存数据的键映射到其在双向链表中的位置。

这样一来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或 put 操作。

  • get 操作
    • 如果 key 不存在，则返回 -1
    • 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
  • put 操作
    • key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
    • key 存在，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移动到双向链表的头部。

小贴士

在双向链表的实现中，使用伪头部和伪尾部标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
public class LRUCache<K, V> {

    private int size;
    private final int capacity;

    /**
     * 双向链表使用伪头部和伪尾部
     * 好处：添加和删除节点时不需要检查相邻节点是否存在
     */
    private final Node<K, V> head;
    private final Node<K, V> tail;
    /**
     * 哈希表
     */
    private final Map<K, Node<K, V>> CACHE;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node<>();
        tail = new Node<>();

        head.next = tail;
        tail.prev = head;
        this.CACHE = new HashMap<>(capacity);
    }

    /**
     * 如果 key 不存在，则返回 null
     * 如果 key 存在，通过哈希表定位到该节点在双向链表中的位置，
     * 并将其移动到双向链表的头部，最后返回该值
     *
     * @author   chengxudong               chengxudong@microwu.com
     * @date    2021/9/11  8:32
     *
     * @param   	k
     * @return  V
     */
    public V get(K k) {
        if (!CACHE.containsKey(k)) {
            return null;
        }
        Node<K, V> node = CACHE.get(k);
        // 先删除，后移动
        remove(node);
        moveToHead(node);
        return node.value;
    }
    
    /**
     * 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加
     * 该节点，并将 key 和该节点添加到哈希表中。然后判断双向链表的节点数是否超出
     * 容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项
     *
     * 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为
     * value，并将该节点移动到双向链表的头部
     *
     * @author   chengxudong               chengxudong@microwu.com
     * @date    2021/9/11  8:44
     *
     * @param   	k
     * @param 		v
     * @return  void
     */
    public void put(K k, V v) {
        if (CACHE.containsKey(k)) {
            // 存在
            Node<K, V> node = CACHE.get(k);
            node.value = v;
            remove(node);
            moveToHead(node);
        } else {
            // 不存在
            Node<K, V> node = new Node<>();
            node.key = k;
            node.value = v;

            moveToHead(node);
            CACHE.put(k, node);
            size++;
            if (size > capacity) {
                Node<K, V> tailNode = removeTail();
                CACHE.remove(tailNode.key);
                size--;
            }
        }
        
    }

    /**
     * remove Tail
     *
     * @author   chengxudong               chengxudong@microwu.com
     * @date    2021/9/11  8:54
     *
     * @param
     * @return  com.microwu.cxd.se.data.structure.lru.LRUCache.Node<K,V>
     */
    private Node<K,V> removeTail() {
        Node<K, V> node = tail.prev;
        node.prev.next = tail;
        tail.prev = node.prev;
        return node;
    }

    /**
     * move head
     *
     * @author   chengxudong               chengxudong@microwu.com
     * @date    2021/9/11  8:39
     *
     * @param   	node
     * @return  void
     */
    private void moveToHead(Node<K,V> node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    /**
     * remove node
     *
     * @author   chengxudong               chengxudong@microwu.com
     * @date    2021/9/11  8:35
     *
     * @param   	node
     * @return  void
     */
    private void remove(Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private static class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> prev;
        private Node<K, V> next;

    }

    public static void main(String[] args) {
        /* 缓存容量 */
        LRUCache<Integer, Integer> cache = new LRUCache( 2 );

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