【LeetCode】 LRU 缓存机制 Java 题解

作者：Albert

2022-10-18
北京
本文字数：2218 字
阅读完需：约 1 分钟

题目描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。


示例：
输入["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出[null, null, null, 1, null, -1, null, -1, 3, 4]
解释LRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); // 缓存是 {1=1}lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}lRUCache.get(1);    // 返回 1lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}lRUCache.get(2);    // 返回 -1 (未找到)lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}lRUCache.get(1);    // 返回 -1 (未找到)lRUCache.get(3);    // 返回 3lRUCache.get(4);    // 返回 4 
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/lru-cache著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是设计类题目，LRUCache 是经典的题目，题目中定义了 put,get 两种方法，我们需要去实现。具体分析来看，在 O(1)的时间复杂度内完成 get,put,我们需要一种高效的存储服务, 在常用的数据结构中, hashMap 是最常用的高效结构。我们还需要记录数据访问的顺序，来确定哪些数据是最久未访问的。一般用链表来记录，链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便。在实际使用过程中，我们一般使用双端链表，方便操作。双端链表头部是最近使用的键值，尾部是最久未使用的键值。
Java 中的 LinkedHashMap 已经实现了 LRU 的内容，我们可以直接使用。一般写算法题目，不建议直接调用系统 API。我们往往需要自己实现一个双端链表。我们首先定义双端链表节点 DLinkedNode,主要的属性有 key,value, prev,next。初始化的时候，我们使用使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限。为什么要这样做呢？我们这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。可以减少判断逻辑。在 get 方法中，首先判断 key 是否存在，若存在，还需要将这个节点移动到链表的头部。在 put 方法中，还需要主要判断是否超过了最大的 capacity,若超过 capacity,则还需要删除最久未使用的节点。具体实现代码如下，供参考。

通过代码

public class LRUCache {    class DLinkedNode {        int key;        int value;        DLinkedNode prev;        DLinkedNode next;        public DLinkedNode() {}        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}    }
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();    private int size;    private int capacity;    private DLinkedNode head, tail;
    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;        head = new DLinkedNode();        tail = new DLinkedNode();        head.next = tail;        tail.prev = head;    }
    public int get(int key) {        DLinkedNode node = cache.get(key);        if (node == null) {            return -1;        }        moveToHead(node);        return node.value;    }
    public void put(int key, int value) {        DLinkedNode node = cache.get(key);        if (node == null) {            DLinkedNode newNode = new DLinkedNode(key, value);            cache.put(key, newNode);            addToHead(newNode);            ++size;            if (size > capacity) {                DLinkedNode tail = removeTail();                cache.remove(tail.key);                --size;            }        }        else {            node.value = value;            moveToHead(node);        }    }
    private void addToHead(DLinkedNode node) {        node.prev = head;        node.next = head.next;        head.next.prev = node;        head.next = node;    }
    private void removeNode(DLinkedNode node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }
    private void moveToHead(DLinkedNode node) {        removeNode(node);        addToHead(node);    }
    private DLinkedNode removeTail() {        DLinkedNode res = tail.prev;        removeNode(res);        return res;    }}