算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现

这篇具有很好参考价值的文章主要介绍了算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言


提示:我曾如此渴望命运的波澜,到最后才发现:人生最曼妙的风景,竟是内心的淡定从容。 我们层如此盼望世界的认可,到最后才知道:世界是自己,与他人毫无关系。 --杨绛

LRU 是非常经典的问题,而且在常年的算法中也是热门,但是他是存在技巧的,我们这就来一起看看吧。

1. LRU的含义

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

从实现上来说LRU相对更容易一些,而LFU比较麻烦,我们这里重点研究一下LRU的问题,当然这也是一道高频题目,让我们设计一个LRU缓存,该题可以排到算法前3是没有问题的。

参考题目介绍:146. LRU 缓存 - 力扣(LeetCode)

在这里插入图片描述算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现,算法集训营,双向链表,散列表,LRU,算法笔记,缓存机制,Java,数据结构
算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现,算法集训营,双向链表,散列表,LRU,算法笔记,缓存机制,Java,数据结构
百度百科:

LRU(最近最少使用)缓存:LRU_百度百科 (baidu.com)

首先关于什么是LRU,最简单的说法是当内存空间满了,不得不淘汰某些数据时(通常时容量已满),先择最久未呗使用的数据进行淘汰。

这里时做了简化的,题目是让我们实现一个容器固定LRUCache。如果插入数据时,发现容器已满时,则先按照LRU规则进行淘汰数据,再插入新的数据,这种【插入】和【查询】都算一次“使用”。

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

该算法的思路是:

发生缺页中断时,选择未使用时间最长的页面置换出去。假设内存只能容纳3个页大小,按照7 0 1 2 0 3 0 4 的次序访问页面。假设内存按照栈的方式类描述访问时间,在上面时最近访问的,在下面的最远时间访问的,LRU就是这样工作的:
算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现,算法集训营,双向链表,散列表,LRU,算法笔记,缓存机制,Java,数据结构
尝试了工作流程,那么我们需要怎么来实现它呢,有什么好的思路呢?定义一个数组,然后根据上面的写上一些规则吗?我估计这个要实现起来会非常难,即使写出来了,也非常复杂,超时等。那我们应该怎么做,这里告诉你标准的答案:Hash+双向链表。

2. Hash+双向链表实现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和value创建一个新的节点,在双向链表的头部添加该节点,并将key和该节点添加进哈希表中。然后判断双向链表的节点书是否超出容量,如果超出容量,则删除双向链表的尾节点,并删除哈希表中的对应项
    • 如果key存在,则于get操作类似,先通过哈希定位,再将对应的节点更新为value,并将该节点移到双向链表的头部。

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

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

说了这么多,还是看图更方便一些:

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

我们先看这个容量为3 的例子,首先缓存了1,此时结构如图所示,之后缓存2,3结构如b所示:

算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现,算法集训营,双向链表,散列表,LRU,算法笔记,缓存机制,Java,数据结构
之后4再进入,此时容量已经不够了,只能再最远未使用的元素1删掉,然后将4插入到链表头部,如此就变成了图c的样子。

如果接下类又访问了一次2,会怎么样呢?我们会将2移动到链表的首位,也就是下面d的样子。
算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现,算法集训营,双向链表,散列表,LRU,算法笔记,缓存机制,Java,数据结构
之后存储5呢?此时将tail指向的3删除,然后将5插入到链表的头部,也就是如上图的e的样子。

上面的方案图示很容易实现,但是这里我们强调几个点哈🥰:

  1. 假设容量没有满,可以直接将元素插入到链表头部就可以
  2. 如果容量满了,就要采取策略,新的元素到来,则tail指向的表尾元素删除就行
  3. 假设要访问的元素已经存在,则将此元素先从链表中删除,再插入到表头就行了。

我们再看一些Hash的操作:

  1. Hash没有容量的限制,凡是被访问的元素都会再Hash中有标记,key就是我们要查询的条件,而value就是链表的节点的引用,可以不访问链表直接定位到某个元素节点,然后执行我们上面提到的方法来删除对应的元素节点。
  2. 这里的双向链表的删除好理解,那HashMap中的删除要如何处理呢?其实就是将node变为null。这样get(key)的时候就会返回null,也就实现了删除的功能。

总结:

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

代码展示看效果
难度:⭐⭐⭐⭐⭐

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

public class LRUCache {

    // 写一个双向链表的结构
    class DLinkedNode {
        int key;
        int value;
        // 前后引用
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {

        }

