力扣题目 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);

    }

}

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

自己实现哈希链表

实现 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);

    }

}

因此我们要实现 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() {}

}

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

class MyLinkedHashMap {

	// 哈希表

	HashMap<Integer, Node> map = new HashMap<>();

	// 双链表

	DoubleList doubleList = new DoubleList();

}

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

	// 获取 key 对应的 value

	public int get(int key) {

		return map.get(key).value;

	}

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);

	}

remove 方法

	// 删除 value 对应的元素

	public void remove(int key) {

		Node node = map.get(key);

		doubleList.remove(node);

		map.remove(key);

	}

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

	// 删除链表首元素（也就是最近不被使用的元素）

	public void removeEldest() {

		Node node = doubleList.removeFirst();

		map.remove(node.key);

	}

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

	// 返回是否存在该 key

	public boolean containsKey(int key) {

		return map.containsKey(key);

	}

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

	// 返回当前容量

	public int size() {

		return map.size();

	}

这样，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();

	}

}

实现双链表

由于 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;

	}

}

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

class DoubleList {

	// 在链表尾部新增一个元素

	public void addLast(Node node) {}

	// 从双链表中删除指定元素

	public void remove(Node node) {}

	// 删除首元素

	public void removeFirst() {}

}

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

	// 在链表尾部新增一个元素

	public void addLast(Node node) {

		node.pre = tail.pre;

		node.next = tail;

		tail.pre.next = node;

		tail.pre = node;

		size++;

	}

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

	// 从双链表中删除指定元素

	public Node remove(Node node) {

		node.pre.next = node.next;

		node.next.pre = node.pre;

		size--;

	}

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;

	}

因此 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;

	}

}

再补一下双链表的节点类

class Node {

	// key, value

	int key, value;

	// 前驱节点, 后继节点

	Node pre, next;

	public Node() {}

	public Node(int key, int value) {

		this.key = key;

		this.value = value;

	}

}

自己实现的完整代码

最后，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;

	}

}

总结

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

参考资料

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

最新文章

1. Oracle逻辑结构（TableSpace→Segment→Extent→Block）
2. TOMCAT配置外部应用
3. 【面试题】TB
4. map reduce filter
5. Java SE 第十讲---面向对象特征之封装2
6. FPGA仿真设置步骤
7. RandomAccessFile、FileChannel、MappedByteBuffer读写文件
8. DynamoDB Local for Desktop Development
9. day52
10. art.dialog
11. [国嵌攻略][048][MMU配置与使用]
12. BZOJ 3198: [Sdoi2013]spring [容斥原理 哈希表]
13. c#一步一步实现ORM（二）
14. 不使用DataContext直接将ViewModels绑定到ItemsControl控件
15. Jetpack 架构组件 Paging 分页加载 MD
16. 高通adsp架构下sensor
17. 【Ｃ＋＋】std：：是什么？
18. bootstrap 参考文档
19. ACTIVEMQ主题、队列设置用户名密码
20. HBase学习之路 （十）HBase表的设计原则

热门文章

1. 齐博x1如何调试查找全站的表单提交接口参数
2. 齐博x1页面报数据表错误如何修复
3. .Net Core - 使用事务IDbtransaction操作DBData
4. Netty学习记录-入门篇
5. 不用终端运行 Vue项目 基于Pycharm
6. react的组件通信
7. EasyPoi 导出Excel(ExcelExportEntity生成表头)
8. Vue.js3.0练习题
9. 前端面试HTML和CSS总结，这一篇就够了！
10. Go语言核心36讲01