当前位置: 首页 > news >正文

【数据结构与算法】通过双向链表和HashMap实现LRU缓存 详解

这个双向链表采用的是有伪头节点和伪尾节点的 与上一篇文章中单链表的实现不同,区别于在实例化这个链表时就初始化了的伪头节点和伪尾节点,并相互指向,在第一次添加节点时,不需要再考虑空指针指向问题了。

/*** 通过链表与HashMap实现LRU缓存** @author CC* @version 1.0* @since2023/9/27*/
public class LRUCache {private Map<Integer, Node> cache = new HashMap<>();//哈希表private int size;//链表长度private int capacity;//缓存容量private Node first;//伪头节点private Node last;//伪尾节点/*** 将一个新节点添加到头部** @param newNode 要添加的新节点*/private void addFirst(Node newNode) {//注意: 顺序很重要//1、分配新节点的前驱和后继newNode.prev = first;newNode.next = first.next;//2、头节点原来的后继的前驱指向新节点first.next.prev = newNode;//3、头节点的后继执行新节点first.next = newNode;}/*** 删除一个节点** @param node 要删除的节点*/private void deleteNode(Node node) {//要删除节点的后继和前驱相互指引node.prev.next = node.next;node.next.prev = node.prev;}/*** 将一个节点放到伪头节点后** @param node 移动的节点*/private void moveToFirst(Node node) {//删除这个节点deleteNode(node);//添加一个头节点addFirst(node);}/*** 删除尾节点** @return 返回删除的这个节点*/private Node deleteToLast() {//获得伪尾节点的前驱 也就是尾节点Node ret = last.prev;//删除尾节点deleteNode(last.prev);return ret;}/*** 存入缓存** @param key* @param value*/public void put(int key, int value) {//从hash表中查询这个健Node node = cache.get(key);//如果hash表中不存在要添加的健if (node == null) {//创建一个新的节点Node newNode = new Node(key, value);//将这个健和节点添加到hash表中cache.put(key, newNode);//将这个节点存到头节点中addFirst(newNode);//如果这个缓存已满if (++size > capacity) {//删除尾节点Node last = deleteToLast();//从hash表中也删除这个健cache.remove(last.key);size--;}//如果hash表中存在要添加的健} else {//将新添加的值覆盖原来的值node.value = value;//并移到头节点moveToFirst(node);}}/*** 获取缓存** @param key 该缓存的健* @return 返回 该节点的值*/public int get(int key) {//通过健从hash表中获取这个节点Node node = cache.get(key);//如果为空 则返回-1if (node == null) {return -1;}//否则 将该节点 移到头节点处moveToFirst(node);return node.value;}/*** 双向链表的遍历 头->尾** @return*/@Overridepublic String toString() {StringJoiner sj = new StringJoiner("->");for (Node n =first.next;n.next!=null;n=n.next){sj.add(String.valueOf(n.value));}return "头->尾:"+sj.toString();}/*** 构造方法** @param capacity 设置缓存容量*/public LRUCache(int capacity) {size = 0;//初始链表长度位0this.capacity = capacity;//设置缓存容量first = new Node();//实例化伪头节点last = new Node();//实例化伪尾节点//初始头尾节点相互指向first.next = last;last.prev = first;}/*** 节点类*/class Node {int key; //键int value;//值Node prev;//前驱Node next;//后继/*** 无参构造*/public Node() {}/*** 有参构造** @param key   健* @param value 值*/public Node(int key, int value) {this.key = key;this.value = value;}}}

测试

