前面，我们学习了 链表 的实现，今天我们来学习链表的一个经典的应用场景 ——LRU 淘汰算法。

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used），本篇将介绍 LRU 策略算法。

LRU Cache

这一算法的核心思想是，当缓存数据达到预设的上限后，会优先淘汰掉近期最少使用的缓存对象。

思路

LRU 淘汰算法涉及数据的添加与删除，出于性能考虑，采用链表来进行实现，思路如下：

  • 维护一个双向链表用于存放缓存数据，越接近链表尾部的数据表示越少被使用到。
  • 放入一个数据时，如果数据已存在则将其移动到链表头部，并更新 Key 所对应的 Value 值，如果不存在，则：
    • 如果缓存容量已达到最大值，则将链表尾部节点删除掉，将新的数据放入链表头部；
    • 如果缓存容量未达到最大值，则直接将新的数据放入链表头部；
  • 查询一个数据时，遍历整个链表，如果能查询到对应的数据，则将其移动到链表头部；如果查询不到则返回 null；
    • 由于遍历链表的时间复杂度为 O(n)，我们可以使用散列表 HashMap 来记录每个 Key 所对应的 Node 节点，将时间复杂度降为 O (1)。

LRU-Cache

代码

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
package one.wangwei.algorithms.utils;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU Cache
 *
 * @author https://wangwei.one
 * @date 2019/01/29
 */
public class LRUCache<K, V> {

    private int capacity;
    private Node head;
    private Node tail;
    private Map<K, Node> nodeMap;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.nodeMap = new HashMap<>(capacity);
    }

    /**
     * Get Key
     *
     * @param key
     * @return
     */
    public V get(K key) {
        Node existNode = nodeMap.get(key);
        if (existNode == null) {
            return null;
        }
        remove(existNode);
        addFirst(existNode);
        return existNode.value;
    }

    /**
     * Add Key-Value
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        Node existNode = nodeMap.get(key);
        if (existNode == null) {
            Node newNode = new Node(key, value);
            if (nodeMap.size() >= capacity) {
                removeLast();
            }
            addFirst(newNode);
        }
        else {
            // update the value
            existNode.value = value;
            remove(existNode);
            addFirst(existNode);
        }
    }

    /**
     * remove node
     *
     * @param node
     */
    private void remove(Node node) {
        Node prev = node.prev;
        Node next = node.next;

        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
        }
        nodeMap.remove(node.key);
    }

    /**
     * add first node
     *
     * @param node
     */
    private void addFirst(Node node) {
        // don't forget set node prev pointer to null !
        node.prev = null;
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        nodeMap.put(node.key, node);
    }

    /**
     * remove last
     */
    private void removeLast() {
        if (tail == null) {
            return;
        }
        // remove key from map
        nodeMap.remove(tail.key);
        // remove node from linked list
        Node prev = tail.prev;
        if (prev != null) {
            prev.next = null;
            tail = prev;
        } else {
            head = tail = null;
        }
    }

    private class Node {

        private K key;
        private V value;
        private Node prev;
        private Node next;

        private Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

源码

LeetCode 上相关的练习题：Leetcode 146. LRU Cache

性能测试：LeetCode 上运行时间为 88ms，超过了 43.42% 的 Java 代码。

相关练习

参考资料