        public DLinkedNode(int _key, int _value) {
            this.key = _key;
            this.value = _value;
        }
    }

    // 需要一个HashMap
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    // 需要一个size
    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 {
            // 如果key存在  先通过hash定位,再修改value,并且将它移动到头部
            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;
    }


    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}

总结

提示:理解双向链表;了解LRU缓存机制;Hash+双向链表的思考文章来源地址https://www.toymoban.com/news/detail-705250.html

到了这里,关于算法通过村第五关-队列和Hash黄金笔记|LRU的设计与实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【sqli靶场】第四关和第五关通关思路

    目录 前言 一、sqli靶场第四关 1.1 判断注入类型 1.2 观察报错   1.3 判断数据表中的列数 1.4 使用union联合查询 1.5 使用group_concat()函数 二、sqli靶场第五关 2.1 判断注入类型 2.2 使用extractvalue函数报错 2.3 爆出数据库中的表名 2.4 爆出users表中的列名 2.5 爆出users表中的数据 🌈嗨

    2024年01月24日
    浏览(30)
  • 编程导航算法村第九关 | 二分查找

    LeetCode852.这个题的要求有点啰嗦,核心意思就是在数组中的某位位置i开始,从0到i是递增的,从i+1 到数组最后是递减的,让你找到这个最高点。 详细要求是:符合下列属性的数组 arr 称为山脉数组 :arr.length = 3存在 i(0 i arr.length - 1)使得: ● arr[0] arr[1] … arr[i-1] arr[i] ●

    2024年02月14日
    浏览(35)
  • 算法村第二关(1)——手写链表反转

    题目:Leetcode-206. 反转链表 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表 对于链表反转的问题,想起来其实非常简单。 就是从前往后,将节点一个一个采用头插法的做成一个新链表嘛,这样新链表就是旧链表的反转链表啦! 那既然这么简单,为什么还要学

    2024年02月14日
    浏览(40)
  • 算法通关村第十五关:青铜-用4KB内存寻找重复元素

    位运算在查找元素中的妙用 题目要求: 给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。 思路分析 本题是非常典型的海量数据处理的问题,使用的是位运算结构 内存大小关系

    2024年02月10日
    浏览(37)
  • 编程导航算法村第八关 | 树的深度优先遍历

    LeetCode100:给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 思路: 两课树同时进行前序遍历,比较节点是否相等 LeetCode101 给定一个二叉树,检查它是否是镜像对称的。 思路

    2024年02月14日
    浏览(36)
  • 编程导航算法村第七关 |二叉树的遍历

    先迭代到树的最底层,左左端的元素,然后弹出栈,访问他的右节点 后续遍历相当于在前序遍历的基础上,先访问右节点再访问左节点,最后翻转

    2024年02月14日
    浏览(37)
  • C++标准库 -- 泛型算法 (Primer C++ 第五版 · 阅读笔记)

    顺序容器只定义了很少的操作:在多数情况下,我们可以添加和删除元素访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迭代器。 我们可以想象用户可能还希望做其他很多有用的操作:查找特定元素、替换或删除一个特定值、重排元素顺序等。 标准库

    2023年04月21日
    浏览(43)
  • 逢试必考的二分查找(算法村第九关青铜挑战)

    除法在计算机中效率很低,一般改用 x ,意思是二进制数的每个位右移 x 位。从十进制的角度看, x 是以 2 为底的指数,这个指数就是除数。 在 Java 中,位运算符 的优先级低于加法运算符 + ,所以需要使用括号来保证正确的优先级 迭代实现

    2024年01月22日
    浏览(39)
  • 算法通关村第十五关——从10亿数字中寻找最小的100万个数字

    本题有三种常用的方法,一种是先排序所有元素,然后取出前100万个数,该方法的时间复杂度为O(nlogn)。很明显对于10亿级别的数据,这么做时间和空间代价太高。 第二种方式是采用选择排序的方式,首先遍历10亿个数字找最小,然后再遍历一次找第二小,然后再一次找第三小

    2024年02月11日
    浏览(45)
  • [Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素

    在 海量数据 中,此时普通的数组、链表、Hash、树等等结构有无效了 ,因为内存空间放不下了。而常规的递归、排序,回溯、贪心和动态规划等思想也无效了,因为执行都会超时,必须另外想办法。这类问题该如何下手呢?这里介绍三种非常典型的思路: 使用位存储 ,使用

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包