手撕LRU 最近最少使用缓存淘汰策略 + LinkedHashMap

LRU 最近最少使用缓存淘汰策略

  • 1 LRU 算法就是一种缓存淘汰策略
  • 2 手撕LRU
  • 3 LinkedHashMap 常见面试题

1 LRU 算法就是一种缓存淘汰策略

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

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

ps:数据库采用改进的LRU 为了解决select *这种只使用一次,但是会把热数据:真正频率较高的挤到后面的问题。

2 手撕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

⭐️要点👿

  1. 定义一个双向链表:链表中的每个Node 包括:key value两个属性双向链表+dummy节点+形成一个环结构
    在这里插入图片描述
public static class Node{  //定义一个双向链表静态内部类 每个节点有key+value,还有prev指针 next指针(实现双向)int key;int value;Node prev;Node next;Node(int key, int value){ // 构造器this.key = key;this.value = value;}}
  1. 定义一个Hashmap:<key, Node>,为了方便根据 key 查找到对应的Node
    在这里插入图片描述
    capacity: 这是LRUCache类中存储缓存容量的变量,应该在对象创建后不可更改,因此使用 private final 来确保其值在对象创建后不会被修改。
    dummy 节点: 哨兵节点是双向链表中的一个特殊节点,它不存储任何实际的数据,仅用于简化链表操作。因为哨兵节点在整个对象生命周期中不会改变,所以将其声明为 private final
    myhashmap哈希表: 这是LRUCache类中存储键值对的哈希表,也应该在对象创建后不可更改。使用 private final 可以确保在对象创建后,哈希表的引用不会指向其他对象。
    总的来说,使用 private final 可以增强代码的安全性和稳定性,防止意外的修改或赋值操作,确保这些重要的成员变量在对象创建后保持不变。
private final int capacity; // 存储上限
private final Node dummy = new Node(0,0); // 新建一个dummy节点
private final HashMap<Integer, Node> myhashmap = new HashMap<>(); // 声明一个hashmap用于存储key-Node

  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
    🔴 先去Hashmap中寻找有无存在key 【调用getNode(key)】
    a. 若有则返回对应的Node,再返回Node.value 。与此同时,由于操作了该节点,因此将该节点移动到链表头部。
    b. 若无则返回-1。

