LRU，全称 Least Recently Used，即最近最少使用。它是一种常用的缓存淘汰算法，也常用于虚拟内存管理。

核心思想：LRU 认为“最近被使用过的数据，在将来被再次访问的概率更高；而很久没被访问的数据，将来被访问的概率也更低”。因此，当缓存空间已满，需要淘汰旧数据来存入新数据时，它会优先淘汰那个“最近最少使用”的数据。

算法原理与数据结构

为了实现 LRU，我们需要高效地完成两件事：

  1. 快速查找：判断一个数据是否在缓存中。

  2. 快速排序：能清晰地记录数据的访问顺序（最近使用的和很久未使用的），并在需要时快速淘汰最久未使用的数据。

单纯使用数组或链表都无法同时满足这两点。因此，LRU 通常由 哈希表（Hash Table） 和 双向链表（Doubly Linked List） 两种数据结构结合实现。

  • 双向链表（用于排序）：

    • 作用：模拟访问顺序。链表头部是 最近使用的（Most Recently Used, MRU），尾部是 最久未使用的（LRU）。
    • 操作：
      • 每当一个数据被访问（get）或添加（put），它就被移动到链表头部。
      • 当需要淘汰数据时，直接删除链表尾部的节点。
    • 为什么是双向链表？ 因为删除一个节点（尤其是中间节点）需要知道其前驱节点，单链表无法在 O(1) 时间内完成。

  • 哈希表（用于快速查找）：

    • 作用：提供 Key 到 链表节点 的快速映射。
    • 操作：通过 Key 可以立刻找到对应的链表节点，从而在 O(1) 时间内获取值或定位节点以便将其移动到头部。

三种实现方案

可以选择链表或者是数组来构建

  1. 数组实现，构建数组，其中每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰（插入、删除，时间复杂度O(n)）。

  2. 链表实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃（访问时间复杂度为O(n)）。

  3. 链表+hash。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

    1
    2
    3
    4
    5
    6
    7
    // 通过HashMap中`key`存储Node的`key`,`value`存储Node来建立Map对Node的映射关系
    class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> prev;
        private Node<K,V> next;
    }
img

1、新数据插入到链表头部；
2、每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3、当链表满的时候，将链表尾部的数据丢弃。

基于数组实现

利用数组 + 时间戳 实现。避免了数组下标值的移动，但是需要遍历所有值，并比较时间戳大小。

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
/**
 * <b>   基于数组实现lru   </b>
 * <p> 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，
 * 并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0
 * 当数组空间已满时，将时间戳最大的数据项淘汰。
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/7/12 16:03
 */
public class ArrLruDemo {

    public static void main(String[] args) {
        ArrLru arrLru = new ArrLru(3);
        arrLru.add(11);
        arrLru.add(22);
        arrLru.add(33);
        arrLru.add(33);

        arrLru.print();
        System.out.println("---------------------");
        System.out.println(arrLru.get());
        System.out.println(arrLru.get(22));

        arrLru.add(44);

        System.out.println("---------------------");
        arrLru.print();
    }
}

class ArrLru {
    private final ArrLruNode[] datas;
    private final int maxSize;    // 数组最大大小
    private int size;       // 数组实际大小

    public ArrLru(int maxSize) {
        this.maxSize = maxSize;
        this.datas = new ArrLruNode[maxSize];
    }

    public void print() {
        System.out.println(Arrays.toString(datas));
    }

    // 添加数据
    public void add(int value) {
        int index = size;
        if (size == maxSize) {  // 满了
            index = maxTS();  // 替换最大遗漏的
        }

        for (int i = 0; i < datas.length; i++) {
            if (datas[i] == null)
                continue;

            if (datas[i].value == value) {
                datas[i].ts = 0;
                index = -1;
            } else
                datas[i].ts++;
        }

        if (index >= 0) {
            datas[index] = new ArrLruNode(value);
            size++;
        }
    }

    // 获得最新使用的数据
    public int get() {
        int index = -1;
        for (int i = 0; i < datas.length; i++) {
            if (datas[i] == null)
                continue;

            if (datas[i].ts == 0) {
                datas[i].ts = 0;
                index = i;
            } else
                datas[i].ts++;
        }

        return index;
    }

