【算法刷题】手撕LRU算法(原理、图解、核心思想)

2024-04-23 05:44

本文主要是介绍【算法刷题】手撕LRU算法(原理、图解、核心思想),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

文章目录

  • 1.LRU算法
    • 1.1相关概念
    • 1.2图解举例
    • 1.3基于HashMap和双向链表实现
      • 1.3.1核心思想
      • 1.3.2代码解读
      • 1.3.3全部代码

1.LRU算法

1.1相关概念

  • LRU(Least Recently Used,最近最久未使用算法):
    • 定义:根据页面调入内存后的使用情况来做决策。LRU页面置换算法选择最近最久未使用的页面予以淘汰;
    • 支持:该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问内以来锁经历的时间t;当淘汰一个页面时,选择现有页面中 t值最大的(即最近最久未使用的)页面进行淘汰
  • 两种硬件支持(选择其中一种即可):
    1. 寄存器:
      • 作用:其中包含了标记位和时间戳,标记位可以快速判断缓存块(页面)是否有效,而无需遍历整个栈来查找。时间戳可以快速记录和更新缓存块(页面)的访问时间,而不必每次访问都遍历栈来更新。
    2. 栈:
      • 作用:用于记录缓存块(页面)的访问顺序(当前使用中的各个页面的页面号)。
      • 新增页面步骤:
        • 每当进程访问某页面时,判断该页面在栈中是否存在
          • 若存在,则将该页面的页面号从栈中取出,并将该原页面号压入栈顶;
          • 若不存在,则将栈底元素移除,并将新页面号压入栈顶;
        • 因此,栈顶始终是最新被访问页面的页面号 , 栈底则是最近最久未使用页面的页面号!

1.2图解举例

  • 举例前提:假设内存只能容纳3个页大小,进程按照 5 2 1 9 2 0 2 8的次序访问页
  • 假设内存按照栈的方式来描述访问时间,并保证 栈顶始终是最新被访问页面的页面号 , 栈底则是最近最久未使用页面的页面号

image-20240419170652555

1.3基于HashMap和双向链表实现

1.3.1核心思想

  • 核心思想:使用自定义节点DLinkedNode模拟双向链表,并通过双向链表实现栈功能;

  • 使用HashMap存储以页面号为key,value存储指向双向链表节点的指针

  • 双向链表维护了页面的访问顺序,链表的头部(即栈顶)为最新访问的页面,底部为最久未使用的页面

  • put(key,value):首先在 HashMap 找到 Key 对应的节点,

    • 如果节点存在,更新节点的值,并把这个节点移动栈顶
    • 如果不存在,需要构造新的节点,并且尝试把节点塞到栈顶 ,如果LRU空间不足,则通过 tail 淘汰掉栈底的节点,同时在 HashMap 中移除 Key。

image-20240419175738628

1.3.2代码解读

  • DLinkedNode
class DLinkedNode {String key;int value;DLinkedNode pre;DLinkedNode next;
}
  • cache:使用HashTable代替HashMap,线程安全
private Hashtable<String, DLinkedNode> cache = new Hashtable<>();
  • put流程:
public void put(String key, int value) {DLinkedNode node = cache.get(key);if(node == null){DLinkedNode newNode = new DLinkedNode();newNode.key = key;newNode.value = value;this.cache.put(key, newNode);this.addNode(newNode);++count;if(count > capacity){// 淘汰栈底元素DLinkedNode tail = this.popTail();this.cache.remove(tail.key);--count;}}else{//该元素已经存在//将该元素移动到栈顶node.value = value;this.moveToHead(node);}
}
  • 移动栈中的元素到栈顶:
    • 首先先删除该节点 (解除引用)
    • 再添加该节点到栈顶
//将该节点移动到头节点
private void moveToHead(DLinkedNode node){this.removeNode(node);this.addNode(node);
}
//删除该节点(跳过该节点)
private void removeNode(DLinkedNode node){DLinkedNode pre = node.pre;DLinkedNode next = node.next;pre.next = next;next.pre = pre;
}
//添加节点到栈顶
private void addNode(DLinkedNode node){node.pre = head;node.next = head.next;head.next.pre = node;	//头部节点的上一个节点为新节点head.next = node;
}

1.3.3全部代码

class DLinkedNode {String key;int value;DLinkedNode pre;DLinkedNode next;
}public class LRUCache {private Hashtable<String, DLinkedNode> cache = new Hashtable<>();private int count;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.count = 0;this.capacity = capacity;head = new DLinkedNode();head.pre = null;tail = new DLinkedNode();tail.next = null;head.next = tail;tail.pre = head;}public void put(String key, int value) {DLinkedNode node = cache.get(key);if(node == null){DLinkedNode newNode = new DLinkedNode();newNode.key = key;newNode.value = value;this.cache.put(key, newNode);this.addNode(newNode);++count;if(count > capacity){// 淘汰栈底元素DLinkedNode tail = this.popTail();this.cache.remove(tail.key);--count;}}else{//该元素已经存在//将该元素移动到栈顶node.value = value;this.moveToHead(node);}}//添加节点private void addNode(DLinkedNode node){node.pre = head;node.next = head.next;head.next.pre = node;head.next = node;}//删除该节点(跳过该节点)private void removeNode(DLinkedNode node){DLinkedNode pre = node.pre;DLinkedNode next = node.next;pre.next = next;next.pre = pre;}//将该节点移动到头节点private void moveToHead(DLinkedNode node){this.removeNode(node);this.addNode(node);}//淘汰栈底元素private DLinkedNode popTail(){DLinkedNode res = tail.pre;this.removeNode(res);return res;}@Overridepublic String toString() {StringBuilder sbu = new StringBuilder();DLinkedNode cur = head.next;sbu.append("{");while (cur != tail) {if (cur.next != tail) {sbu.append(cur.key).append("=").append(cur.value).append(", ");} else {sbu.append(cur.key).append("=").append(cur.value);}cur = cur.next;}sbu.append("}");return sbu.toString();}public static void main(String[] args) {LRUCache lruCache = new LRUCache(3);lruCache.put("1", 5);lruCache.put("2", 2);lruCache.put("3", 1);System.out.println(lruCache);System.out.println("使用后:");lruCache.put("2",2);System.out.println(lruCache);lruCache.put("2",2);System.out.println(lruCache);lruCache.put("4", 13);System.out.println("最不常用的被删除,新元素插到头部:");System.out.println(lruCache);}}
  • 测试结果:

image-20240419181126783

在这里插入图片描述

这篇关于【算法刷题】手撕LRU算法(原理、图解、核心思想)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/927934

相关文章

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

Nacos注册中心和配置中心的底层原理全面解读

《Nacos注册中心和配置中心的底层原理全面解读》:本文主要介绍Nacos注册中心和配置中心的底层原理的全面解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录临时实例和永久实例为什么 Nacos 要将服务实例分为临时实例和永久实例?1.x 版本和2.x版本的区别