LRU缓存机制

LRU缓存机制：

• 理解LUR缓存机制的逻辑
• 理解LRU的算法
• LRU算法设计
• 代码实现

---

LUR缓存机制：

LRU 算法就是一种缓存淘汰策略，原理不难，但是面试中写出没有 bug 的算法比较有技巧，需要对数据结构进行层层抽象和拆解，本文就带你写一手漂亮的代码。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

常见的场景如手机的后台运行缓存，我们依次打开了[王者荣耀] [淘宝] [微信] [抖音]，假设手机只允许同时打开个应用程序，那么在我们打开抖音的那一刻，就会将最久未使用的 [王者荣耀] 关闭，腾出空间给 抖音

---

LRU的算法描述：

1. 接收一个capacity的参数作为缓存的最大容量
2. 实现put(key,value)方法存入键值对
3. 实现get(key)方法获取key对应的value，若不存在返回-1

代码如下：

//缓存容量为2
LRUCache cache = new LRUCache(2);
//可以把cache理解为一个队列
//最近使用过的在队列头，久未使用的在队列尾
 
cache.put(1,1);//cache = [(1,1)]
 
cache.put(2,2);//cache = [(2,2),(1,1)]
 
cache.get(1);//此时访问了key为1的entry 因此将其移动到队列头 cache = [(1,1),(2,2)]
 
cache.put(3,3);//此时容量已满，需要删除久未使用的数据，也就是队列尾 然后插入新的数据 cache = [(3,3),(1,1)]
 
cache.get(2);//return -1
 
cache.put(1,4);//key=1已经存在，只需要覆盖value即可 且此时需要将更新的entry提前到队列头 cache = [(1,4),(3,3)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LRU算法设计：

要让LRUCache的put和get方法时间复杂度为O(1)，那么要求数据结构的查询时间为O(1)，插入时间为O(1)，删除时间为O(1)，且有序。

为了区分最近使用和久未使用的数据，我们必须要求cache有序；能够在cache中判断key是否存在；cache容量满了需要删除最后一个entry；每次访问的entry都重新放在队列头部。

为此我们可以考虑到HashMap与LinkedList的结合——LinkedHashMap

LRU缓存算法的核心就是基于LinkedHashMap实现的，其核心就是通过HashMap赋予链表查询迅速的特性

代码实现：

1、先实现双向链表

class DoubleLinkedList {
    class Entry{
        int key;
        int value;
        Entry prev;
        Entry next;
 
        Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
 
    private Entry head;
 
    private Entry tail;
 
    private int size;
 
    public LRUCache() {
        //缓存初始化
        head = new Entry(0,0);
        tail = new Entry(0,0);
        head.next = tail;
        tail.prev = head;
        int size = 0;
    }
 
    //在链表首部添加entry
    public void addFirst(Entry entry) {
        entry.next = head.next;
        entry.prev = head;
        head.next.prev = entry;
        head.next = entry;
        size++;
    }
 
    //删除链表中的entry
    public void remove(Entry entry) {
        Entry prev = entry.prev;
        Entry next = entry.next;
        prev.next = next;
        next.prev = prev;
        size--;
    }
 
    //删除链表中最后一个节点并返回
    public Entry removeLast() {
        if (tail.prev == head) {
            return null;
        }
        Entry last = tail.prev;
        remove(last);
        return last;
    }
 
    public int size() {
        return size;
    }
}
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

2、结合HashMap

public class LRUCache {
    private HashMap<Integer, DoubleLinkedList.Entry> map;
 
    private DoubleLinkedList cache;
 
    private int capacity;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleLinkedList();
    }
 
    public int get(int key) {
        //若map中不存在cache映射的key return -1
        if (!map.containsKey(key)) {
           return -1;
        }
        int val = map.get(key).value;
        //将get过的entry提前,put方法直接采用了删除尾部，首部添加的策略。
        put(key,val);
        return val;
    }
 
    public void put(int key, int val) {
        DoubleLinkedList.Entry x = new DoubleLinkedList.Entry(key,val);
        if (map.containsKey(key)) {
            //可以理解为缓存队列尾部删除 首部添加
            cache.remove(map.get(key));
            cache.addFirst(x);
 
            //map中添加该entry的映射
            map.put(key,x);
        } else {
            //当缓存已满，不仅要删除最后一个Entry，还要把map中映射到该节点的key同时删除，而这个key只能通过Entry得到。
            if(capacity == cache.size()) {
                //删除链表最后一个数据
                DoubleLinkedList.Entry last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key,x);
        }
    }
}
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

原文参考LeetCode：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/