LRU缓存

devtools/2024/11/23 11:57:38/

什么是LRU缓存?

    LRU（Least Recently Used）是最近最少使用算法，是操作系统中用于分页置换的算法，如果要向内存中添加分页，并且内存分页已满的情况下，就选出最近一段时间最不常用的分页进行置换（例如将最不常用的分页暂时放到磁盘，这时内存就有一个空闲分页，将新增分页放过来即可）。

题目

链接：leetcode.146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity)

    以 正整数 作为容量 capacity 初始化 LRU 缓存

  • int get(int key)

    如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

  • void put(int key, int value)

    如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

分析

一、 容器内容的设计

我们可以用一个容器对数据进行缓存，第一个元素表示最近最不经常使用，最后一个元素表示最近最经常使用，从前往后依次过渡

二、 数据结构的选型

① 使用数组

假设将内容全部用数组进行缓存

现在使用元素2，那么应该将2移到尾部，3、4、5全部向前移动。这样查询的时间复杂度为O(1)，移动的时间复杂度为O(n)。

那么题目要求的get时间复杂度就为O(n)，put时间复杂度为O(n)。显然不能使用数组。

② 使用链表

如果使用元素2，那么需要找到元素2，然后将元素2放到尾部即可。这样查询的时间复杂度为O(n)，移动的时间复杂度为O(1)，

显然对于查询操作我们可以使用哈希去优化，使得查询的时间复杂度为O(1)

③ 哈希+ 链表

 

这样查询2只需要通过key映射，查询效率为O(1)，将2移动到链表尾部，1指向3即可，移动效率为O(1)，完美!

但是这里有个问题，我们通过key定位到元素2时，如何获取2前面的元素？

聪明的小伙伴已经想出来了，答案就是将单链表变为双向链表

④ 哈希 + 双向链表

 这样不管是查询还是移动，复杂度都是O(1)

解答

① 设计双向链表节点结构

java">class ListNode {//	节点前驱ListNode pre;//	节点后继ListNode next;//	哈希中的keyint key;//	数据域，记录缓存内容int val;//	构造函数public ListNode() {}public ListNode(int key, int val) {this.key = key;this.val = val;}
}

这里节点中为什么要设计key呢？因为如果添加元素时缓存区已满，就需要删除链表中第一个元素（最近最不常使用的元素），同时还要在哈希中移除，所以需要记录这个数据的key

② 使用带假节点的双向链表

为什么使用假节点？原因很简单，操作方便。对于一个单链表，添加元素时要判断头指针是否为空，删除元素时需要判断是不是头部元素，如果是头部元素，就需要将头指针向后移，但是使用假节点之后便不再需要进行这些操作。结构如下：

 可以看出，对于带有假节点的链表，head后邻节点是有效的第一个节点（在不是rear的情况下），rear前邻节点是最后一个有效节点（在不是head的情况下）

③ 初始化LRU容器

java">//	头部指针
private ListNode head;
//	尾部指针
private ListNode rear;
//	哈希表
private HashMap<Integer, ListNode> hash = new HashMap<>();
//	缓存容量
private final int capacity;public LRUCache(int capacity) {//	缓存容量this.capacity = capacity;//  初始化双向链表//	头部假节点this.head = new ListNode();//	尾部假节点this.rear = new ListNode();//	首尾相连head.next = rear;rear.pre = head;
}

目前为止，双向链表还是一个空链表

④ 获取缓存元素

思路如下：

  1. 元素不存在，直接返回-1

  2. 元素存在

    1. 将元素移到链表尾部

    2. 返回元素

代码实现：

java">public int get(int key) {//  从哈希表中查找节点ListNode node = hash.get(key);//  节点不存在，返回-1if (node == null) {return -1;}//  节点存在，将节点移动到链表尾部moveToLast(node);//  返回缓存数据return node.val;
}

⑤ 放置缓存元素

思路如下：

  1. 元素不存在

    1. 如果缓存已满，删除链表第一个元素

    2. 添加新节点到链表尾部

  2. 元素存在

    1. 将元素移动到链表尾部

    2. 更节点数据

代码实现：

java">public void put(int key, int value) {//  判断key是否存在ListNode valueNode = hash.get(key);//  元素不存在if (valueNode == null) {//  判断缓存是否到达上限if (hash.size() == capacity) {//  删除最不经常使用的节点ListNode firstNode = head.next;removeNode(firstNode);}//  添加新节点到链表尾部addNodeToBack(new ListNode(key, value));} else {//  节点存在，将节点移到尾部，并修改节点值moveToLast(valueNode);valueNode.val = value;}
}

⑥ 操作节点函数的封装

将节点放置到尾部

java">private void moveToLast(ListNode node) {//  如果节点在链表中，那么更新他的前驱与后继的指针指向if (node.pre != null && node.next != null) {ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}//  将节点插入到尾部ListNode rearPre = rear.pre;rearPre.next = node;node.pre = rearPre;node.next = rear;rear.pre = node;
}

添加节点到尾部并放入哈希表

java">private void addNodeToBack(ListNode newNode) {//	将节点移动到尾部moveToLast(newNode);//	将节点映射信息放入哈希表hash.put(newNode.key, newNode);
}

删除节点

java">private void removeNode(ListNode node) {//	移除哈希表中存储的信息hash.remove(node.key);//	移除链表中的节点ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;
}

代码实现