        //实例一个缓存大小为7的LRU缓存LRUCache lruCache =new LRUCache(5);lruCache.put(1,1);lruCache.put(2,2);lruCache.put(3,3);lruCache.put(4,4);lruCache.put(5,5);lruCache.put(6,6);System.out.println("依次存入1、2、3、4、5、6后的缓存:"+lruCache);int l1 = lruCache.get(1);System.out.println("取出1后的缓存:"+lruCache+",取出的值:"+l1);int l2 = lruCache.get(2);System.out.println("取出2后的缓存:"+lruCache+",取出的值:"+l2);int l3 = lruCache.get(3);System.out.println("取出3后的缓存:"+lruCache+",取出的值:"+l3);lruCache.put(9,9);System.out.println("存入9后的缓存:"+lruCache);

测试结果

相关文章:

【数据结构与算法】通过双向链表和HashMap实现LRU缓存 详解

这个双向链表采用的是有伪头节点和伪尾节点的 与上一篇文章中单链表的实现不同&#xff0c;区别于在实例化这个链表时就初始化了的伪头节点和伪尾节点&#xff0c;并相互指向&#xff0c;在第一次添加节点时&#xff0c;不需要再考虑空指针指向问题了。 /*** 通过链表与HashMa…...

MySQL的内置函数

文章目录 1. 聚合函数2. group by子句的使用3. 日期函数4. 字符串函5. 数学函数6. 其它函数 1. 聚合函数 COUNT([DISTINCT] expr) 返回查询到的数据的数量 用SELECT COUNT(*) FROM students或者SELECT COUNT(1) FROM students也能查询总个数。 统计本次考试的数学成绩分数去…...

数据结构与算法-(7)---栈的应用-(3)表达式转换

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

Lilliefors正态性检验(一种非参数统计方法)

Lilliefors检验&#xff08;也称为Kolmogorov-Smirnov-Lilliefors检验&#xff09;是一种用于检验数据是否符合正态分布的统计检验方法&#xff0c;它是Kolmogorov-Smirnov检验的一种变体&#xff0c;专门用于小样本情况。与K-S检验不同&#xff0c;Lilliefors检验不需要假定数…...

【云原生】配置Kubernetes CronJob自动备份MySQL数据库(单机版)

文章目录 每天自动备份数据库MySQL【云原生】配置Kubernetes CronJob自动备份Clickhouse数据库 每天自动备份数据库 MySQL 引用镜像:databack/mysql-backup,使用文档:https://hub.docker.com/r/databack/mysql-backup 测试、开发环境:每天0点40分执行全库备份操作,备份文…...

基于PSO算法的功率角摆动曲线优化研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

数论知识点总结(一)

文章目录 目录 文章目录 前言 一、数论有哪些 二、题法混讲 1.素数判断,质数,筛法 2.最大公约数和最小公倍数 3.快速幂 4.约数 前言 现在针对CSP-J/S组的第一题主要都是数论,换句话说,持数论之剑,可行天下矣! 一、数论有哪些 数论 原根,素数判断,质数,筛法最大公约数…...

知识分享 钡铼网关功能介绍:使用SSLTLS 加密,保证MQTT通信安全

背景 为了使不同的设备或系统能够相互通信&#xff0c;让旧有系统和新的系统可以集成&#xff0c;通信更加灵活和可靠。以及将数据从不同的来源收集并传输到不同的目的地&#xff0c;实现数据的集中管理和分发。 通信网关完美克服了这一难题&#xff0c;485或者网口的设备能通过…...

asp.net core mvc区域路由

ASP.NET Core 区域路由&#xff08;Area Routing&#xff09;是一种将应用程序中的路由划分为多个区域的方式&#xff0c;类似于 MVC 的控制器和视图的区域划分。区域路由可以帮助开发人员更好地组织应用程序的代码和路由&#xff0c;并使其更易于维护。 要使用区域路由&#…...

KNN(下):数据分析 | 数据挖掘 | 十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

Servlet开发-session和cookie理解案例-登录页面

项目展示 进入登录页面&#xff0c;输入正确的用户名和密码以后会自动跳到主页 登录成功以后打印用户名以及上次登录的时间&#xff0c;如果浏览器和客户端都保存有上次登录的信息&#xff0c;则不需要登录就可以进入主页 编码思路 1.首先提供一个登录的前端页面&…...

Polygon Miden:扩展以太坊功能集的ZK-optimized rollup

1. 引言 Polygon Miden定位为zkVM&#xff0c;定于2023年Q4上公开测试网。 zk、zkVM、zkEVM及其未来中指出&#xff0c;当前主要有3种类型的zkVM&#xff0c;括号内为其相应的指令集&#xff1a; mainstream&#xff08;WASM, RISC-V&#xff09;EVM&#xff08;EVM bytecod…...

[题]宝物筛选 #单调队列优化

五、宝物筛选&#xff08;洛谷P1776&#xff09; 题目链接 好家伙&#xff0c;找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #include<bits/stdc.h> using namespace std; const int N 1e5 10; int f[N]; int n, m; int v, w, s; int l…...

.NET的键盘Hook管理类,用于禁用键盘输入和切换

一、MyHook帮助类 此类需要编写指定屏蔽的按键&#xff0c;灵活性差。 using System; using System.Runtime.InteropServices; using System.Diagnostics; using System.Windows.Forms; using Microsoft.Win32;namespace MyHookClass {/// <summary>/// 类一/// </su…...

Anaconda Jupyter

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言An…...

Unity中Shader的前向渲染路径ForwardRenderingPath

文章目录 前言一、前向渲染路径的特点二、渲染方式1、逐像素(效果最好)2、逐顶点(效果次之)3、SH球谐(效果最差) 三、Unity中对灯光设置 后&#xff0c;自动选择对应的渲染方式1、ForwardBase仅用于一个逐像素的平行灯&#xff0c;以及所有的逐顶点与SH2、ForwardAdd用于其他所…...

简历项目优化关键方法论-START

START方法论是非常著名的面试法则&#xff0c;经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务&#xff0c;你负责的做的是什么Action:动作&#xff0c;针对这样的情况分析&#xff0c;你采用了什么行动方式Result:结果&#xff0c;在这样…...

TensorFlow学习1:使用官方模型进行图片分类

前言 人工智能以后会越来越发达&#xff0c;趁着现在简单学习一下。机器学习框架有很多&#xff0c;这里觉得学习谷歌的 TensorFlow&#xff0c;谷歌的技术还是很有保证的&#xff0c;另外TensorFlow 的中文文档真的很友好。 文档&#xff1a; https://tensorflow.google.cn/…...

C++ 并发编程实战 第八章 设计并发代码 一

目录 8.1 在线程间切分任务 8.1.1 先在线程间切分数据&#xff0c;再开始处理 8.1.2 以递归方式划分数据 8.1.3 依据工作类别划分任务 借多线程分离关注点需防范两大风险 在线程间按流程划分任务 8.2 影响并发性能的因素 8.2.1 处理器的数量 8.2.2 数据竞争和缓存兵乓…...

设计模式8、装饰者模式 Decorator

解释说明&#xff1a;动态地给一个对象增加一些额外的职责。就扩展功能而言&#xff0c;装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件&#xff08;Component&#xff09;&#xff1a;定义一个抽象接口以规范准备收附加责任的对象 具体构件&#xff08;ConcreteCom…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...