LRUCache详解

article/2025/8/25 4:19:10

1.概念

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
 

2.LRUCache的实现原理

实现LRU Cache的方法和思路很多，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。

使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，

使用哈希表是因为哈希表的增删查改也是O(1)。

package test;import java.util.HashMap;
import java.util.Map;class Node {public int key;public int val;public Node prev;public Node next;public Node() {}public Node(int key, int val) {this.key = key;this.val = val;}@Overridepublic String toString() {return "Node{" +"key=" + key +", val=" + val +'}';}
}public class MyLRUCache {public Node head;public Node tail;public int usedsize;public Map<Integer, Node> cache;public int capacity;public MyLRUCache(int capacity) {this.head = new Node();this.tail = new Node();head.next = tail;tail.prev = head;cache = new HashMap<>();this.capacity = capacity;}//插入元素public void put(int key, int val) {Node node = cache.get(key);if (node == null) {Node newnode = new Node(key, val);cache.put(key, newnode);addToTail(newnode);usedsize++;//检查当前双向链表的有效数据个数 是不是超过了capacityif (usedsize > capacity) {Node removeNode = removeHead();cache.remove(removeNode.key);usedsize--;}printNodes("put");} else {//更新val的值，其实没必要node.val = val;moveTotail(node);}}//删除指定节点public void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}//移动当前节点到尾巴节点public void moveTotail(Node node) {removeNode(node);addToTail(node);}//添加到尾巴节点public void addToTail(Node node) {tail.prev.next = node;node.prev = tail.prev;node.next = tail;tail.prev = node;}//删除最近没使用的头结点public Node removeHead() {Node del = head.next;head.next = del.next;del.next.prev = head;return del;}//访问当前的key 把你访问的节点放到尾巴public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}//把最近使用的放到了尾巴moveTotail(node);printNodes("get");return node.val;}public void printNodes(String str) {System.out.println(str + " ");Node cur = head.next;while (cur != tail) {System.out.print(cur + " ");cur = cur.next;}System.out.println();}public static void main(String[] args) {MyLRUCache myLRUCache = new MyLRUCache(3);myLRUCache.put(100, 1);myLRUCache.put(200, 2);myLRUCache.put(300, 3);System.out.println("获取元素");myLRUCache.get(200);myLRUCache.get(100);System.out.println("存放元素，会删除头结点，因为头节点是最近最少使用的");myLRUCache.put(999, 9);}
}

3.jdk当中LRUCache被封装到了LinkedHashMap

