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

2024-04-23 05:44
文章标签 算法 原理 图解 刷题 lru 核心思想

本文主要是介绍【算法刷题】手撕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断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言（assert）：从原理到实战引言：为什么需要断言？一、断言基础1.1 语
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

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

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

MySQL中的表连接原理分析

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

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

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

Java Stream的distinct去重原理分析

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

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建
阅读更多...
Spring Boot 实现 IP 限流的原理、实践与利弊解析

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

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

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

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

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

《Mysql的主从同步/复制的原理分析》：本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步？mysql主从同步架构有哪些？Mysql主从复制的原理/整体流程级联复制架构为什么好？Mysql主从复制注意
阅读更多...
Nacos注册中心和配置中心的底层原理全面解读

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2