【算法刷题】手撕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。

相关文章

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,：本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖？1.2 核心危害二、Spring的三级缓存机制2.1 三
阅读更多...
C#中async await异步关键字用法和异步的底层原理全解析

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》：本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
Go 语言中的select语句详解及工作原理

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道（channel）操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1：监听多个通道示例 2：带
阅读更多...
鸿蒙中@State的原理使用详解(HarmonyOS 5)

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的？二、@Spythontate的基本原理1. 依赖关系的收集2.
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
Java编译生成多个.class文件的原理和作用

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类（常规内部类）局部内部类（方法内部类）匿名内部类二、
阅读更多...
Python中随机休眠技术原理与应用详解

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2
阅读更多...
Java的IO模型、Netty原理解析

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容：标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO（blocking I/O）NI
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2