力扣146｜LRU缓存淘汰算法

LRU缓存淘汰算法

leet code146: https://leetcode.cn/problems/lru-cache

一、基本思想

1.1 基本思想

LRU全名Last Recently Used，即当缓存空间满时，优先淘汰最不常使用（访问）的缓存。

1.2 抽象接口

1、 init() 初始化大小为N的缓存空间

2、 put(key, val) 将id为key的缓存加入缓存空间，要求O（1）时间复杂度

3、get(key) 得到id为key的缓存，要求O（1）时间复杂度

明确行为：

要实现缓存访问时间的区别，所选的数据结构最好能保持元素有序。

在put存一个缓存时，有可能是插入，也有可能是更新。不论是插入还是更新，id为key的缓存页都被访问了一次，需要将它的优先级提高。插入时还需要考虑缓存满，需要选择一个缓存页淘汰。

在get一个缓存时，访问了一遍id为key的缓存，需要提高它的优先级。

二、代码实现

2.1 数据结构

插入删除要求O（1），自然是选择链表。

查找更新要求O（1），肯定是哈希表。

两者结合就形成了哈希链表，LinkedHashMap。

2.2 借助API实现

class LRUCache {
    int cap;
    // 插入队尾，就是最常使用的
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int get(int key) {
        int val = -1;
        if(cache.containsKey(key)){
            // 得到值
            val = cache.get(key);
            // 提升这个值到队尾
            cache.remove(key);
            cache.put(key, val);
        }
        return val;
    }
    
    public void put(int key, int val) {
        if(cache.containsKey(key)){
            cache.put(key, val); //变更数据
            this.get(key);
            return;
        }else{
            // 插入需要先判断容量是否已满
            if(cache.size()>=this.cap){
                // 淘汰队首
                int oldKey = cache.keySet().iterator().next();
                cache.remove(oldKey);
            }
                cache.put(key, val);
            }
        }
    }
}
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

我们用链表存数据，最新的数据插入到队尾。

get要做的事情：得到key对应的值，将key优先级提高。

put要做的事情：判断key在不在链表中，相应的修改/插入操作行为。

​ 修改操作：修改值，提升优先级。

​ 插入操作：判断队伍空间是否满，已满需要淘汰队首。然后在插入。

2.3 自己实现哈希链表

（1）想明白

要做哪些事？

• 自己实现双向链表
• 利用HashMap哈希表
• 整合这两个为哈希链表

哈希链表要实现哪些API？

• get 根据key得到值
• put 根据key进行修改或插入操作
• remove 删除指定key

双向链表要实现的API：

• 插入节点
• 删除节点（给出Node）

（2）双向链表实现

class Node{
    public int key,val;
    public Node prev,next;
    Node(int key, int val){
        this.key = key;
        this.val = val;
        prev = null;
        next = null;
    }
}

class DoubleList{
    private Node dummyNode;
    public int size;
    DoubleList(){
        dummyNode = new Node(-1, -1);
        dummyNode.prev = dummyNode;
        dummyNode.next = dummyNode;
        size = 0;
    }
    public void insert(Node tmp){
       tmp.prev = dummyNode.prev;
       tmp.next = dummyNode;
       dummyNode.prev.next = tmp;
       dummyNode.prev = tmp;
       size+=1;
    }
    public void remove(Node tmp){
       if(size<=0) return;
       Node front  = tmp.prev;
       Node rear = tmp.next;
       front.next = rear;
       rear.prev = front;
       tmp.prev = null;
       tmp.next = null;
       size-=1;
    }
    public int removeFirst(){
        int ret = dummyNode.next.key;
        remove(dummyNode.next);
        return ret;
    }
}
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

技巧：

• 伪头节点
• 循环链表

(3) LRUCache实现

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;
    public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        Node tmp = map.get(key);
        int val = -1;
        if(tmp==null) return val;
        val = tmp.val;
        cache.remove(tmp);
        cache.insert(tmp);
        return val;
    }
    
    public void put(int key, int val) {
        Node tmp = map.get(key);
        if(tmp==null){
            // 插入操作,判断队满
            if(cache.size == cap){
               int oldkey = cache.removeFirst();
               map.remove(oldkey);
            }
            Node new_tmp = new Node(key,val); 
            map.put(key, new_tmp);
            cache.insert(new_tmp);
        }else{
            // 更新操作
            cache.remove(tmp);
            tmp.val = val;
            cache.insert(tmp);
        }
    }
}
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