• LRU 缓存

    力扣题目 146. LRU 缓存

    实现 LRU 缓存需要用到哈希链表 LinkedHashMap。
    LinkedHashMap 是由哈希表和双链表结合而成的，它的结构如下所示。
    在这里插入图片描述

    用自带的 LinkedHashMap 实现

    利用 Java 语言自带的 LinkedHashMap 很容易实现 LRU 缓存。

    class LRUCache {
    // 缓存容量
    int cap;
    // 哈希链表
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
	
	// 初始化
    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        // 如果不存在这个 key, 返回 -1
        if(!cache.containsKey(key)){
            return -1;
        }
        // 存在这个 key
        // 将该元素提升为最近使用过的
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        // 已经存在这个 key
        if(cache.containsKey(key)){
            // 修改 value 值
            cache.put(key, value);
            // 将该元素提升为最近使用过的
            makeRecently(key);
            return;
        }
        // 不存在这个 key
        // 如果容量满了
        if(cache.size() == cap){
            // 删除链表头第一个元素（最不常使用的）
            int oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }
        // 插入新元素
        cache.put(key, value);
    }

    // 将该元素提升为最近使用过的
    private void makeRecently(int key){
        int value = cache.get(key);
        // 删除该元素
        cache.remove(key);
        // 新增该元素
        cache.put(key, value);
    }
}

    • 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

    由于该题是面试高频考点，而面试官希望面试者能自己实现哈希链表，因此下面自己实现一下。

    自己实现哈希链表

    实现 MyLinkedHashMap

    考虑写一个 MyLinkedHashMap 代替 LinkedHashMap。
    下面是用 MyLinkedHashMap 代替 LinkedHashMap 的代码，为简化起见，不考虑泛型了，初始化就变成了 MyLinkedHashMap cache = new MyLinkedHashMap<>();
    大部分 LinkedHashMap 的方法都保留了，将删除双链表的首元素封装成一个新方法 cache.removeEldest();

    class LRUCache {
    // 缓存容量
    int cap;
    // 哈希链表
    MyLinkedHashMap cache = new MyLinkedHashMap();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        // 如果不存在这个 key, 返回 -1
        if(!cache.containsKey(key)){
            return -1;
        }
        // 存在这个 key
        // 将该元素提升为最近使用过的
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        // 已经存在这个 key
        if(cache.containsKey(key)){
            // 修改 value 值
            cache.put(key, value);
            // 将该元素提升为最近使用过的
            makeRecently(key);
            return;
        }
        // 不存在这个 key
        // 如果容量满了
        if(cache.size() == cap){
            // 删除链表头第一个元素（最不常使用的）
            cache.removeEldest();
        }
        // 插入新元素
        cache.put(key, value);
    }

    // 将该元素提升为最近使用过的
    private void makeRecently(int key){
        int value = cache.get(key);
        // 删除该元素
        cache.remove(key);
        // 新增该元素
        cache.put(key, value);
    }
}

    • 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

    因此我们要实现 MyLinkedHashMap 的以下方法

    class MyLinkedHashMap {

	// 获取 key 对应的 value 
	public int get(int key) {}
	// 新增一对 key, value 或修改 key 对应的 value
	public void put(int key, int value) {}
	// 删除 value 对应的元素
	public void remove(int key) {}
	// 删除链表首元素（也就是最近不被使用的元素）
	public void removeEldest() {}
	// 返回是否存在该 key
	public boolean containsKey(int key) {}
	// 返回当前容量
	public int size() {}
} 

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

    MyLinkedHashMap 是有哈希表和双链表结合而成的，类中自然有这两个数据结构。

    class MyLinkedHashMap {
	// 哈希表
	HashMap<Integer, Node> map = new HashMap<>();
	// 双链表
	DoubleList doubleList = new DoubleList();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    下面一一实现上述方法
    get 方法
    由于 LRUCache 中调用 get 方法时已经考虑了 key 不存在的情况，调用 MyLinkedHashMap 中的 get 方法时 key 一定时存在的，因此就不用考虑 key 不存在的情况了。

    	// 获取 key 对应的 value 
	public int get(int key) {
		return map.get(key).value;
	}

    • 1
    • 2
    • 3
    • 4

    put方法
    由于 LRUCache 中调用 put 方法时可以新增，也可以修改，因此要在 MyLinkedHashMap 中的 put 方法考虑这两种情况

    新增和删除要在哈希表和双链表中同时操作，保持一致性

    	// 新增一对 key, value 或修改 key 对应的 value
	public void put(int key, int value) {
		// 已经存在该 key, 修改
		if(containsKey(key)) {
			map.get(key).value = value;
			return;
		}
		// 不存在该 key, 新增
		Node node = new Node(key, value);
		doubleList.addLast(node);
		map.put(key, node);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    remove 方法

    	// 删除 value 对应的元素
	public void remove(int key) {
		Node node = map.get(key);
		doubleList.remove(node);
		map.remove(key);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    removeEldest 方法
    这个方法也体现了为什么双链表中的节点应该同时保存 key 和 value ，因为需要删除双链表的首元素，还要删除 map 中对应的 key，因此要返回被删除的首元素节点，从首元素节点中获取 key。

    	// 删除链表首元素（也就是最近不被使用的元素）
	public void removeEldest() {
		Node node = doubleList.removeFirst();
		map.remove(node.key);
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    containsKey 方法
    直接调用 map 的 containsKey() 方法。

    	// 返回是否存在该 key
	public boolean containsKey(int key) {
		return map.containsKey(key);
	}

    • 1
    • 2
    • 3
    • 4

    size 方法
    直接调用 map 的 size 方法。

    	// 返回当前容量
	public int size() {
		return map.size();
	}

    • 1
    • 2
    • 3
    • 4

    这样，MyLinkedHashMap 就写完了，该类的完整代码如下

    class MyLinkedHashMap {
	// 哈希表
	HashMap<Integer, Node> map = new HashMap<>();
	// 双链表
	DoubleList doubleList = new DoubleList();

	// 获取 key 对应的 value 
	public int get(int key) {
		return map.get(key).value;
	}
	
	// 新增一对 key, value 或修改 key 对应的 value
	public void put(int key, int value) {
		// 已经存在该 key, 修改
		if(containsKey(key)) {
			map.get(key).value = value;
			return;
		}
		// 不存在该 key, 新增
		Node node = new Node(key, value);
		doubleList.addLast(node);
		map.put(key, node);
	}
	
	// 删除 value 对应的元素
	public void remove(int key) {
		Node node = map.get(key);
		doubleList.remove(node);
		map.remove(key);
	}
	
	// 删除链表首元素（也就是最近不被使用的元素）
	public void removeEldest() {
		Node node = doubleList.removeFirst();
		map.remove(node.key);
	}
	
	// 返回是否存在该 key
	public boolean containsKey(int key) {
		return map.containsKey(key);
	}
	
	// 返回当前容量
	public int size() {
		return map.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

    实现双链表

    由于 MyLinkedHashMap 中 map 是调用 java 现成的，而 DoubleList 不是 java 现成的，因此需要自己实现 DoubleList
    DoubleList 的基本结构如下

    class DoubleList {
	// 虚拟头节点、虚拟尾节点
	Node head, tail;
	// 双链表长度
	int size;
	
	// 构造方法
	public DoubleList() {
		head = new Node(-1, -1);
		tail = new Node(-1, -1);
		head.next = tail;
		tail.pre = head;
		size = 0;
	}
}

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

    综合 MyLinkedHashMap 调用 DoubleList 的情况，需要实现 DoubleList 以下方法

    class DoubleList {
	
	// 在链表尾部新增一个元素
	public void addLast(Node node) {}
	// 从双链表中删除指定元素
	public void remove(Node node) {}
	// 删除首元素
	public void removeFirst() {}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    下面一一实现这些方法。
    addLast 方法
    在双链表尾部新增一个元素，要修改四个指针，注意顺序，防止指针丢失，先要修改不容易获得的节点的指针。

    	// 在链表尾部新增一个元素
	public void addLast(Node node) {
		node.pre = tail.pre;
		node.next = tail;
		tail.pre.next = node;
		tail.pre = node;
		size++;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    remove 方法
    从这个方法可以看出为什么选择双链表而不是单链表，因为需要在 O(1) 时间内删除任意位置的某个节点，删除一个节点需要它的前驱节点，单链表无法实现。

    	// 从双链表中删除指定元素
	public Node remove(Node node) {
		node.pre.next = node.next;
		node.next.pre = node.pre;
		size--;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    removeFirst 方法
    由于调用 removeFirst() 方法的只有 removeEldest() 方法，而 removeEldest() 方法被调用时 cache.size() == cap，而 cap 容量至少为1，因此双链表中是存在元素的，可以不用考虑双链表为空的情况。

    	// 删除首元素
	public Node removeFirst() {
		// 考虑双链表为空的情况
		if(head.next == tail){
			return null;
		}
		// 双链表不为空
		// 获取双链表首元素
		Node node = head.next;
		remove(node);
        return node;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    因此 DoubleList 的完整代码如下

    class DoubleList {
	// 虚拟头节点、虚拟尾节点
	Node head, tail;
	// 双链表长度
	int size;
	
	// 构造方法
	public DoubleList() {
		head = new Node(-1, -1);
		tail = new Node(-1, -1);
		head.next = tail;
		tail.pre = head;
		size = 0;
	}

	// 在链表尾部新增一个元素
	public void addLast(Node node) {
		node.pre = tail.pre;
		node.next = tail;
		tail.pre.next = node;
		tail.pre = node;
		size++;
	}

	// 从双链表中删除指定元素
	public void remove(Node node) {
		node.pre.next = node.next;
		node.next.pre = node.pre;
		size--;
	}

	// 删除首元素
	public Node removeFirst() {
		// 考虑双链表为空的情况
		if(head.next == tail){
			return null;
		}
		// 双链表不为空
		// 获取双链表首元素
		Node node = head.next;
		remove(node);
        return node;
	}
}

    • 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

    再补一下双链表的节点类

    class Node {
	// key, value
	int key, value;
	// 前驱节点, 后继节点
	Node pre, next;

	public Node() {}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    自己实现的完整代码

    最后，LRUcache 的完整代码如下

    class LRUCache {
    // 缓存容量
    int cap;
    // 哈希链表
    MyLinkedHashMap cache = new MyLinkedHashMap();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        // 如果不存在这个 key, 返回 -1
        if(!cache.containsKey(key)){
            return -1;
        }
        // 存在这个 key
        // 将该元素提升为最近使用过的
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        // 已经存在这个 key
        if(cache.containsKey(key)){
            // 修改 value 值
            cache.put(key, value);
            // 将该元素提升为最近使用过的
            makeRecently(key);
            return;
        }
        // 不存在这个 key
        // 如果容量满了
        if(cache.size() == cap){
            // 删除链表头第一个元素（最不常使用的）
            cache.removeEldest();
        }
        // 插入新元素
        cache.put(key, value);
    }

    // 将该元素提升为最近使用过的
    private void makeRecently(int key){
        int value = cache.get(key);
        // 删除该元素
        cache.remove(key);
        // 新增该元素
        cache.put(key, value);
    }
}

class MyLinkedHashMap {
	// 哈希表
	HashMap<Integer, Node> map = new HashMap<>();
	// 双链表
	DoubleList doubleList = new DoubleList();

	// 获取 key 对应的 value 
	public int get(int key) {
		return map.get(key).value;
	}
	
	// 新增一对 key, value 或修改 key 对应的 value
	public void put(int key, int value) {
		// 已经存在该 key, 修改
		if(containsKey(key)) {
			map.get(key).value = value;
			return;
		}
		// 不存在该 key, 新增
		Node node = new Node(key, value);
		doubleList.addLast(node);
		map.put(key, node);
	}
	
	// 删除 value 对应的元素
	public void remove(int key) {
		Node node = map.get(key);
		doubleList.remove(node);
		map.remove(key);
	}
	
	// 删除链表首元素（也就是最近不被使用的元素）
	public void removeEldest() {
		Node node = doubleList.removeFirst();
		map.remove(node.key);
	}
	
	// 返回是否存在该 key
	public boolean containsKey(int key) {
		return map.containsKey(key);
	}
	
	// 返回当前容量
	public int size() {
		return map.size();
	}
}

class DoubleList {
	// 虚拟头节点、虚拟尾节点
	Node head, tail;
	// 双链表长度
	int size;
	
	// 构造方法
	public DoubleList() {
		head = new Node(-1, -1);
		tail = new Node(-1, -1);
		head.next = tail;
		tail.pre = head;
		size = 0;
	}

	// 在链表尾部新增一个元素
	public void addLast(Node node) {
		node.pre = tail.pre;
		node.next = tail;
		tail.pre.next = node;
		tail.pre = node;
		size++;
	}

	// 从双链表中删除指定元素
	public void remove(Node node) {
		node.pre.next = node.next;
		node.next.pre = node.pre;
		size--;
	}

	// 删除首元素
	public Node removeFirst() {
		// 考虑双链表为空的情况
		if(head.next == tail){
			return null;
		}
		// 双链表不为空
		// 获取双链表首元素
		Node node = head.next;
		remove(node);
        return node;
	}
}

class Node {
	// key, value
	int key, value;
	// 前驱节点, 后继节点
	Node pre, next;

	public Node() {}

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

    • 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
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156

    总结

    通过自己阅读别人的题解，再自己实现了几遍，写出了这篇题解，也是为了帮助自己更好的理解。然而在实现的过程中仍然出了一些bug，可想在面试的时候把上述代码无bug一次写出还是比较困难的。通过自己实现这道题，也理解了东哥所说的“算法就像搭乐高”，比如先用 MyLinkedHashMap 去实现 LRUcache，再去补 MyLinkedHashMap 中的方法实现，而 MyLinkedHashMap 中又用到 DoubleList 中的一些方法，用到了哪些方法再去补，这样对我来说比较容易记忆，以后只要会用自带的 LinkedHashMap 做，就能一步步改成自己实现的了，需要哪个就去造哪个。如果对整个流程用到哪些类都比较清晰，也可以先写 Node 类，再用 Node 类实现 DoubleList，再用DoubleList 类实现 MyLinkedHashMap ，最后用 MyLinkedHashMap 类实现 LRUcache，这不就像搭乐高了吗？

    参考资料

    算法就像搭乐高：带你手撸 LRU 算法

  • 相关阅读:
    python基础练习题目
    【ros】解决protobuf的安装问题
    重磅 | 死磕 Elasticsearch 8.X 方法论认知清单（2022年国庆更新版）
    javaScript的for循环语句练习之解决鸡兔同笼问题（基础版）
    Vue学习笔记（一）
    【漏洞复现系列】二、weblogic-cve_2020_2883（RCE/反序列化）
    idea中还原dont ask again
    C++设计模式学习-面向对象设计原则
    java-php-python-ssm医患辅助系统计算机毕业设计
    LeetCode117. Populating Next Right Pointers in Each Node II
  • 原文地址：https://blog.csdn.net/m0_46283220/article/details/126458681