    public int get(int value) {
        int idnex = -1;

        for (int i = 1; i < datas.length; i++) {
            if (datas[i] == null)
                continue;

            if (datas[i].value == value) {
                idnex = i;
                datas[i].ts = 0;
            } else
                datas[i].ts++;
        }

        return idnex;
    }

    // 获得时间戳最大的（下标）
    public int maxTS() {
        int index = 0;
        long maxUserd = datas[index].ts;

        for (int i = 1; i < datas.length; i++) {
            if (datas[i].ts > maxUserd) {
                index = i;
                maxUserd = datas[i].ts;
            }
        }

        return index;
    }

    @NoArgsConstructor
    @ToString
    static class ArrLruNode {
        public int value;       // 储存数据
        public long ts;      // 使用时间戳

        public ArrLruNode(int value) {
            this.value = 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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
/**
 * <b>   基于链表实现lru   </b>
 * <p> 每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/7/24 20:27
 */
public class ListLru {

    public static void main(String[] args) throws CloneNotSupportedException {
        LruNode<String, Integer> lru = new LruNode<>(8);
        lru.add("11", 11);
        lru.add("22", 22);
        lru.add("33", 33);
        lru.add("55", 55);

        System.out.println(lru.get("33"));

        System.out.println("------------------");
        System.out.println(lru.getHead());
        System.out.println(lru.getTail());

//        lru.print();
    }

}

class LruNode<K, V> {
    private ListLruNode<K, V> head;
    private ListLruNode<K, V> tail;
    private final int maxSize;
    private int size;

    public LruNode(int maxSize) {
        this.maxSize = maxSize;
    }

    public ListLruNode<K, V> getHead() {
        return this.head;
    }

    public ListLruNode<K, V> getTail() {
        return tail;
    }

    // 添加（当已存在key，当满了）
    public void add(K k, V v) {
        ListLruNode<K, V> node = new ListLruNode<>(k, v);
        if (head == null) {
            head = node;
            head.next = tail;
            tail = node;
            tail.pre = head;
            size = 1;
            return;
        }

        ListLruNode<K, V> parent = head;
        if (parent.key.equals(k)) {
            parent.value = v;
            return;
        }

        if (parent.remove(k)) // 移除已经存在的（根据key）
            size--;

        if (size == maxSize) { // 满了
            parent.remove();
            size--;
        }
        tail = parent.getTail();

        node.next = parent; // 插入头部
        node.next.pre = node;
        head = node;
        size++;
    }

    // 根据k获取
    public V get(K k) throws CloneNotSupportedException {
        ListLruNode<K, V> parent = head;
        if (parent == null)
            return null;

        ListLruNode<K, V> node = parent.get(k);
        if (node == null)
            return null;

        if (node.key.equals(head.key))
            return node.value;

        tail = parent.getTail();

        node.next = head; // 替换头节点
        head.pre = node;
        head = node;

        return node.value;
    }

    // 打印
    public void print() {
        ListLruNode<K, V> parent = head;
        if (parent == null)
            return;

        while (parent != null) {
            System.out.println(parent);

            parent = parent.next;
        }
    }

}

// 链表节点
class ListLruNode<K, V> implements Cloneable {
    public K key;
    public V value;
    public ListLruNode<K, V> pre;
    public ListLruNode<K, V> next;

    public ListLruNode(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public ListLruNode(ListLruNode<K, V> node) {
        this.key = node.key;
        this.value = node.value;
        this.next = node.next;
        this.pre = node.pre;
    }

    @Override
    public String toString() {
        return "ListLruNode{" +
                "key=" + key +
                ", value=" + value +
//                ", pre=" + pre +
                ", next=" + next +
                '}';
    }

    @Override
    protected ListLruNode<K, V> clone() throws CloneNotSupportedException {
//        ListLruNode<K, V> node = new ListLruNode<>(this);
        ListLruNode<K, V> node = (ListLruNode<K, V>) super.clone(); // 浅拷贝
        node.key = this.key;
        node.value = this.value;
// 深拷贝
        node.pre = this.pre;
        node.next = this.next;
        return node;
    }

    // 迭代获取
    public ListLruNode<K, V> get(K k) {
        if (k == null)
            return null;

        if (this.key.equals(k)) {
            if (this.pre != null)
                this.pre.next = this.next; // 移除该节点

            return this;
        }
        return this.next == null ? null : this.next.get(k);
    }

    // 获得最后一个节点
    public ListLruNode<K, V> getTail() {
        if (this.next != null)
            return this.next.getTail();
        else
            return this;
    }

    // 移除最后一个节点
    public void remove() {
        if (this.next != null) {
            this.next.remove();
        } else
            this.pre.next = null; // 移除最后一个
    }

    // 移除已存在的key节点
    public boolean remove(K k) {
        if (this.key.equals(k)) {
            if (this.pre != null) { // 非头部
                this.pre.next = this.next; // 移除该节点
                return true;
            }
            return false;
        }

        if (this.next != null)
            return this.next.remove(k);

        return false;
    }
}

基于链表+Hash实现

基于双链表和hash数组实现

其核心实现结合了哈希表（快速查找）和双向链表（维护访问顺序） 两种数据结构，使得所有操作都能在常数时间内完成。

  • HashMap：存储 key → Node，实现 O(1) 查找。

  • 双向链表：维护访问顺序，头节点为最新访问，尾节点为最久未访问。

  • 每次访问或插入，将节点移到头部；容量超限时，删除尾部节点。

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
/**
 * <b>   基于数组、链表和hash实现lru   </b>
 * <p> 用一个数组来存储链表节点数据，每次hash直接定位到该链表。hash冲突用双向链表。
 * 每次将插入、最新查找的节点添加至链表头部
 * 当链表数量达到最大值时，将末尾链表节点移除。
 *
 * @Author Haeng
 * @Email haeng2030@gmail.com
 * @Date 2021/7/12 16:03
 */
public class ArrLruMapDemo {

    public static void main(String[] args) {
        // 输出结果： 1，2，null，3，4
        ArrLruMap<String, Integer> map = new ArrLruMap<>(3);
        map.add("1", 1);
        map.add("2", 2);
        System.out.println(map.get("1"));
        map.add("3", 3);
        System.out.println(map.get("2"));
        map.add("4", 4);
        System.out.println(map.get("1"));
        System.out.println(map.get("3"));
        System.out.println(map.get("4"));

        System.out.println("---------------------");
        map.print();
    }
}

class ArrLruMap<K, V> {
    private final ArrLruMapNode<K, V>[] datas;
    private final int maxSize;    // 数组最大大小
    private volatile int size;       // 数组实际大小

    public ArrLruMap(int maxSize) {
        this.maxSize = maxSize;
        this.datas = new ArrLruMapNode[maxSize];
        head = new ArrLruMapNode<>();
        tail = new ArrLruMapNode<>();
        head.after = tail;
        tail.before = head;
    }

    private final ArrLruMapNode<K, V> head;
    private final ArrLruMapNode<K, V> tail;

    private int getIndex(K key) {
        int h = 0;
        return (h = (key.hashCode() ^ 32) % maxSize) < 0 ? (h * -1) : h;

//        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public void print() {
        System.out.println(Arrays.toString(datas));
    }

    // 添加数据
    public void add(K key, V value) {
        if (key == null)
            throw new IllegalArgumentException("key must not null");

        int index = getIndex(key);
        ArrLruMapNode<K, V> data = datas[index];
        ArrLruMapNode<K, V> node = new ArrLruMapNode<>(key, value);
        ArrLruMapNode<K, V> temp = null;
        if (data == null) { // 新添加
            datas[index] = node;
            addToHead(node);
            temp = node;

        } else { // 更新存在的
            // 查找是否存在，如果不存在直接加入，否则就移除并加至头部
            temp = replaceAndGet(data, key, value);
            if (temp != null) {
                temp.next = node;
                node.pre = temp;

                addToHead(node);
            }
        }

        if (temp != null)
            size++;

        if (size > maxSize) {  // 满了
            removeLast();
        }
    }

    // 将节点插入到头部
    private void addToHead(ArrLruMapNode<K, V> node) {
        head.after.before = node;
        node.after = head.after;

        head.after = node;
        node.before = head;
    }

    // 移除以前的，并加至头部
    private void moveToHead(ArrLruMapNode<K, V> node, boolean toHead) {
        node.after.before = node.before;
        node.before.after = node.after;

        if (toHead)
            addToHead(node);
    }

    // 如果存在，将已存在节点的值替换并移到头部。
    // 如贵不存在，返回拉链表的最后一个节点
    private ArrLruMapNode<K, V> replaceAndGet(ArrLruMapNode<K, V> root, K key, V value) {
        ArrLruMapNode<K, V> node = root;
        ArrLruMapNode<K, V> next = null;
        while (node != null) {
            if (node.key.equals(key)) {

                node.value = value;
                moveToHead(node, true);
                next = null;
                break;
            }
            next = node;
            node = node.next;
        }

        return next;
    }

    // 如果存在，将指定的节点移至头部并返回
    private ArrLruMapNode<K, V> moveAndGet(ArrLruMapNode<K, V> root, K key) {
        ArrLruMapNode<K, V> node = root;
        ArrLruMapNode<K, V> temp = null;
        while (node != null) {
            if (node.key.equals(key)) {

                moveToHead(node, true);

                temp = node;
                break;
            }
            node = node.next;
        }

        return temp;
    }

    // 移除最后一个
    private void removeLast() {
        remove(tail.before);
    }

    // 移除指定节点
    private void remove(ArrLruMapNode<K, V> node) {
        if (node == null)
            return;

        int index = getIndex(node.key);

        if (node.next == null && node.pre == null) {
            datas[index] = null;
        } else {

            if (node.next != null)
                node.next.pre = node.pre;

            if (node.pre != null)
                node.pre.next = node.next;

            if (node.pre == null)
                datas[index] = node.next;
        }

        // 移除链表中已存在的
        moveToHead(node, false);

        size--;
    }

    // 获得指定数据
    public V get(K key) {
        if (key == null)
            throw new IllegalArgumentException("key must not null");

        ArrLruMapNode<K, V> node = head.after;
        if (node != null && key.equals(node.key))
            return node.value;

        int index = getIndex(key);
        node = datas[index];
        if (node == null)
            return null;

        node = moveAndGet(node, key);

        return node == null ? null : node.value;
    }


    // 节点
    static class ArrLruMapNode<K, V> {
        K key;
        int hash;
        volatile V value;       // 储存数据

        // 双链表
        volatile ArrLruMapNode<K, V> before;
        volatile ArrLruMapNode<K, V> after;
        // hash冲突拉链链表
        volatile ArrLruMapNode<K, V> next;
        volatile ArrLruMapNode<K, V> pre;

        public ArrLruMapNode() {
        }

        public ArrLruMapNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

Java 中如何应用

方式 优点 缺点 适用场景
LinkedHashMap 简单、内置、代码少 非线程安全 简单单线程场景
手动双向链表 可控性强，适合面试 代码复杂，易出错 学习/面试/定制需求
Guava Cache 功能丰富，成熟稳定 性能略逊于 Caffeine 一般项目
Caffeine 高性能，功能强，推荐生产使用 需要引入第三方依赖 生产环境高性能缓存

使用内置类：LinkedHashMap

最简单、最常用的方式。LinkedHashMap 内部维护了插入或访问顺序，通过重写 removeEldestEntry() 方法可以实现自动淘汰最久未使用的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true 表示按访问顺序排序（LRU核心）
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当 size > capacity 时，移除最老的元素
        return size() > capacity;
    }
}

使用第三方库

  • Guava

    Guava 的 Cache 支持多种淘汰策略（包括 LRU），还支持过期时间、加载函数等高级功能。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    import com.google.common.cache.Cache;
    import com.google.common.cache.CacheBuilder;

    Cache<Integer, String> cache = CacheBuilder.newBuilder()
        .maximumSize(100)
        .build();

    cache.put(1, "A");
    String value = cache.getIfPresent(1);

  • Caffeine

    Caffeine 是目前 Java 生态中性能最好的本地缓存库，基于 Guava 改进，支持 Window TinyLFU 等更优算法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    import com.github.benmanes.caffeine.cache.Cache;
    import com.github.benmanes.caffeine.cache.Caffeine;

    Cache<Integer, String> cache = Caffeine.newBuilder()
        .maximumSize(100)
        .build();

    cache.put(1, "A");
    String value = cache.getIfPresent(1);