双向链表+Map实现LRU
LRU:
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。
核心思想:
基于Map实现k-v存储,双向链表中使用一个虚拟头部和虚拟尾部,虚拟头部的下一个结点是链表第一个结点,虚拟尾部的前一个结点是链表最后一个结点。每次查询、新增、修改某个Key时,将key在链表中的位置移动到头部,这样尾部结点就是最近最少使用的,每次容量超限时从尾部删除。get缓存和put缓存操作的时间复杂度都为O(1)
链表结点结构:
class Node{int key;int value;Node next;Node prev;public Node(){next=null;prev=null;}public Node(int key,int value){this.key=key;this.value=value;next=null;prev=null;}}
代码:
假设缓存的kv都为int类型
public class LRUCache {class Node{int key;int value;Node next;Node prev;public Node(){next=null;prev=null;}public Node(int key,int value){this.key=key;this.value=value;next=null;prev=null;}}private int capacity;private HashMap<Integer,Node> cache=new HashMap<>();private Node head,tail;public LRUCache(int capacity) {this.capacity=capacity;head=new Node();tail=new Node();head.next=tail;tail.prev=head;}public int get(int key) {Node node= cache.get(key);if(node==null)return -1;//删除key在链表中的noderemoveNode(node);//将key在链表中的node放到队头addToHead(node);return node.value;}public void put(int key, int value) {Node node =cache.get(key);if(node!=null){//更新valuenode.value=value;//删除key在链表中的noderemoveNode(node);//将key在链表中的node放到队头addToHead(node);}else{Node newNode=new Node(key,value);cache.put(key,newNode);//将key在链表中的node放到队头addToHead(newNode);if(cache.size()>capacity){//容量超过capacityNode remo =tail.prev;cache.remove(remo.key);removeNode(remo);}}}private void removeNode(Node node){node.prev.next=node.next;node.next.prev=node.prev;}private void addToHead(Node node){node.next=head.next;node.prev=head;head.next.prev=node;head.next=node;}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)); // 返回 1lRUCache.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)); // 返回 3System.out.println(lRUCache.get(4)); // 返回 4}
}
运行结果:

注:
为什么用双向链表而不是单向链表?
在删除链表操作中,单链表要找到要删除结点的前驱结点时间复杂度就为O(n)了,而用双链表可以在O(1)复杂度上删除结点。
为什么链表节点需要同时存储 key 和 value,而不是仅仅只存储 value
(容量超限)删除缓存时,要根据node的key从Map中找到node,从而将缓存删除。
相关文章:
双向链表+Map实现LRU
LRU: LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。 核心思想: 基于Map实现k-v存储,双向链表中使用一个虚拟头部和虚拟尾部,虚拟头部的…...
HTML(27)——渐变
渐变是多个颜色逐渐变化的效果,一般用于设置盒子模型 线性渐变 属性:background-image : linear-gradient( 渐变方向 颜色1 终点位置, 颜色2 终点位置, ......); 取值: 渐变方向:可选 to 方位名词角度度数 终点位置:可选 百分…...
2024上半年网络工程师考试《应用技术》试题一
阅读以下说明,回答问题。 【说明】 MPLS基于(1)进行转发,进行MPLS标签交换和报文转发的网络设备称为(2),构成MPLS域(MPSDomain)。位于MPLS域边缘、连接其他网络的LSR称为(3),区域内部的LSR称为核心LSR(CoreLSR)IP报文进入MPLS网络时…...
pnpm介绍
PNPM 是一个 JavaScript 包管理器,类似于 npm 和 Yarn。它的全称是 "Performant npm",主要设计目标是优化包的安装和管理过程,以提升速度和效率。PNPM 的主要特点包括: 符号链接(Symlink)&#x…...
Linux内核的启动过程(非常详细)零基础入门到精通,收藏这一篇就够了
Linux内核的生成过程 内核的生成步骤可以概括如下: ① 先生成 vmlinux,这是一个elf可执行文件。② 然后 objcopy 成 arch/i386/boot/compressed/vmlinux.bin,去掉了原 elf 文件中一些无用的section等信息。③ gzip 后压缩为 arch/i386/boot…...
相关分析 - 肯德尔系数
肯德尔系数(Kendall’s Tau)是一种非参数统计方法,用于衡量两个变量之间的相关性。它是由统计学家莫里斯肯德尔(Maurice Kendall)在1938年提出的。肯德尔系数特别适用于有序数据,可以用来评估两个有序变量之…...
【咨询】企业数字档案馆(室)建设方案-模版范例
导读:本模版来源某国有大型医药行业集团企业数字档案馆(室)建设方案(一期300W、二期250W),本人作为方案的主要参与者,总结其中要点给大家参考。 目录 1、一级提纲总览 2、项目概述 3、总体规…...
selfClass 与 superClass 的区别
在 Objective-C 中,[self class] 和 [super class] 都用于获取对象的类信息,但它们在运行时的行为略有不同。理解它们的区别有助于更好地掌握 Objective-C 的消息传递机制和继承关系。让我们详细解释这两个调用的区别。 [self class] 当你在一个对象方…...
秒懂设计模式--学习笔记(6)【创建篇-建造者模式】
目录 5、建造者模式5.1 介绍5.2 建造步骤的重要性5.3 地产开发商的困惑5.4 建筑施工方5.5 工程总监5.6 项目实施5.7 建造者模式的各角色定义5.8 建造者模式 5、建造者模式 5.1 介绍 建造者模式(Builder)又称为生成器模式,主要用于对复杂对象…...
领略超越王勃的AI颂扬艺术:一睹其惊艳夸赞风采
今日,咱也用国产AI技术,文心一言3.5的文字生成与可灵的图像创作,自动生成一篇文章,提示语文章末下载。 【玄武剑颂星际墨侠】 苍穹为布,星辰织锦,世间万象,皆入我玄武剑公众号之浩瀚画卷。此号…...
Linux走进网络
走进网络之网络解析 目录 走进网络之网络解析 一、认识计算机 1.计算机的发展 2.传输介质 3.客户端与服务器端的概念 交换机 路由器 二、计算机通信与协议 1. 协议的标准化 2. 数据包的传输过程 OSI 协议 ARP协议 3. TCP/IP:四层模型 4. TCP三次握手和四次挥手…...
go语言Gin框架的学习路线(六)
gin的路由器 Gin 是一个用 Go (Golang) 编写的 Web 框架,以其高性能和快速路由能力而闻名。在 Gin 中,路由器是框架的核心组件之一,负责处理 HTTP 请求并将其映射到相应的处理函数上。 以下是 Gin 路由器的一些关键特性和工作原理的简要解释…...
Java面经知识点汇总版
Java面经知识点汇总版 算法 14. 最长公共前缀(写出来即可) Java 计算机基础 数据库 基础 SQL SELECT first_name, last_name, salary FROM employees WHERE department Sales AND salary > (SELECT AVG(salary)FROM employeesWHERE department Sal…...
详细分析Sql Server中的declare基本知识
目录 前言1. 基本知识2. Demo3. 拓展Mysql4. 彩蛋 前言 实战探讨主要来源于触发器的Demo 1. 基本知识 DECLARE 语句用于声明变量 声明的变量可以用于存储临时数据,并在 SQL 查询中多次引用 声明变量:使用 DECLARE 语句声明一个或多个变量变量命名&a…...
Perl 语言入门:编写并执行你的第一个脚本
摘要 Perl 是一种高级、通用的、解释型、动态编程语言,以其强大的文本处理能力而闻名。本文将指导初学者如何编写和执行他们的第一个 Perl 脚本,包括 Perl 的基本概念、脚本的基本结构、运行 Perl 脚本的方法以及一些简单的 Perl 语法。 引言 Perl&am…...
python库 - missingno
missingno 是一个用于可视化和分析数据集中缺失值的 Python 库。它提供了一系列简单而强大的工具,帮助用户直观地理解数据中的缺失模式,从而更好地进行数据清洗和预处理。missingno 库特别适用于数据分析和数据科学项目,尤其是在处理缺失数据…...
VPN的限制使得WinSCP无法直接连接到FTP服务器解决办法
由于VPN的限制使得WinSCP无法直接连接到FTP服务器,并且堡垒机的文件上传限制为500M,因此我们需要找到一种绕过这些限制的方法。以下是几个可行的方案: 方法1:通过分割文件上传 分割文件: 使用文件分割工具(…...
PCI DSS是什么?
PCI DSS,全称为Payment Card Industry Data Security Standard(支付卡行业数据安全标准),是由支付卡行业安全标准委员会(PCI Security Standards Council)制定的一套安全标准,旨在保护信用卡信息…...
DeepMind的JEST技术:AI训练速度提升13倍,能效增强10倍,引领绿色AI革命
谷歌旗下的人工智能研究实验室DeepMind发布了一项关于人工智能模型训练的新研究成果,声称其新提出的“联合示例选择”(Joint Example Selection,简称JEST)技术能够极大地提高训练速度和能源效率,相比其他方法ÿ…...
如何使用 pytorch 创建一个神经网络
我已发布在:如何使用 pytorch 创建一个神经网络 SapientialM.Github.io 构建神经网络 1 导入所需包 import os import torch from torch import nn from torch.utils.data import DataLoader from torchvision import datasets, transforms2 检查GPU是否可用 dev…...
3分钟上手!Balena Etcher:安全烧录系统镜像的终极解决方案
3分钟上手!Balena Etcher:安全烧录系统镜像的终极解决方案 【免费下载链接】etcher Flash OS images to SD cards & USB drives, safely and easily. 项目地址: https://gitcode.com/GitHub_Trending/et/etcher 你是否曾因烧录系统镜像而丢失…...
K型热电偶的5个常见设计坑:从运放选型到单片机ADC采样的避坑指南
K型热电偶的5个常见设计坑:从运放选型到单片机ADC采样的避坑指南 在工业测温领域,K型热电偶凭借其宽温区、高性价比和良好的线性度,成为工程师们的首选传感器之一。然而,许多初入行业的硬件工程师在实际应用中常常踩入一些"…...
LiuJuan Z-Image Generator真实案例:为独立音乐人生成专辑封面人像全流程
LiuJuan Z-Image Generator真实案例:为独立音乐人生成专辑封面人像全流程 最近,一位独立音乐人朋友找到我,说他想为自己的新专辑设计一个封面。预算有限,请不起专业画师,但又不想要那些千篇一律的模板。他想要一张能体…...
Qwen-Image-2512-SDNQ Web服务实战:WebUI下载功能与浏览器兼容性全平台测试
Qwen-Image-2512-SDNQ Web服务实战:WebUI下载功能与浏览器兼容性全平台测试 1. 项目概述与核心价值 今天我要和大家分享一个特别实用的AI图片生成项目——基于Qwen-Image-2512-SDNQ-uint4-svd-r32模型的Web服务。这个项目最大的亮点在于,它把复杂的AI图…...
GPT-OSS-20B参数调优实战:如何设置才能获得最佳生成效果
GPT-OSS-20B参数调优实战:如何设置才能获得最佳生成效果 1. 模型特性与调优基础 1.1 GPT-OSS-20B核心架构 GPT-OSS-20B作为OpenAI开源的重量级模型,采用混合专家架构(MoE)设计,总参数量210亿,其中活跃参数36亿。这种设计使其在…...
全志T3核心板DDR初始化失败:从ZQ校准误导到VREF电压偏差的排查实录
1. 问题现象与初步排查 那天早上刚到实验室,测试组的同事就急匆匆跑过来:"哥,又有三台设备启动不了,uboot都没跑起来!"我接过设备一看,果然又是熟悉的ZQ校准错误提示,这已经是本周第五…...
Android 性能优化:内存泄漏排查与解决
Android性能优化:内存泄漏排查与解决 在Android开发中,性能优化是提升用户体验的关键环节,而内存泄漏则是常见却容易被忽视的问题。内存泄漏会导致应用占用内存持续增加,最终引发卡顿、崩溃甚至被系统强制终止。如何高效排查与解…...
深度解析ShardingCore:EF Core分库分表架构实战与性能优化指南
深度解析ShardingCore:EF Core分库分表架构实战与性能优化指南 【免费下载链接】sharding-core high performance lightweight solution for efcore sharding table and sharding database support read-write-separation .一款ef-core下高性能、轻量级针对分表分库…...
MusePublic显存利用率提升方案:CPU卸载+自动清理策略详解
MusePublic显存利用率提升方案:CPU卸载自动清理策略详解 1. 项目背景与显存挑战 MusePublic是一款专为艺术感时尚人像创作设计的轻量化文本生成图像系统。基于专属大模型和safetensors格式封装,系统针对艺术人像的优雅姿态、细腻光影和故事感画面进行了…...
TwinCAT界面美化指南:3步搞定背景主题切换(附最佳配色方案推荐)
TwinCAT界面美化实战:从主题定制到高效编程的视觉优化 每次打开TwinCAT开发环境,是否觉得默认的灰白色调让人昏昏欲睡?作为工业自动化领域的核心开发工具,TwinCAT的界面美学长期被工程师们忽视。实际上,一个精心调校的…...