package test;import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache extends LinkedHashMap<String, Integer> {public int capacity;public LRUCache(int capacity) {super(capacity, 0.75f, true);this.capacity = capacity;}@Overridepublic Integer get(Object key) {return super.getOrDefault(key, -1);}@Overridepublic Integer put(String key, Integer value) {return super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {return size() > capacity;}public static void main(String[] args) {LRUCache lruCache = new LRUCache(3);lruCache.put("a", 1);lruCache.put("b", 2);lruCache.put("c", 3);System.out.println(lruCache);System.out.println("获取元素");System.out.println(lruCache.get("b"));System.out.println(lruCache);System.out.println(lruCache.get("a"));System.out.println(lruCache);System.out.println("存放元素,会删除头结点，因为头结点是最近最少使用的");lruCache.put("d", 4);System.out.println(lruCache);}public static void main2(String[] args) {LinkedHashMap<String, Integer> linkedHashMap =new LinkedHashMap<String, Integer>(16, 0.7f, true);linkedHashMap.put("a", 1);linkedHashMap.put("b", 2);linkedHashMap.put("c", 3);System.out.println(linkedHashMap);System.out.println("获取元素");System.out.println(linkedHashMap.get("a"));System.out.println(linkedHashMap);System.out.println(linkedHashMap.get("b"));System.out.println(linkedHashMap);System.out.println(linkedHashMap.get("c"));System.out.println(linkedHashMap);//把常用的数据放到了尾巴 不常用的放在头部便于删除}public static void main1(String[] args) {LinkedHashMap<String, Integer> linkedHashMap =new LinkedHashMap<String, Integer>(16, 0.7f, false);linkedHashMap.put("a", 1);linkedHashMap.put("b", 2);linkedHashMap.put("c", 3);System.out.println(linkedHashMap);System.out.println("获取元素");System.out.println(linkedHashMap.get("a"));System.out.println(linkedHashMap);}
}

4.LRU缓存

 

class Node {public int key;public int val;public Node prev;public Node next;public Node() {}public Node(int key, int val) {this.key = key;this.val = val;}@Overridepublic String toString() {return "Node{" +"key=" + key +", val=" + val +'}';}
}public class LRUCache {public Node head;public Node tail;public int usedsize;public Map<Integer, Node> cache;public int capacity;public LRUCache(int capacity) {this.head = new Node();this.tail = new Node();head.next = tail;tail.prev = head;cache = new HashMap<>();this.capacity = capacity;}//插入元素public void put(int key, int val) {Node node = cache.get(key);if (node == null) {Node newnode = new Node(key, val);cache.put(key, newnode);addToTail(newnode);usedsize++;//检查当前双向链表的有效数据个数 是不是超过了capacityif (usedsize > capacity) {Node removeNode = removeHead();cache.remove(removeNode.key);usedsize--;}} else {//更新val的值，其实没必要node.val = val;moveTotail(node);}}//删除指定节点public void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}//移动当前节点到尾巴节点public void moveTotail(Node node) {removeNode(node);addToTail(node);}//添加到尾巴节点public void addToTail(Node node) {tail.prev.next = node;node.prev = tail.prev;node.next = tail;tail.prev = node;}//删除最近没使用的头结点public Node removeHead() {Node del = head.next;head.next = del.next;del.next.prev = head;return del;}//访问当前的key 把你访问的节点放到尾巴public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}//把最近使用的放到了尾巴moveTotail(node);return node.val;}public void printNodes(String str) {System.out.println(str + " ");Node cur = head.next;while (cur != tail) {System.out.print(cur + " ");cur = cur.next;}System.out.println();}
}


http://chatgpt.dhexx.cn/article/d0QbU1Zt.shtml

相关文章

LRUCache 详解

LRUCache 详解

LRU算法详解 一、什么是 LRU 算法 就是一种缓存淘汰策略。 计算机的缓存容量有限&#xff0c;如果缓存满了就要删除一些内容&#xff0c;给新内容腾位置。但问题是&#xff0c;删除哪些内容呢&#xff1f;我们肯定希望删掉哪些没什么用的缓存&#xff0c;而把有用的数据继续…
阅读更多...
LRU Cache

LRU Cache

前言 哈喽&#xff0c;各位小伙伴大家好&#xff0c;本章内容为大家介绍计算机当中为了提高数据相互传输时的效率而引进的一种重要设计结构叫做LRU Cache,下面将为大家详细介绍什么是LRU Cache,以及它是如何是实现的&#xff0c;如何提升效率的。 1.什么是LRU Cache? LRU是L…
阅读更多...
uniapp日历原生插件

uniapp日历原生插件

<template><!-- 打卡日历页面 --><view classall><view class"bar"><!-- 上一个月 --><view class"previous" click"handleCalendar(0)"><button class"barbtn">上一月</button><…
阅读更多...
微信小程序使用日历插件

微信小程序使用日历插件

一&#xff0c;添加插件 1&#xff0c;在你的小程序关联的微信公众平台打开 设置》第三方服务》添加插件 2&#xff0c;直接AppID&#xff08;wx92c68dae5a8bb046&#xff09;搜索到该插件并申请授权&#xff0c;授权成功即可在小程序使用 二&#xff0c;小程序使用插件 app…
阅读更多...
日历组件

日历组件

日历组件&#xff1a; <template><div class"calendar" click.stop><div class"input-wrap"><inputtype"text"v-if"dateChangeSets":placeholder"placeholder"class"input dateChangeSets middle…
阅读更多...
vue-calendar基于vue的日历插件

vue-calendar基于vue的日历插件

本文转载于https://www.cnblogs.com/zwhgithub/p/8005414.html vue-calendar-component 基于 vue 2.0 开发的轻量&#xff0c;高性能日历组件占用内存小&#xff0c;性能好&#xff0c;样式好看&#xff0c;可扩展性强原生 js 开发&#xff0c;没引入第三方库 效果 Install …
阅读更多...
实用插件（一）日历插件——My97DatePicker

实用插件（一）日历插件——My97DatePicker

注&#xff1a;My97DatePicker插件仅限pc端使用&#xff0c;若是app项目&#xff0c;建议使用ICalendar或者Mobiscroll。 &#xff08;ICalendar插件在华为手机上存在兼容性问题&#xff0c;日期不能滚动&#xff0c;但使用很简单&#xff1b;Mobiscroll使用起来较为复杂&…
阅读更多...
sys-calendar.js带节假日的日历插件

sys-calendar.js带节假日的日历插件

下载地址 sys-calendar.js带节假日的日历插件&#xff0c;代码引用比较多。 dd:
阅读更多...
jquery日历插件，可自定义日期内容

jquery日历插件，可自定义日期内容

效果图&#xff1a; 使用&#xff1a; <link href"static/css/raoCalendar.css" rel"stylesheet" type"text/css"><script src"static/js/jquery.min.js"></script> <script src"static/js/raoCalendar.js…
阅读更多...
两款超好用js日历插件（fullcalendar和zabuto_calendar）

两款超好用js日历插件（fullcalendar和zabuto_calendar）

这两款插件特别类似，其实用其中一款即可。 先展示一下我用这两款插件制作的排班系统 这个是fullcalendar插件制作的排班页面，左边新建一系列组和组员，可以将人员直接拖拽至右边的日历上，不同组以颜色区别。 这个是将上面的排班内容用zabuto_calendar插件显示出来，黄色区域…
阅读更多...
BootStrap日历插件

BootStrap日历插件

BootStrap日历插件 前端引入插件三大步骤 引入插件所需的资源文件 <%--引入BootStrap日历插件相关资源文件--%><%--按照资源文件相互依赖的顺序来引入--%><script type"text/javascript" src"jquery/jquery-1.11.1-min.js"></scrip…
阅读更多...
jQuery实现移动端手机选择日期日历插件

jQuery实现移动端手机选择日期日历插件

效果图 calendar.css html, body {color: #333;margin: 0;height: 100%;font-family: "Microsoft YaHei", "Helvetica Neue", Helvetica, Arial, Verdana, sans-serif;-webkit-font-smoothing: antialiased;-moz-osx-font-smoothing: grayscale;font-weig…
阅读更多...
uniapp日历插件

uniapp日历插件

日历插件 效果图一、使用方法二、组件编写&#xff0c;两个文件、直接上代码month.vuecalendar.vue 效果图 一、使用方法 <template><view><view class"" click"open"><text>展示日历{{value[0]}}-{{value[1]}}</text><…
阅读更多...
calendar.js多种形式日历插件

calendar.js多种形式日历插件

下载地址 calendar.js是一款强大的日历插件&#xff0c;有多种形式的日历插件&#xff0c;比如&#xff0c;选择年、选择月、范围等。 dd:
阅读更多...
日历插件：bootstrap-datetimepicker

日历插件：bootstrap-datetimepicker

1. 简述 前端插件使用步骤&#xff1a; 1)引入开发包&#xff1a;.js,.css 下载开发包&#xff0c;拷贝到项目webapp目录下 把开发包引入到jsp文件中&#xff1a;<link><script> 2)创建容器&#xff1a;<input type"text"…
阅读更多...
最棒的 10 款 jQuery 日历插件

最棒的 10 款 jQuery 日历插件

RT&#xff0c; 最棒的 10 款 jQuery 日历插件 做个记号&#xff0c;以后就不用再翻来翻去 1、JavaScript Calendar, JSCal2 地址&#xff1a;点击打开链接 2、Date Picker 地址&#xff1a;点击打开链接 3、 jQuery Frontier Calendar 地址&#xff1a;点击打开链接…
阅读更多...
vue日历插件vue-calendar

vue日历插件vue-calendar

原始效果&#xff1a; 修改后的效果&#xff1a; 接下来&#xff0c;我们使用它&#xff5e; 1.安装 npm i vue-calendar-component --save cnpm i vue-calendar-component --save //国内镜像 2.在使用到日历插件的文件中引入 import Calendar from vue-calendar-componen…
阅读更多...
使用JS实现简单的日历插件

使用JS实现简单的日历插件

实现简单的日历插件 一、简要介绍二、基础代码html部分js部分 一、简要介绍 实现一个如下图所示的日历&#xff0c;这边主要提供html部分和js部分的代码&#xff0c;css部分大家自行编写哦。 二、基础代码 html部分 其实就是一个div容器&#xff0c;为其设置相应的id值。 <…
阅读更多...
FullCalendar - 开源的多功能 JavaScript 日历插件

FullCalendar - 开源的多功能 JavaScript 日历插件

本文字数&#xff1a;747 字 9图 阅读完需&#xff1a;约 4 分钟 点击上方“青年码农”关注 回复“源码”可获取各种资料 FullCalendar 是一个支持 React、Vue、Angular 和原生 JavaScript 的日历插件&#xff0c;FullCalendar 拥有超过 300 种设置&#xff0c;支持模块化导入&…
阅读更多...
HTML页面日历插件

HTML页面日历插件

web页面显示日历插件。如下图 <!DOCTYPE html> <html><head><meta charset"utf-8" /><title></title><style>body,td,.p1,.p2,.i {font-family: arial}body {margin: 6px 0 0 0;background-color: #fff;color: #000;}tab…
阅读更多...
推荐文章

Copyright @ 2022~2023