第 5 关 | 算法的备胎 hash 和 找靠山的队列: 3.黄金挑战——LRU 的设计与实现-灵析社区

时光小少年

1. 理解 LRU 的原理

缓存是应用软件的必备功能之一，在操作系统，Java里的Spring、mybatis、redis、mysql等软件中都有自己的内部缓存模块，而缓存是如何实现的呢？在操作系统教科书里我们知道常用的有FIFO、LRU和LFU三种基本的方式。FIFO也就是队列方式不能很好利用程序局部性特征，缓存效果比较差，一般使用LRU（最近最少使用）和LFU(最不经常使用淘汰算法)比较多一些。LRU是淘汰最长时间没有被使用的页面，而LFU是淘汰一段时间内，使用次数最少的页面。

从实现上LRU是相对容易的，而LFU比较复杂，我们本章重点研究一下LRU的问题，这也是一道高频题目。LeetCode146：设计一个LRU缓存，这个题也经常见到，在牛客也是长期排名前三

先看题意，LeetCode 146：运用你所掌握的数据结构，设计和实现一个 LRU （最近最少使用）缓存机制。

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["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);    // 返回 1
lRUCache.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);    // 返回 3
lRUCache.get(4);    // 返回 4

关于是 LRU ，简历来说就是当内存满了，不得不淘汰某些数据（通常是容量满了），选择最久没使用的数据进行淘汰。

这里做了一个简化，就是题目让我们实现一个容器固定的 LRUCache,如果插入数据的时候，发现容器已经满了，那先按照 LRU 规则淘汰一个数据，然后将新数据插入，其中【插入】和【查询】都算作一个操作。

百度百科上有一个例子：baike.baidu.com/item/LRU/12…

最近最少使用算法（LRU ）是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。

该算法的思路是，发生缺页中断，选择未使用时间最长的页面置换出去。假设内存只能容纳 3 页大小，按照 7 0 1 2 0 3 0 4 的次序访问页，假设内存按照占栈的方式来描述访问时间，在上面的是最近访问的，在下面的是最远时间访问的，LRU 就是这样工作的：

如果再有其他元素依此类推。

如果告诉你上述原理，要如何实现呢？定义一个数组，根据上面的规则写吗？

那样的话，估计一个小时也写不出来，即使写出来，也非常容易超时，那要怎么做呢？目前公认最好的方式就是 Hash + 双链表。

2. 哈希 + 双链表实现 LRU

目前公认最合理的方式是 Hash + 双向链表，想不到吧，接下来我们来看看要怎么做。

• Hash 的作用：用来做到访问 O(1) 的元素，哈希表就是普通的哈希映射（HashMap）通过缓存数据的键映射到其在双链表中的位置，Hash 里面的数据就是 key——value结构。value 就是我们自己封装的 node，key 则是键值，也就是在 Hash 的地址。
• 双向链表用来实现根据访问情况对元素进行排序。双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久没使用的.

这样一来，我们要确认元素的位置直接访问哈希表就可以了，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，这样就可以实现在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

• 对于 get 操作，首先判断 key 是否存在：
• 如果 key 不存在，返回 -1； 如果 key 存在，这 key 对应的节点就是最近正在被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并且将其移动到双向链表中的头部，最后返回该节点。
• 对于 put 操作，首选判断 key 是否存在：
• 如果 key 存在，则先通过 key 定位 node ，然后将对应节点的值更新为 value，并且将该节点移动到双链表的头部。 如果 key 不存在，则使用 key 和 value 创建一个新节点，在双向链表的头部添加该节点，并且将 key 和 value 的节点添加进哈希表，然后判断双向链表的节点数字是否超出容量，如果超出容量，那就删除双向链表的尾部节点，并且删除哈希表中对应的项；

上述各种操作完成之后，访问哈希表的时间复杂度为 O(1),在双向链表的头部添加节点，在双向链表的尾部删除节点的复杂度也是 O（1）。而将一个节点移动到双向链表的头部，可以分为【删除该节点】和【在双向链表的头部添加节点】两步操作，都可以在 O（1）的时间内完成。

同时为了方便操作，在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻节点是否存在。

我们以容量为 3 的例子，首先缓存了 1，此时结构如图 a 所示，之后再缓存 2 和 3，结构如 b 所示。

之后 4 再进入，此时容量已经不够了，只能将最远未使用的 1 删除，然后将 4 插入到链表头部。此时就变成了上图 c 的样子。

接下来假如又访问了一次 2，会怎么样呢？此时会将 2 移动到链表的首部，也就是下图 d 的样子。

之后假如又要缓存 5 呢？此时将 tail 指向的 3 删除就好了，然后将 5 插入到链表头部，也就是图 e 的样子。

上面的方案要实现是非常容易的，我们注意到链表主要执行几个操作：

1. 假如容量没满，则将新元素直接插入到链表头就行了。
2. 如果容量够了，新的元素到来，则将 tail 指向的表尾元素删除就可以了。
3. 假如要访问已经存在的元素，则此时将该节点先从链表删除，再插入到表头就可以了。

再看 hash 的操作：

1. hash 没有容量的限制，凡是被访问的元素在 hash 中都会有标记，key 就是我们的查询条件，而 value 就是链表的结点的引用，可以不同访问链表直接定位到某个节点，然后就可以执行我们再上一节提到的方法来删除对应的节点。
2. 这里的双向链表的删除好理解，那 HashMap 设计如何删除的？其实就是将 node 变为null。这样get（key）的时候返回的就是 null ，这样就可以实现删除功能了。
3. 上述各项操作中，访问哈希表的时间复杂度为 O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也是 O（1）。而将一个节点移到双向链表的头部，可以分为【删除节点】和【在双向链表头部添加节点】两步操作，都可以在 O（1）时间内完成。

package com.qinyao.leetcode.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName LRUCache
 * @Description
 * @Version 1.0.0
 * @Author LinQi
 * @Date 2023/09/12
 */
public class LruCache {

    private class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {

        }

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.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;
        }
        // 如果 key 存在，先通过 哈希表定位，再移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        // 如果缓存为空，则创建元素
        if (node == null) {
            // 如果 key 不存在，创建一个新节点
            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 DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

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

    public static void main(String[] args) {
        LruCache lruCache = new LruCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));

    }
}

点赞 评论 收藏 目录

阅读量：1171

点赞量：0

收藏量:0