  • void put(int key, int value)
    - 如果关键字 key 已经存在,则变更其数据值 value ;
    - 如果不存在,则向缓存中插入该组 key-value 。
    - 如果插入操作导致关键字数量超过 capacity,则应该 逐出 最久未使用的关键字
    🔴先去Hashmap中寻找有无存在key 【调用getNode(key)】
    a. 若有则返回对应的Node,修改Node.value属性,即可实现更改值的目的。与此同时,由于操作了该节点,因此将该节点移动到链表头部。
    b. 如果没有,则新建一个Node节点包含key-Node,并将这个新建的节点放进链表头部。与此同时,在Hashmap中也添加这个<key,Node>

// 最近最少使用 用于页面置换算法,淘汰最近最少使用的页面
class LRUCache {public static class Node{  //定义一个双向链表静态内部类 每个节点有key+value,还有prev指针 next指针(实现双向)int key;int value;Node prev;Node next;Node(int key, int value){ // 构造器this.key = key;this.value = value;}}private final int capacity; // 存储上限private final Node dummy = new Node(0,0); // 新建一个dummy节点private final HashMap<Integer, Node> myhashmap = new HashMap<>(); // 声明一个hashmap用于存储key-Node// 【初始化】LRUCache的构造方法// 参数capacity用来指定LRU缓存的容量,即缓存可以存储的key-value对的数量上限public LRUCache(int capacity) { this.capacity = capacity;// 构造环 放在这里的原因:在Java中,类字段初始化必须在构造方法内或者直接初始化字段时进行,不能在类的主体外进行语句级别的初始化操作,所以不能把下面两行放到构造器外面。dummy.prev = dummy;dummy.next = dummy;}// 如果有对应的key,则返回key对应的value。如果没有就返回-1public int get(int key) {Node node = getNode(key); // 去尝试拿到这个nodeif(node != null) return node.value;else return -1;}// 如果key已经存在,则变更其数据值value // 如果key不存在,则向缓存中插入该组 key-value// 如果插入操作导致键值对数量超过 capacity ,则应该 逐出 最久未使用的关键字public void put(int key, int value) { Node node = getNode(key); // 去尝试拿到这个nodeif(node == null) { // 如果没拿到,即key不存在,则向缓存中插入该组 key-valueNode newNode = new Node(key,value);pushFront(newNode); // 添加到顶部myhashmap.put(key,newNode); // 添加到hashmapif(myhashmap.size() > capacity){ // 如果插入操作导致键值对数量超过 capacity ,则应该 逐出 最久未使用的关键字Node backNode = dummy.prev;remove(backNode); // 从链表移走最后一个节点myhashmap.remove(backNode.key); // 从hashmap移走最后一个节点对应的key-Node键值对}}else{ // 如果拿到,即key已经存在,则变更其数据值value node.value = value;}}// 【辅助方法】// 1.在hashmap中根据key拿到Nodeprivate Node getNode(int key){if(!myhashmap.containsKey(key)){ // 如果没有返回nullreturn null; }Node node = myhashmap.get(key); // 如果有就把这个Node找出来remove(node);  // 1.把他从原来的链表中删了pushFront(node); // 2.把他放到链表最开始return node;       // 3.返回这个节点}// 2.把节点从链表中删了 ——前后节点跳跃过node连接即可private void remove(Node node){node.prev.next = node.next;node.next.prev = node.prev;}// 3.把节点放到链表最开始private void pushFront(Node node){node.next = dummy.next;dummy.next.prev = node;node.prev = dummy;dummy.next = node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

3 LinkedHashMap 常见面试题

LinkedHashMap 常见面试题
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/287784.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

“Kimi概念”降温,长文本“担不起”大模型的下一步

Kimi火了…… 这是这波AI浪潮中&#xff0c;国内创业公司第一次真正“破圈”。最明显的标志是&#xff0c;在二级市场中&#xff0c;Kimi已被市场作为一个概念板块来对待&#xff0c;它们被称之为“Kimi概念股”。在之前爆炒的板块中&#xff0c;可能有华为产业链、苹果产业链&…

SV-7045VP sip网络草坪音箱 室外网络广播POE供电石头音箱

SV-7045VP sip网络草坪音箱 室外网络广播POE供电石头音箱 18123651365微信 SV-7045VP SIP网络草坪音箱 sip POE石头音箱 描述 SV-7041VP是深圳锐科达电子有限公司的一款防水网络草坪音箱&#xff0c;具有10/100M以太网接口&#xff0c;可将网络音源通过自带的功放和喇叭输出…

ESD保护二极管ESD9B3.3ST5G 以更小的空间实现强大的保护 车规级TVS二极管更给力

什么是汽车级TVS二极管&#xff1f; TVS二极管是一种用于保护电子电路的电子元件。它主要用于电路中的过电压保护&#xff0c;防止电压过高而损坏其他部件。TVS二极管通常被称为“汽车级”是因为它们能够满足汽车电子系统的特殊要求。 在汽车电子系统中&#xff0c;由于车辆启…

机器学习——神经网络简单了解

一、神经网络基本概念 神经网络可以分为生物神经网络和人工神经网络 (1)生物神经网络,指的是生物脑内的神经元、突触等构成的神经网络&#xff0c;可以使生物体产生意识&#xff0c;并协助生物体思考、行动和管理各机体活动。 (2)人工神经网络,是目前热门的深度学习的研究…

【第二部分--Python之基础】02

二、运算符与程序流程控制 1、运算符 1.1 算术运算符 算术运算符用于组织整数类型和浮点类型的数据&#xff0c;有一元运算符和二元运算符之分。 一元算术运算符有两个&#xff1a;&#xff08;正号&#xff09;和-&#xff08;负号&#xff09;&#xff0c;例如&#xff1…

【C++11】thread线程库

【C11】thread线程库 目录 【C11】thread线程库thread类的简单介绍函数指针lambda表达式常用在线程中 线程函数参数join与detach利用RAII思想来自动回收线程 原子性操作库(atomic)atomic中的load函数&#xff1a;atomic中对变量进行原子操作的一些函数 CAS(Compare-And-Swap)无…

Git学习笔记之基础

本笔记是阅读《git pro》所写&#xff0c;仅供参考。 《git pro》网址https://git-scm.com/book/en/v2 git官网 https://git-scm.com/ 一、git起步 1.1、检查配置信息 git config --list查看所有的配置以及它们所在的文件 git config --list --show-origin可能有重复的变量名…

科技云报道:从“算力核弹”到生成式AI,新纪元还有多远?

科技云报道原创。 “我们需要更大的GPU”&#xff01; 3月19日凌晨&#xff0c;一年一度的“AI风向标”重磅会议——GTC 2024如期而至。 英伟达CEO黄仁勋在大会上发布了包括新一代加速计算平台NVIDIA Blackwell、Project GR00T人形机器人基础模型、Omniverse Cloud API、NVI…

【prompt六】MaPLe: Multi-modal Prompt Learning

1.motivation 最近的CLIP适应方法学习提示作为文本输入,以微调下游任务的CLIP。使用提示来适应CLIP(语言或视觉)的单个分支中的表示是次优的,因为它不允许在下游任务上动态调整两个表示空间的灵活性。在这项工作中,我们提出了针对视觉和语言分支的多模态提示学习(MaPLe),以…

大数据开发(日志离线分析项目)

大数据开发&#xff08;日志离线分析项目&#xff09; 一、项目需求1、使用jqueryecharts的方式调用程序后台提供的rest api接口&#xff0c;获取json数据&#xff0c;然后通过jquerycss的方式进行数据展示。工作流程如下&#xff1a;2、七大角度1、用户基本信息分析模块2、浏览…

【计算机视觉】三、图像处理——实验:图像去模糊和去噪、提取边缘特征

文章目录 0. 实验环境1. 理论基础1.1 滤波器&#xff08;卷积核&#xff09;1.2 PyTorch:卷积操作 2. 图像处理2.1 图像读取2.2 查看通道2.3 图像处理 3. 图像去模糊4. 图像去噪4.1 添加随机噪点4.2 图像去噪 0. 实验环境 本实验使用了PyTorch深度学习框架&#xff0c;相关操作…

openGauss学习笔记-252 openGauss性能调优-使用Plan Hint进行调优-Scan方式的Hint

文章目录 openGauss学习笔记-252 openGauss性能调优-使用Plan Hint进行调优-Scan方式的Hint252.1 功能描述252.2 语法格式252.3 参数说明252.4 示例 openGauss学习笔记-252 openGauss性能调优-使用Plan Hint进行调优-Scan方式的Hint 252.1 功能描述 指明scan使用的方法&#…

【计算机操作系统】深入探究CPU,PCB和进程工作原理

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…

【二叉树】Leetcode 102. 二叉树的层序遍历【中等】

二叉树的层序遍历 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09; 示例1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 解题思路…

elasticsearch基础应用

1._cat接口 | _cat接口 | 说明 | | GET /_cat/nodes | 查看所有节点 | | GET /_cat/health | 查看ES健康状况 | | GET /_cat/master | 查看主节点 | | GET /_cat/indices | 查看所有索引信息 | es 中会默认提供上面的几个索引&#xff0c;表头…

Spring 自定义 CustomQualifier

为什么写这篇文章 Spring 支持类型注入&#xff0c;并且可以通过Qualifier 或者Mate 调整类型注入的范围。但是通过自定义注解结合现有的 Qualifier 使用起来有种种困难。 将 Qualifier 融合在自定义注解中&#xff0c;在使用 AliasFor 遇到问题仅仅检查注解中的一部分内容是否…

外包干了10天,技术倒退明显

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近6年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…

Tomcat下载安装以及配置

一、Tomcat介绍 二、Tomcat下载安装 进入tomcat官网&#xff0c;https://tomcat.apache.org/ 1、选择需要下载的版本&#xff0c;点击下载 下载路径一定要记住&#xff0c;并且路径中尽量不要有中文 8、9、10都可以&#xff0c;本博文以8为例 2、将下载后的安装包解压到指定位…

【小黑送书—第十四期】>>重磅升级——《Excel函数与公式应用大全》(文末送书)

今天给大家带来AI时代系列书籍&#xff1a;《Excel 2019函数与公式应用大全》全新升级版&#xff0c;Excel Home多位微软全球MVP专家打造&#xff0c;精选Excel Home海量案例&#xff0c;披露Excel专家多年研究成果&#xff0c;让你分分钟搞定海量数据运算&#xff01; 由北京…

YOLOv8官方仓库正式支持RT-DETR训练、测试以及推理

YOLOv8太卷啦 | YOLOv8官方仓库正式支持RT-DETR训练、测试以及推理 RT-DETR由百度开发&#xff0c;是一款端到端目标检测器&#xff0c;在保持高精度的同时提供实时性能。它利用ViT的强大特性&#xff0c;通过解耦尺度内交互和跨尺度融合来有效处理多尺度特征。 RT-DETR具有很强…