LRU 怎么实现？怎么实现 O(1) 增加删除？不用 Hashmap 可以吗？

有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步, 认准 https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java 面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。https://store.amazingmemo.com/chapterDetail/1685324709017001`

LRU 缓存机制的实现

LRU（Least Recently Used）缓存机制是一种常见的页面置换算法，用于管理缓存中的数据。它会淘汰最长时间未被使用的数据，以便为新的数据腾出空间。要实现一个高效的 LRU 缓存，我们需要在 O(1) 时间复杂度内完成以下操作：

  • 获取数据（get）
  • 添加新数据（put）

使用 LinkedHashMap 实现 LRU

在 Java 中，可以通过 LinkedHashMap 来实现一个简单的 LRU 缓存。LinkedHashMap 内部维护了一个双向链表来记录插入顺序或访问顺序，这使得它非常适合实现 LRU 缓存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

在这个实现中，我们重写了 removeEldestEntry 方法，当缓存大小超过容量时，它会移除最老的元素（最少使用的元素）。

使用 HashMap 和 双向链表 实现 LRU

为了实现 O(1) 的增加和删除操作，我们通常会使用 HashMap 结合双向链表。HashMap 提供 O(1) 的查找速度，而双向链表可以在 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
public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    private void addNode(DLinkedNode node) {
        // 添加节点的实现
    }

    private void removeNode(DLinkedNode node) {
        // 移除节点的实现
    }

    private void moveToHead(DLinkedNode node) {
        // 将节点移动到头部的实现
    }

    private DLinkedNode popTail() {
        // 移除尾部节点的实现
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
}

方法实现

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
public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    tail = new DLinkedNode();

    head.next = tail;
    tail.prev = head;
}

public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;

    // 移动到头部
    moveToHead(node);

    return node.value;
}

public void put(int key, int value) {
    DLinkedNode node = cache.get(key);

    if(node == null) {
        DLinkedNode newNode = new DLinkedNode();
        newNode.key = key;
        newNode.value = value;

        cache.put(key, newNode);
        addNode(newNode);

        ++size;

        if(size > capacity) {
            // 移除尾部节点
            DLinkedNode tail = popTail();
            cache.remove(tail.key);
            --size;
        }
    } else {
        // 更新值
        node.value = value;
        moveToHead(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
private void addNode(DLinkedNode node) {
    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
}

private void removeNode(DLinkedNode node) {
    DLinkedNode prev = node.prev;
    DLinkedNode next = node.next;

    prev.next = next;
    next.prev = prev;
}

private void moveToHead(DLinkedNode node) {
    removeNode(node);
    addNode(node);
}

private DLinkedNode popTail() {
    DLinkedNode res = tail.prev;
    removeNode(res);
    return res;
}

不使用 HashMap 的实现

不使用 HashMap 的话，我们无法在 O(1) 时间内完成查找操作。如果使用其他数据结构（如数组或链表），查找操作的时间复杂度至少是 O(n)，这将导致整个 LRU 缓存的效率下降。因此，在实现高效的 LRU 缓存时，HashMap 是不可或缺的组成部分。