LRU缓存机制实现

Mar 4, 2021, 7:51 pm

一、 LRU缓存说明：

本文来自于LeetCode第146题(LRU 缓存机制)，在面试中经常出现，算是比较热门的算法题。
LRU(Least Recently Used, 最久最少使用)算法在实际应用中非常广泛，比如CPU cache中，memcache/redis缓存中。
理解并掌握LRU算法的实现，算是基本要求。

二、 LRU缓存算法JAVA实现

算法要求：

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

在实现这道题(LRU 缓存机制)的时候，考虑到hashmap在最差情况下无法实现O(1)的要求，底层我没有采用hashmap实现，而是采用了数组的实现。
原题中

1 <= capacity <= 3000

所以我取巧底层采用容量为3001的数组，实现起来比使用hashmap要复杂。
官方题解使用hashmap，一般来讲hashmap的平均时间复杂度接近O(1)，所以也讲得通。

考虑到本题的主要目的是考察对双向链表的使用，所以也不必纠结于是数组还是hashmap。
以下是我的实现，代码逻辑不复杂，就不多讲解了，看代码和注释应该能懂。

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
class LRUCache {
    Node head, tail;
    Node[] nodes;
    int size = 0;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        nodes = new Node[3001];
    }
    
    public int get(int key) {
        Node node = nodes[key];
        if(node == null) return -1;
        Node pre = node.pre, next = node.next;
        if(pre != null && next != null) {
            // 在中间
            midToHead(node, pre, next);
        } else if(next != null) {
            // 在尾
            tailToHead(node, next);
        }
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = nodes[key];
        if (node != null) {
            node.value = value;
            Node pre = node.pre, next = node.next;
            if(pre != null && next != null) {
                // 在中间
                midToHead(node, pre, next);
            } else if(next != null) {
                // 在尾
                tailToHead(node, next);
            }
        } else {
            // 新增
            node = new Node(key, value);
            nodes[key] = node;
            if(head != null) {
                // 插入到头
                node.pre = head;
                head = head.next = node;
            } else {
                // 第一个元素
                tail = head = node;
            }
            if(++size > capacity) {
                // 删除最久未用
                int oldKey = tail.key;
                nodes[oldKey] = null;
                tail.next.pre = null;
                tail = tail.next;
                size--;
            }
        }
    }
    private void midToHead(Node node, Node pre, Node next) {
        pre.next = next;
        next.pre = pre;
        node.pre = head;
        node.next = null;
        head = head.next = node;
    }
    private void tailToHead(Node node, Node next) {
        tail = next;
        next.pre = null;
        node.pre = head;
        node.next = null;
        head = head.next = node;
    }
}

class Node {
    int value;
    int key;
    Node pre;
    Node next;
    public Node(int key, int value){this.value = value; this.key = key;}
}

三、总结

  1. 面试碰到这个题目，最好别用LinkedHashMap重写removeEldestEntry方法来实现，毕竟面试官出这个题目是为了考察你是否掌握了LRU算法；
  2. 实际工作中，反而推荐重写removeEldestEntry方法实现，即使你会自己实现，也还是推荐LinkedHashMap的实现。毕竟代码中需要的是稳定靠谱的实现方法，重新实现的话还需要严密的测试，无论从效率还是收益上来说都不划算;
  3. 算法不复杂，主要是需要心细，移动节点的时候，前后的节点链接需要处理好，遗漏任何一个都会导致算法失败；
  4. 算法实现还有可以优化的地方，比如双向链表增加头指针和尾指针，代码逻辑会更加简洁，读者也可以尝试进行优化。