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

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode 力扣 难度
146. LRU Cache 146. LRU 缓存 🟠
- 剑指 Offer II 031. 最近最少使用缓存 🟠

———–

LRU 算法就是一种缓存淘汰策略，原理不难，但是面试中写出没有 bug 的算法比较有技巧，需要对数据结构进行层层抽象和拆解，本文就带你写一手漂亮的代码。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

举个简单的例子，安卓手机都可以把软件放到后台运行，比如我先后打开了「设置」「手机管家」「日历」，那么现在他们在后台排列的顺序是这样的：

但是这时候如果我访问了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样：

假设我的手机只允许我同时开 3 个应用程序，现在已经满了。那么如果我新开了一个应用「时钟」，就必须关闭一个应用为「时钟」腾出一个位置，关那个呢？

按照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未使用的，然后把新开的应用放到最上面：

现在你应该理解 LRU（Least Recently Used）策略了。当然还有其他缓存淘汰策略，比如不要按访问的时序来淘汰，而是按访问频率（LFU 策略）来淘汰等等，各有应用场景。本文讲解 LRU 算法策略，我会在 LFU 算法详解 中讲解 LFU 算法。

一、LRU 算法描述

力扣第 146 题「 LRU缓存机制」就是让你设计数据结构：

首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。

注意哦，get 和 put 方法必须都是 O(1) 的时间复杂度，我们举个具体例子来看看 LRU 算法怎么工作。

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)

cache.put(1, 1);
// cache = [(1, 1)]

cache.put(2, 2);
// cache = [(2, 2), (1, 1)]

cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1

cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头

cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据

cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

//缓存容量为2
LRUCache* cache = new LRUCache(2);

//cache可以理解成一个队列
//假设左边为队头，右边为队尾
//最近使用的在队头，久未使用的在队尾
//键值对(key, val)用圆括号表示

cache->put(1,1);
//cache = [(1, 1)]

cache->put(2,2);
//cache = [(2, 2), (1, 1)]

cache->get(1);      //返回1
//cache = [(1, 1), (2, 2)]
//解释：因为最近访问了键1，所以提前至队头
//返回键1对应的值1

cache->put(3,3);
//cache = [(3, 3), (1, 1)]
//解释：缓存容量已满，需要删除内容空出位置
//优先删除久未使用的数据，也就是队尾的数据
//然后把新的数据插入队头

cache->get(2);      //返回-1(未找到)
//cache = [(3, 3), (1, 1)]
//解释：cache中不存在键为2的数据

cache->put(1,4);    
//cache = [(1, 4), (3, 3)]
//解释：键1已存在，把原始值1覆盖为4
//不要忘记也要将键值对提前到队头

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 缓存容量为 2
cache = LRUCache(2)
# 你可以把 cache 理解成一个队列
# 假设左边是队头，右边是队尾
# 最近使用的排在队头，久未使用的排在队尾
# 圆括号表示键值对 (key, val)

cache.put(1, 1)
# cache = [(1, 1)]

cache.put(2, 2)
# cache = [(2, 2), (1, 1)]

cache.get(1)       # 返回 1
# cache = [(1, 1), (2, 2)]
# 解释：因为最近访问了键 1，所以提前至队头
# 返回键 1 对应的值 1

cache.put(3, 3)
# cache = [(3, 3), (1, 1)]
# 解释：缓存容量已满，需要删除内容空出位置
# 优先删除久未使用的数据，也就是队尾的数据
# 然后把新的数据插入队头

cache.get(2)       # 返回 -1 (未找到)
# cache = [(3, 3), (1, 1)]
# 解释：cache 中不存在键为 2 的数据

cache.put(1, 4)    
# cache = [(1, 4), (3, 3)]
# 解释：键 1 已存在，把原始值 1 覆盖为 4
# 不要忘了也要将键值对提前到队头

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

cache := Constructor(2)

cache.Put(1, 1)
// cache = [(1, 1)]

cache.Put(2, 2)
// cache = [(2, 2), (1, 1)]

cache.Get(1)
// 返回 1
// cache = [(1, 1), (2, 2)]
// 解释: 因为最近访问了键 1, 所以提前至队头.
// 返回键 1 对应的值 1

cache.Put(3, 3)
// cache = [(3, 3), (1, 1)]
// 解释: 缓存容量已满, 需要删除内容空出位置.
// 优先删除久未使用的数据, 也就是队尾的数据.
// 然后把新的数据插入队头.

