LeetCode 146：LRU 缓存

链接

思路：

LRU 算法是⼀种缓存淘汰策略 ，在操作系统的虚拟内存管理中有应用；
传统的内存管理方式有驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至结束。而事实上，在一个时间段内，只需要访问一小部分数据即可正常运行，这就导致内存中驻留了大量用不到的数据；

LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据就优先删除；

cache 这个数据结构的要求：

1. cache 中的元素必须有时序，以区分最近使⽤的和久未使⽤的数据，当容量满了之后要删除最久未 使⽤的那个元素腾位置;
2. 我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val
3. 每次访问 cache 中的某个 key，需要将这个元素变为最近使⽤的，也就是说 cache 要⽀持在任意位置快速插入和删除元素;

哈希表查找快，但是数据无固定顺序；链表有顺序之分，插⼊删除快，但是查找慢。所以结合⼀下，形成⼀种新的数据结构：哈希链表 LinkedHashMap（继承HashMap）

1. 如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使⽤的，越靠头部的元素就是 最久未使⽤的。
2. 对于某⼀个 key，我们可以通过哈希表快速定位到链表中的节点，从⽽取得对应 val。
3. 链表显然是支持在任意位置快速插⼊和删除的，改改指针就⾏。只不过传统的链表⽆法按照索引快速访问 某⼀个位置的元素，而这⾥借助哈希表，通过 key 快速映射到任意⼀个链表节点，然后进⾏插⼊和删除。

为什么要是双向链表，单链表行不行？
因为删除链表时，双向链表的前驱操作可以保证时间复杂度为O(1)，而单向链表的删除要从头遍历直到找到节点，时间复杂度为 O(n)；

既然哈希表中已经存了 key，为什么链表中还要存 key 和 val 呢，只存 val 不就⾏了？
因为在删除节点时，使用removeFirst()删除链表头部也就是最长时间未使用的节点，然后需要再根据该方法返回的这个节点的key，去删除hashmap中对应的键值对；

用双向链表和哈希表实现：
初始化：

class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最⼤容量
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    /* 将某个 key 提升为最近使⽤的 */
    private void makeRecently(int key) {
        Node x = map.get(key);
		// 先从链表中删除这个节点
        cache.remove(x);
		// 重新插到队尾
        cache.addLast(x);
    }

    /* 添加最近使⽤的元素 */
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
		// 链表尾部就是最近使⽤的元素
        cache.addLast(x);
		// 别忘了在 map 中添加 key 的映射
        map.put(key, x);
    }

    /* 删除某⼀个 key */
    private void deleteKey(int key) {
        Node x = map.get(key);
		// 从链表中删除
        cache.remove(x);
		// 从 map 中删除
        map.remove(key);
    }

    /* 删除最久未使⽤的元素 */
    private void removeLeastRecently() {
		// 链表头部的第⼀个元素就是最久未使⽤的
        Node deletedNode = cache.removeFirst();
		// 同时别忘了从 map 中删除它的 key
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将该数据提升为最近使⽤的
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧的数据
            deleteKey(key);
            // 新插⼊的数据为最近使⽤的数据
            addRecently(key, val);
            return;
        }
        if (cap == cache.size()) {
            // 删除最久未使⽤的元素
            removeLeastRecently();
        }
        // 添加为最近使⽤的元素
        addRecently(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
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

put的逻辑：

注意：Collection（List+Set）直接使用迭代器，Map使用keySet() 获得key的Set集合再使用迭代器！

用哈希链表实现：

class LRUCache {
    private int capacity;
    // 哈希链表
    LinkedHashMap<Integer,Integer> cache=new LinkedHashMap<>(); 
    public LRUCache(int capacity) {
        this.capacity=capacity;
    }
    
    // get即最近访问，要更新位置
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        // 更新位置
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        // 如果key已经存在
        if(cache.containsKey(key)){
            // 由哈希表的put()覆盖原来的value
            cache.put(key,value);
            // 更新位置
            makeRecently(key);
            // 
            return;
        }else{ // 如果key不存在
		       // 判断容量是否满
	        if(cache.size()>=this.capacity){
	            // 哈希链表头部就是最久未使⽤的 key
	            int oldKey=cache.keySet().iterator().next();
	            cache.remove(oldKey);
	        }
	        // 如果key不存在，直接添加
	        cache.put(key,value);
    	}
	}


    // 更新节点为最近位置
    private void makeRecently(int key){
        // 获取哈希链表中对应的value
        int val=cache.get(key);
        // 删除
        cache.remove(key);
        // 重新添加至末尾
        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
38
39
40
41
42
43
44
45
46
47
48
49
50