Java 基于 LinkedHashMap 实现 LRU 缓存

发表于 阅读次数： 评论数： 本文字数： 427 阅读时长 ≈ 1 分钟

核心思想

  • LRU（最近最少使用）算法最常见的实现方法是使用一个双向链表或类似的数据结构，最近访问的数据会被移动到链表头部，链表尾部的节点就是最久未被访问的数据。
  • LRU 算法可以使用双向链表实现，也就是在各个 Node 节点之间增加 prev 指针和 next 指针，以此构成双向链表。将新增或者访问到的节点移动到链表的头部，超出容量时则从链表的尾部删除节点。
  • 要满足 O (1) 时间复杂度，可以使用 HaspMap，里面储存的是 key 与链表节点，这样可以快速查找节点，然后将它删除或者移动到链表的头部。
  • LRU 的算法核心是哈希链表，本质就是哈希表 + 双向链表的结合体 (HashMap + DoubleLinkedList)，时间复杂度是 O (1)，底层的数据结构如下图所示：

  • 下面这幅动图完美诠释了 HashMap + DoubleLinkedList 的工作原理，其中 key2 是最近访问的数据（可以将其移动到双向链表的尾部或者头部）。

扩展阅读

代码实现

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
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    /**
     * 缓存容量
     */
    private final int capacity;

    /**
     * 负载因子
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public LRUCache(int capacity) {
        // 调用父类的构造方法，并传入参数 accessOrder = true，让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部
        super(capacity, DEFAULT_LOAD_FACTOR, true);
        this.capacity = capacity;
    }

    /**
     * 重写父类方法，判断是否需要删除最近最久未使用的节点
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > capacity;
    }
    
    public int getCapacity() {
        return capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, Integer> lruCache = new LRUCache(3);

        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        System.out.println(lruCache.keySet());

        lruCache.put(4, 4);
        System.out.println(lruCache.keySet());

        lruCache.put(3, 3);
        System.out.println(lruCache.keySet());
        lruCache.put(3, 3);
        System.out.println(lruCache.keySet());
        lruCache.put(3, 3);
        System.out.println(lruCache.keySet());
        lruCache.put(5, 5);
        System.out.println(lruCache.keySet());
    }

}

程序执行的输出结果：

1
2
3
4
5
6
[1, 2, 3]
[2, 3, 4]
[2, 4, 3]
[2, 4, 3]
[2, 4, 3]
[4, 3, 5]