cache.Get(2)
// 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释: cache 中不存在键为 2 的数据.

cache.Put(1, 4)
// cache = [(1, 4), (3, 3)]
// 解释: 键 1 已存在, 把原始值 1 覆盖为 4.
// 不要忘了也要将键值对提前到队头.

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var cache = new LRUCache(2);

	cache.put(1, 1);
	// cache = [(1, 1)]

	cache.put(2, 2);
	// cache = [(2, 2), (1, 1)]

	cache.get(1);  // 返回 1
	// cache = [(1, 1), (2, 2)]
	// 解释：因为最近访问了键 1，所以提前至队头
	// 返回键 1 对应的值 1

	cache.put(3, 3);
	// cache = [(3, 3), (1, 1)]
	// 解释：缓存容量已满，需要删除内容空出位置
	// 优先删除久未使用的数据，也就是队尾的数据
	// 然后把新的数据插入队头

	cache.get(2);  // 返回 -1 (未找到)
	// cache = [(3, 3), (1, 1)]
	// 解释：cache 中不存在键为 2 的数据

	cache.put(1, 4);    
	// cache = [(1, 4), (3, 3)]
	// 解释：键 1 已存在，把原始值 1 覆盖为 4
	// 不要忘了也要将键值对提前到队头

二、LRU 算法设计

分析上面的操作过程，要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：

1、显然 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。

2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val；

3、每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

借助这个结构，我们来逐一分析上面的 3 个条件：

1、如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。

2、对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。

3、链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

也许读者会问，为什么要是双向链表，单链表行不行？另外，既然哈希表中已经存了 key，为什么链表中还要存 key 和 val 呢，只存 val 不就行了？

想的时候都是问题，只有做的时候才有答案。这样设计的原因，必须等我们亲自实现 LRU 算法之后才能理解，所以我们开始看代码吧～

三、代码实现

很多编程语言都有内置的哈希链表或者类似 LRU 功能的库函数，但是为了帮大家理解算法的细节，我们先自己造轮子实现一遍 LRU 算法，然后再使用 Java 内置的 LinkedHashMap 来实现一遍。