java">class LRUCache {private static class ListNode {public ListNode pre;public ListNode next;public int key;public int val;public ListNode() {}public ListNode(int key, int val) {this.key = key;this.val = val;}}private ListNode head;private ListNode rear;private HashMap<Integer, ListNode> hash = new HashMap<>();private final int capacity;public LRUCache(int capacity) {this.capacity = capacity;//  初始化双向链表this.head = new ListNode();this.rear = new ListNode();head.next = rear;rear.pre = head;}public int get(int key) {//  从哈希表中查找节点ListNode node = hash.get(key);//  节点不存在，返回-1if (node == null) {return -1;}//  节点存在，将节点移动到链表尾部moveToLast(node);//  返回缓存数据return node.val;}public void put(int key, int value) {//  判断key是否存在ListNode valueNode = hash.get(key);//  元素不存在if (valueNode == null) {//  判断缓存是否到达上限if (hash.size() == capacity) {//  删除最不经常使用的节点ListNode firstNode = head.next;removeNode(firstNode);}//  添加新节点到链表尾部addNodeToBack(new ListNode(key, value));} else {//  节点存在，将节点移到尾部，并修改节点值moveToLast(valueNode);valueNode.val = value;}}private void addNodeToBack(ListNode newNode) {moveToLast(newNode);hash.put(newNode.key, newNode);}private void moveToLast(ListNode node) {//  如果节点在链表中，那么更新他的前驱与后继的指针指向if (node.pre != null && node.next != null) {ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}//  将节点插入到尾部ListNode rearPre = rear.pre;rearPre.next = node;node.pre = rearPre;node.next = rear;rear.pre = node;}private void removeNode(ListNode node) {hash.remove(node.key);ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}
}


http://www.ppmy.cn/devtools/136281.html

相关文章

七次课掌握 Photoshop：绘画与修饰

七次课掌握 Photoshop：绘画与修饰

Photoshop 提供了丰富的绘画和修饰工具&#xff0c;帮助我们在数字图像中进行创作和润色。熟练掌握这些工具和方法&#xff0c;可以提升我们的图像处理和设计水平。 一、绘画类工具 1、画笔工具 快捷键&#xff1a;B 画笔工具 Brush Tool是 Photoshop 中最基本的绘画工具&#…
阅读更多...
全新三网话费余额查询API系统源码 Thinkphp全开源 附教程

全新三网话费余额查询API系统源码 Thinkphp全开源 附教程

全新三网话费余额查询API系统源码 thinkphp全开源 附教程 本套系统是用thinkphp6.0框架开发的，PHP版本需8.1以上，可查询手机号话费余额、归属地和运营商等信息，系统支持用户中心在线查询和通过API接口对接发起查询，用户余额充值是对接usdt接口或者通过后台生成卡密，源码全…
阅读更多...
利用 GitHub 和 Hexo 搭建个人博客【保姆教程】

利用 GitHub 和 Hexo 搭建个人博客【保姆教程】

利用 GitHub 和 Hexo 搭建个人博客 利用 GitHub 和 Hexo 搭建个人博客一、前言二、准备工作&#xff08;一&#xff09;安装 Node.js 和 Git&#xff08;二&#xff09;注册 GitHub 账号 三、安装 Hexo&#xff08;一&#xff09;创建博客目录&#xff08;二&#xff09;安装 H…
阅读更多...
【Linux】详解shell代码实现（上）

【Linux】详解shell代码实现（上）

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;青果大战linux 总有光环在陨落&#xff0c;总有新星在闪烁 学校开始搞蓝桥的校选…
阅读更多...
【数据结构】树——链式存储二叉树的基础

【数据结构】树——链式存储二叉树的基础

写在前面 书接上文&#xff1a;【数据结构】树——顺序存储二叉树 本篇笔记主要讲解链式存储二叉树的主要思想、如何访问每个结点、结点之间的关联、如何递归查找每个结点&#xff0c;为后续更高级的树形结构打下基础。不了解树的小伙伴可以查看上文 文章目录 写在前面 一、链…
阅读更多...
使用chrome 访问虚拟机Apache2 的默认页面，出现了ERR_ADDRESS_UNREACHABLE这个鸟问题

使用chrome 访问虚拟机Apache2 的默认页面，出现了ERR_ADDRESS_UNREACHABLE这个鸟问题

本地环境 主机MacOs Sequoia 15.1虚拟机Parallels Desktop 20 for Mac Pro Edition 版本 20.0.1 (55659)虚拟机-操作系统Ubuntu 22.04 服务器版本 最小安装 开发环境 编辑器编译器调试工具数据库http服务web开发防火墙Vim9Gcc13Gdb14Mysql8Apache2Php8.3Iptables 第一坑 数…
阅读更多...
B树的简单实现

B树的简单实现

template<class K, size_t M> struct BTreeNode {K _keys[M]; // 用于存储关键字的数组&#xff0c;最多容纳 M 个关键字&#xff08;超额一个&#xff0c;为分裂提供空间&#xff09;。BTreeNode<K, M>* _subs[M 1]; // 存储子节点的指针数组&#xff0c;最多 M1…
阅读更多...
苹果手机数据删除了怎么恢复？2种常见方法及其操作步骤

苹果手机数据删除了怎么恢复？2种常见方法及其操作步骤

苹果手机作为市场上的主流智能手机之一&#xff0c;其数据安全和恢复问题一直备受用户关注。我们在使用苹果手机的过程中&#xff0c;经常会因为误操作、系统升级、设备故障等原因导致手机数据丢失或删除。那么当苹果手机数据删除了怎么恢复呢&#xff1f;本文将详细介绍几种常…
阅读更多...
最新文章

Copyright @ 2022~2023