【算法】用JAVA代码实现LRU 【缓存】【LRU】

这篇具有很好参考价值的文章主要介绍了【算法】用JAVA代码实现LRU 【缓存】【LRU】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LRU(Least Recently Used)是一种常见的缓存淘汰策略,用于在缓存空间不足时确定哪些数据应该被淘汰。其基本原则是淘汰最近最少被访问的数据。
工作原理
最近使用优先
LRU算法基于这样的思想:最近被使用的数据很可能在短时间内还会被使用,因此保留这些数据有助于提高缓存命中率。
缓存访问时机更新
每当缓存中的数据被访问,就将该数据移到最近使用的位置,通常是放到缓存的最前面或最后面。
淘汰最久未使用的数据
当缓存空间达到容量上限时,需要淘汰数据以腾出空间。
LRU会选择淘汰最久未被访问的数据,即位于缓存队列末尾的数据。文章来源地址https://www.toymoban.com/news/detail-817328.html

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1

到了这里,关于【算法】用JAVA代码实现LRU 【缓存】【LRU】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【golang项目-GeeCache】动手写分布式缓存 day1 - 实现LRU算法

    【go项目-geecache】动手写分布式缓存 - day1 - 实现LRU算法 【go项目-geecache】动手写分布式缓存 - day2 - 单机并发缓存 【go项目-geecache】动手写分布式缓存 - day3 - HTTP 服务端 【go项目-geecache】动手写分布式缓存 - day4 - 一致性哈希(hash) 【go项目-geecache】动手写分布式缓存 - day5 - 分布

    2023年04月20日
    浏览(39)
  • 缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

    CMU 15-445 (FALL 2022) Project #1 Task#2 LRU-K 替换策略详解实现,尽量提供思路,也可以为其他同学实现LRU-K算法做参考 参考文献:The LRU-K page replacement algorithm for database disk buffering (acm.org) 在网上都找不到其他参考,只有这一篇1993年的论文 LRU-K替换策略 LRU-K是LRU算法的一种衍生。强烈

    2023年04月12日
    浏览(37)
  • LRU 缓存淘汰算法

    Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。 接收一个参数 capacity 作为缓存的最大容量 实现一个函数 put() 添加数据到缓存 实现一个函数 get() 查询缓存中的数据 以上函数应该在 (O(1)) 的时间内完成 满足以上需求的数据结构 —

    2024年02月11日
    浏览(60)
  • 操作系统实验:页面置换算法——FIFO、LRU 代码实现

            最简单的页面置换算法是FIFO。 在分配内存页面数( AP )小于进程页面数( PP )时,最先运行的 AP个页面放入内存;当内存分配页面被占满时,如果 又需要处理新的页面,则将原来放的内存中的AP个页中 最先进入 的调出(FIFO),再将新页面放入;所使用的内存

    2024年02月08日
    浏览(34)
  • 初识Go语言25-数据结构与算法【堆、Trie树、用go中的list与map实现LRU算法、用go语言中的map和堆实现超时缓存】

      堆是一棵二叉树。大根堆即任意节点的值都大于等于其子节点。反之为小根堆。   用数组来表示堆,下标为 i 的结点的父结点下标为(i-1)/2,其左右子结点分别为 (2i + 1)、(2i + 2)。 构建堆   每当有元素调整下来时,要对以它为父节点的三角形区域进行调整。 插入元素

    2024年02月12日
    浏览(59)
  • Python算法题集_LRU 缓存

    本文为Python算法题集之一的代码示例 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果 key 存在于缓存中,则返回的值,否则返回 -1 。 void put(int

    2024年02月21日
    浏览(42)
  • 【算法训练-模拟 一】模拟设计LRU缓存结构

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是LRU缓存结构设计,这类题目出现频率还是很高的,几乎所有大厂都常考。 当然面对这道题,首先要讲清楚LRU是干什么的 LRU(Least Recently Used)缓存结构是一种常见的缓存管理策略, 用于

    2024年02月10日
    浏览(53)
  • LRU算法与Caffeine、Redis中的缓存淘汰策略

    在现代计算机系统中,缓存是提高系统性能的关键技术之一。为了避免频繁的IO操作,常见的做法是将数据存储在内存中的缓存中,以便快速访问。然而,由于内存资源有限,缓存的大小是有限的,因此需要一种策略来淘汰缓存中的数据,以便为新的数据腾出空间。本文将介

    2024年02月12日
    浏览(40)
  • 【数据结构】LRU缓存的简单模拟实现(leetcode力扣146LRU缓存)

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

    2024年02月03日
    浏览(43)
  • 页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]

    ⌛️ Page Replacement Algorithm ⌨️ ◆ 对上图说明 :后面分别用四种算法,对该样例都进行了检验,结果一致。 ● 后文代码的常见变量 :    [1] n :物理页框数。    [2] len :地址走向的长度。    [3] save_Frame :含有 n 个格子的物理页框(即一个长度为 n 的动态数组,指针

    2024年02月06日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包