首先，我们把双链表的节点类写出来，为了简化，key 和 val 都认为是 int 类型：

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Node {
    public:
        int key, val;
        Node* next;
        Node* prev;
        Node(int k, int v){
            this->key = k;
            this->val = v;
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Node:
    def __init__(self, k: int, v: int):
        self.key = k
        self.val = v
        self.next = None
        self.prev = None

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type Node struct {
    key, val int
    next, prev *Node
}

func NewNode(k, v int) *Node {
    return &Node{key: k, val: v}
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var Node = function(k, v) {
  this.key = k;
  this.val = v;
  this.next = null;
  this.prev = null;
};

然后依靠我们的 Node 类型构建一个双链表，实现几个 LRU 算法必须的 API：

class DoubleList {  
    // 头尾虚节点
    private Node head, tail;  
    // 链表元素数
    private int size;
    
    public DoubleList() {
        // 初始化双向链表的数据
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // 在链表尾部添加节点 x，时间 O(1)
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }
    
    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public Node removeFirst() {
        if (head.next == tail)
            return null;
        Node first = head.next;
        remove(first);
        return first;
    }

    // 返回链表长度，时间 O(1)
    public int size() { return size; }

}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class DoubleList {
private:
    // 头尾虚节点
    Node* head;
    Node* tail;
    // 链表元素数
    int size;

public:
    DoubleList() {
        // 初始化双向链表的数据
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
        size = 0;
    }

    // 在链表尾部添加节点 x，时间 O(1)
    void addLast(Node* x) {
        x->prev = tail->prev;
        x->next = tail;
        tail->prev->next = x;
        tail->prev = x;
        size++;
    }

    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
        size--;
    }

    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    Node* removeFirst() {
        if (head->next == tail)
            return nullptr;
        Node* first = head->next;
        remove(first);
        return first;
    }

    // 返回链表长度，时间 O(1)
    int getSize() { return size; }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class DoubleList:
    # 头尾虚节点
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    
    # 在链表尾部添加节点 x，时间 O(1)
    def addLast(self, x: Node):
        x.prev = self.tail.prev
        x.next = self.tail
        self.tail.prev.next = x
        self.tail.prev = x
        self.size += 1
    
    # 删除链表中的 x 节点（x 一定存在）
    # 由于是双链表且给的是目标 Node 节点，时间 O(1)
    def remove(self, x: Node):
        x.prev.next = x.next
        x.next.prev = x.prev
        self.size -= 1
    
    # 删除链表中第一个节点，并返回该节点，时间 O(1)
    def removeFirst(self) -> Node:
        if self.head.next == self.tail:
            return None
        first = self.head.next
        self.remove(first)
        return first
    
    # 返回链表长度，时间 O(1)
    def size(self) -> int:
        return self.size

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type DoubleList struct {
    head, tail *Node
    size       int
}

func NewDoubleList() *DoubleList {
    // 初始化双向链表的数据
    head := &Node{key: 0, val: 0}
    tail := &Node{key: 0, val: 0}
    head.next, tail.prev = tail, head
    return &DoubleList{head: head, tail: tail, size: 0}
}

// 在链表尾部添加节点 x，时间 O(1)
func (this *DoubleList) AddLast(x *Node) {
    x.prev = this.tail.prev
    x.next = this.tail
    this.tail.prev.next = x
    this.tail.prev = x
    this.size++
}

// 删除链表中的 x 节点（x 一定存在）
// 由于是双链表且给的是目标 Node 节点，时间 O(1)
func (this *DoubleList) Remove(x *Node) {
    x.prev.next = x.next
    x.next.prev = x.prev
    this.size--
}

// 删除链表中第一个节点，并返回该节点，时间 O(1)
func (this *DoubleList) RemoveFirst() *Node {
    if this.head.next == this.tail {
        return nil
    }
    first := this.head.next
    this.Remove(first)
    return first
}

// 返回链表长度，时间 O(1)
func (this *DoubleList) Size() int {
    return this.size
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var DoubleList = function() {
    // 头尾虚节点
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    // 链表元素数
    this.size = 0;

    // 初始化双向链表的数据
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

// 在链表尾部添加节点 x，时间 O(1)
DoubleList.prototype.addLast = function(x) {
    x.prev = this.tail.prev;
    x.next = this.tail;
    this.tail.prev.next = x;
    this.tail.prev = x;
    this.size++;
};

// 删除链表中的 x 节点（x 一定存在）
// 由于是双链表且给的是目标 Node 节点，时间 O(1)
DoubleList.prototype.remove = function(x) {
    x.prev.next = x.next;
    x.next.prev = x.prev;
    this.size--;
};

// 删除链表中第一个节点，并返回该节点，时间 O(1)
DoubleList.prototype.removeFirst = function() {
    if (this.head.next == this.tail)
        return null;
    var first = this.head.next;
    this.remove(first);
    return first;
};

// 返回链表长度，时间 O(1)
DoubleList.prototype.size = function() {
    return this.size;
};

到这里就能回答刚才「为什么必须要用双向链表」的问题了，因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。

注意我们实现的双链表 API 只能从尾部插入，也就是说靠尾部的数据是最近使用的，靠头部的数据是最久未使用的。

有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可，先搭出代码框架：

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

#include <unordered_map>

class LRUCache {
    // key -> Node(key, val)
    std::unordered_map<int, Node*> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    DoubleList cache;
    // 最大容量
    int cap;
    
    public:
        LRUCache(int capacity) {
            cap = capacity;
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache:
    # key -> Node(key, val)
    # 创建一个哈希表将 Node 节点的 key 映射至其本身
    map: dict[int, Node]

    # Node(k1, v1) <-> Node(k2, v2)...
    # 双向链表用来实现 LRU 缓存淘汰机制
    cache: DoubleList

    # 最大容量
    # 缓存最大容量，超过此容量则淘汰
    cap: int
    
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.cache = DoubleList()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type LRUCache struct {
    // key -> Node(key, val)
    mapCache map[int]*Node
    // Node(k1, v1) <-> Node(k2, v2)...
    cache *DoubleList
    // 最大容量
    cap int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap: capacity,
        mapCache: make(map[int]*Node),
        cache: &DoubleList{},
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var LRUCache = function(capacity) {
    // key -> Node(key, val)
    this.map = new Map();
    // Node(k1, v1) <-> Node(k2, v2)...
    this.cache = new DoubleList();
    // 最大容量
    this.cap = capacity;
}

先不慌去实现 LRU 算法的 get 和 put 方法。由于我们要同时维护一个双链表 cache 和一个哈希表 map，很容易漏掉一些操作，比如说删除某个 key 时，在 cache 中删除了对应的 Node，但是却忘记在 map 中删除 key。

解决这种问题的有效方法是：在这两种数据结构之上提供一层抽象 API。

说的有点玄幻，实际上很简单，就是尽量让 LRU 的主方法 get 和 put 避免直接操作 map 和 cache 的细节。我们可以先实现下面几个函数：

class LRUCache {
    // 为了节约篇幅，省略上文给出的代码部分...

    /* 将某个 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);
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache {
private:
    /* 节点结构体 */
    struct Node {
        int key, val;
        Node* next;
        Node(int _key, int _val) : key(_key), val(_val), next(nullptr) {}
    };
    /* 哈希表存储节点指针 */
    unordered_map<int, Node*> map;
    /* 虚拟头节点 */
    Node* head;
    /* 虚拟尾节点 */
    Node* tail;
    /* 缓存容量 */
    int capacity;

public:
    LRUCache(int _capacity) : capacity(_capacity) {
        /* 初始化虚拟头尾节点 */
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->next = nullptr;
    }

    int get(int key) {
        if (!map.count(key)) {
            return -1;
        }
        /* 通过哈希表定位到节点 */
        Node* node = map[key];
        /* 将节点移动到链表尾部 */
        moveToEnd(node);
        return node->val;
    }

    void put(int key, int value) {
        if (map.count(key)) {
            /* 如果已存在，修改对应节点的值，并移动到链表尾部 */
            Node* node = map[key];
            node->val = value;
            moveToEnd(node);
            return;
        }
        if (map.size() == capacity) {
            /* 如果超出容量，删除链表头部节点 */
            deleteHead();
        }
        /* 添加新的节点到链表尾部，并在哈希表中添加映射 */
        addNode(new Node(key, value));
    }

private:
    /* 将节点移动到链表尾部 */
    void moveToEnd(Node* node) {
        removeNode(node);
        addNode(node);
    }

    /* 删除链表头部节点 */
    void deleteHead() {
        Node* node = head->next;
        removeNode(node);
        map.erase(node->key);
        delete node;
    }

    /* 添加节点到链表尾部 */
    void addNode(Node* node) {
        tail->next = node;
        node->next = nullptr;
        map[node->key] = node;
        tail = node;
    }

    /* 删除链表中的节点 */
    void removeNode(Node* node) {
        Node* prev = head;
        while (prev->next != node) {
            prev = prev->next;
        }
        prev->next = node->next;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache:
    def makeRecently(self, key: int):
        # 将某个 key 提升为最近使用的
        x = self.map.get(key)
        # 先从链表中删除这个节点
        self.cache.remove(x)
        # 重新插到队尾
        self.cache.append(x)

    def addRecently(self, key: int, val: int):
        # 添加最近使用的元素
        x = Node(key, val)
        # 链表尾部就是最近使用的元素
        self.cache.append(x)
        # 别忘了在 map 中添加 key 的映射
        self.map[key] = x

    def deleteKey(self, key: int):
        # 删除某一个 key
        x = self.map.get(key)
        # 从链表中删除
        self.cache.remove(x)
        # 从 map 中删除
        self.map.pop(key)

    def removeLeastRecently(self):
        # 删除最久未使用的元素
        # 链表头部的第一个元素就是最久未使用的
        deletedNode = self.cache.pop(0)
        # 同时别忘了从 map 中删除它的 key
        deletedKey = deletedNode.key
        self.map.pop(deletedKey)

    def __init__(self, capacity: int):
        self.cache = []
        self.map = {}
        self.capacity = capacity

    def get(self, key: int) -> int:
        # 读操作
        if key not in self.map:
            return -1
        self.makeRecently(key)
        return self.map.get(key).val

    def put(self, key: int, value: int) -> None:
        # 写操作
        if key in self.map:
            self.map.get(key).val = value
            self.makeRecently(key)
            return
        if len(self.cache) == self.capacity:
            self.removeLeastRecently()
        self.addRecently(key, value)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type LRUCache struct {
    // 为了节约篇幅，省略上文给出的代码部分...
}

// 将某个 key 提升为最近使用的
func (this *LRUCache) makeRecently(key int) {
    x := this.map[key]
    // 先从链表中删除这个节点
    this.cache.Remove(x)
    // 重新插到队尾
    this.cache.PushBack(x)
}

// 添加最近使用的元素
func (this *LRUCache) addRecently(key int, val int) {
    x := &Node{key, val, nil, nil}
    // 链表尾部就是最近使用的元素
    this.cache.PushBack(x)
    // 别忘了在 map 中添加 key 的映射
    this.map[key] = x
}

// 删除某一个 key
func (this *LRUCache) deleteKey(key int) {
    x := this.map[key]
    // 从链表中删除
    this.cache.Remove(x)
    // 从 map 中删除
    delete(this.map, key)
}

// 删除最久未使用的元素
func (this *LRUCache) removeLeastRecently() {
    // 链表头部的第一个元素就是最久未使用的
    deletedNode := this.cache.Remove(this.cache.Front())
    // 同时别忘了从 map 中删除它的 key
    deletedKey := deletedNode.(*Node).key
    delete(this.map, deletedKey)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var LRUCache = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

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

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

    /* 删除某一个 key */
    this.deleteKey = function(key) {
        var x = map.get(key);
        // 从链表中删除
        cache.remove(x);
        // 从 map 中删除
        map.remove(key);
    }

    /* 删除最久未使用的元素 */
    this.removeLeastRecently = function() {
        // 链表头部的第一个元素就是最久未使用的
        var deletedNode = cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        var deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }
}

这里就能回答之前的问答题「为什么要在链表中同时存储 key 和 val，而不是只存储 val」，注意 removeLeastRecently 函数中，我们需要用 deletedNode 得到 deletedKey。

也就是说，当缓存容量已满，我们不仅仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 得到。如果 Node 结构中只存储 val，那么我们就无法得知 key 是什么，就无法删除 map 中的键，造成错误。

上述方法就是简单的操作封装，调用这些函数可以避免直接操作 cache 链表和 map 哈希表，下面我先来实现 LRU 算法的 get 方法：

class LRUCache {
    // 为了节约篇幅，省略上文给出的代码部分...

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache {
    // 为了节约篇幅，省略上文给出的代码部分...

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache:
    # 为了节约篇幅，省略上文给出的代码部分...

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        # 将该数据提升为最近使用的
        self.makeRecently(key)
        return self.map[key].val

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type LRUCache struct {
    // 省略上文的代码部分...
}

func (this *LRUCache) get(key int) int {
    if _, ok := this.map[key]; !ok {
        return -1
    }
    // 将该数据提升为最近使用的
    this.makeRecently(key)
    return this.map[key].val
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var LRUCache = function() {
    // 省略上文给出的代码部分...
};

LRUCache.prototype.get = function(key) {
    if (!map.has(key)) {
        return -1;
    }
    // 将该数据提升为最近使用的
    makeRecently(key);
    return map.get(key).val;
};

put 方法稍微复杂一些，我们先来画个图搞清楚它的逻辑：

这样我们可以轻松写出 put 方法的代码：

class LRUCache {
    // 为了节约篇幅，省略上文给出的代码部分...
    
    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);
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache {
    // 为了节约篇幅，省略上文给出的代码部分...
    
public:
    void put(int key, int val) {
        if (map.find(key) != map.end()) {
            // 删除旧的数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }
        
        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class LRUCache:

    def put(self, key: int, val: int) -> None:
        if key in self.map:
            # 删除旧的数据
            self.deleteKey(key)
            # 新插入的数据为最近使用的数据
            self.addRecently(key, val)
            return

        if self.cap == len(self.cache):
            # 删除最久未使用的元素
            self.removeLeastRecently()
        # 添加为最近使用的元素
        self.addRecently(key, val)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type LRUCache struct {
    // 省略上文给出的代码部分...
}

func (this *LRUCache) put(key int, val int) {
    if _, ok := this.m[key]; ok {
        // 删除旧的数据
        this.deleteKey(key)
        // 新插入的数据为最近使用的数据
        this.addRecently(key, val)
        return
    }

    if this.cap == len(this.cache) {
        // 删除最久未使用的元素
        this.removeLeastRecently()
    }
    // 添加为最近使用的元素
    this.addRecently(key, val)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var LRUCache = function() {
  // 为了节约篇幅，省略上文给出的代码部分...

  this.put = function(key, val) {
    if (map.has(key)) {
      // 删除旧的数据
      deleteKey(key);
      // 新插入的数据为最近使用的数据
      addRecently(key, val);
      return;
    }

    if (cap === cache.size) {
      // 删除最久未使用的元素
      removeLeastRecently();
    }
    // 添加为最近使用的元素
    addRecently(key, val);
  };
};

至此，你应该已经完全掌握 LRU 算法的原理和实现了，我们最后用 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) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

#include<unordered_map>
using namespace std;

class LRUCache {
    int cap;
    unordered_map<int, int> cache;
public:
    LRUCache(int capacity) {
        this->cap = capacity;
    }
    
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) 
            return -1;
        // 将 key 变为最近使用
        makeRecently(key);
        return it->second;
    }
    
    void put(int key, int val) {
        if (cache.count(key)) {
            // 修改 key 的值
            cache[key] = val;
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        
        if (cache.size() >= this->cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.begin()->first;
            cache.erase(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache[key] = val;
    }
    
    void makeRecently(int key) {
        int val = cache[key];
        // 删除 key，重新插入到队尾
        cache.erase(key);
        cache[key] = val;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        # 缓存最大容量
        self.cap = capacity
        # 记录key-value的顺序
        self.cache = OrderedDict()
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            # 返回-1表示查找失败
            return -1
        # 将当前访问的节点移到双向链表尾部
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 修改key对应的value值
            self.cache[key] = value
            # 将当前访问的节点移到双向链表尾部
            self.cache.move_to_end(key)
            return
        
        if len(self.cache) >= self.cap:
            # 双向链表头部为最久没有被访问的节点，删除该节点
            self.cache.popitem(last=False)

        # 添加新节点到链表尾部
        self.cache[key] = value

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

import "container/list"

type LRUCache struct {
    cap  int                    // 缓存容量
    cache map[int]*list.Element // 双向链表节点 指向的map
    list *list.List             // 双向链表
}

type keyVal struct {
    key, val int // 节点的Key和Value
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap:   capacity,                            // 初始化缓存容量
        cache: make(map[int]*list.Element),          // 初始化map映射
        list:  list.New(),                           // 初始化双向链表
    }
}

func (this *LRUCache) Get(key int) int {
    if elem, ok := this.cache[key]; ok {             // 如果map里有key对应的双向链表节点
        this.list.MoveToFront(elem)                  // 把节点移动到链表头
        return elem.Value.(*keyVal).val              // 返回节点的value值
    }
    return -1                                        // 没有找到的情况下，返回-1
}

func (this *LRUCache) Put(key int, value int) {
    if elem, ok := this.cache[key]; ok {             // 如果map里有key对应的双向链表节点
        this.list.MoveToFront(elem)                  // 把节点移动到链表头
        elem.Value.(*keyVal).val = value             // 更新节点的value值
        return
    }
    if this.list.Len() >= this.cap {                 // 如果超过了缓存容量
        tail := this.list.Back()                     // 获取链表的尾节点
        k := tail.Value.(*keyVal).key                // 获取节点的key
        this.list.Remove(tail)                       // 从链表中删除尾节点
        delete(this.cache, k)                        // 从map中删除尾节点
    }
    elem := this.list.PushFront(&keyVal{key, value}) // 将节点添加到链表头
    this.cache[key] = elem                           // 将节点映射到map中
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var LRUCache = function(capacity) {
    this.cap = capacity;
    this.cache = new Map();
};

LRUCache.prototype.get = function(key) {
    if (!this.cache.has(key)) {
        return -1;
    }
    // 将 key 变为最近使用
    this.makeRecently(key);
    return this.cache.get(key);
};

LRUCache.prototype.put = function(key, val) {
    if (this.cache.has(key)) {
        // 修改 key 的值
        this.cache.set(key, val);
        // 将 key 变为最近使用
        this.makeRecently(key);
        return;
    }

    if (this.cache.size >= this.cap) {
        // 链表头部就是最久未使用的 key
        const oldestKey = this.cache.keys().next().value;
        this.cache.delete(oldestKey);
    }
    // 将新的 key 添加链表尾部
    this.cache.set(key, val);
};

LRUCache.prototype.makeRecently = function(key) {
    const val = this.cache.get(key);
    // 删除 key，重新插入到队尾
    this.cache.delete(key);
    this.cache.set(key, val);
};

至此，LRU 算法就没有什么神秘的了。更多数据结构设计相关的题目参见 数据结构设计经典习题。

接下来可阅读：

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode 力扣
- 剑指 Offer II 031. 最近最少使用缓存
引用本文的文章

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释