JavaDS —— LRUCache

概念

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。

什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有
的部分内容，从而腾出空间来放新内容。

LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

LRUCache 的运行机制

LRUCache 使用的是 哈希表加双向链表的 数据结构进行实现的，由于使用哈希表，那么查找的时间复杂度为O(1)，使用双向链表，那么在插入和删除结点的时间复杂度页为 O(1)，总体来看，LRUCache 的查找、插入以及删除的时间复杂度均为O(1)，效率十分的高
在这里插入图片描述

数据的插入是以尾插的形式进行的，如果空间不够的话，就会删除最前面的数据，然后再执行插入操作。

如果更新或者访问数据的话，就会将数据放到最后面。

因此，LRUCahche 会将经常访问的数据放在后面，将不经常访问的数据放在前面，如果插入的时候，发现空间不够，就会删除前面的数据也就是不经常访问的数据。

LinkedHashMap

在Java 中，类似LRUCahe的数据结构是 LinkedHashMap.

构造方法：
在这里插入图片描述

参数说明：
1.initialCapacity 初始容量大小，使用无参构造方法时，此值默认是16
2.loadFactor 加载因子，使用无参构造方法时，此值默认是 0.75f

3.accessOrder
false：基于插入顺序
true：基于访问顺序

解释一下 accessOrder，accessOrder 表示你有没有需求——把经常访问到的数据放到后面，把不经常访问到的数据放到前面，如果你有这个需求可以设置为 true (也就是基于访问顺序进行对数据的管理)，如果你没有这个需求，只是单纯的插入数据，那么可以指定为 false

大家页看到了还有其他一些构造方法，这些构造方法不需要指定 accessOrder，那么Java 会默认你是 基于访问顺序，也就是 accessOrder = true 来进行管理数据，毕竟 LinkedHashMap 是 LRUCache 数据结构。

演示：
asscessOrder 等于 false， 基于插入顺序管理数据。

    public static void main(String[] args) {LinkedHashMap<Integer,Character> map = new LinkedHashMap<>(5,0.7f,false);map.put(3,'c');map.put(2,'d');map.put(5,'s');map.get(2);System.out.println(map);map.get(3);System.out.println(map);}

在这里插入图片描述

accessOrder 等于 true ，基于访问顺序 管理数据：

    public static void main(String[] args) {LinkedHashMap<Integer,Character> map = new LinkedHashMap<>(5,0.7f,true);map.put(3,'c');map.put(2,'d');map.put(5,'s');System.out.println(map);map.get(2);System.out.println(map);map.get(3);System.out.println(map);}

在这里插入图片描述

模拟实现

结构定义

我们需要哈希表和双向链表两种数据结构，这里我们直接使用哈希表 HashMap，就不模拟哈希表的实现了。哈希表我们存放 key 和 Node 这两个数值，这样我们就可以通过 key 获取到 key 所在的结点了。

双向链表需要结点，我们来定义结点：

static class Node {int key;int val;Node prev;Node next;public Node(int key, int val) {this.key = key;this.val = val;}public Node() {}}

我们使用双向链表进行插入和删除的时候，可以提前定义好两个空结点，方便我们插入和删除操作，所以上面的结点里面还定义了空的构造方法。

除此之外，我们还需要两个成员变量，一个用来记录当前使用了多少的空间，另一个则是用来记录容量的大小。

    HashMap<Integer,Node> map;int useSized; //使用空间int capacity; //容量//两个辅助结点，便于插入和删除操作Node head;Node tail;

最后我们来搭建LRUCache 的两个构造方法：

    //提供构造方法public LRUCache() {capacity = 3;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}

查找

使用哈希表的 get 方法，就可以找到对应的结点。

    //查找public Node get(int key) {return map.get(key);}

删除

删除某个数值，我们先通过哈希表得到结点，然后对链表和哈希表同时进行删除操作。

    public boolean remove(int key) {Node node = get(key);if(node == null) {return false;}removeNode(node);return true;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;map.remove(node.key);}

插入

插入首先我们要找到是否已经存在 key 这个数值

如果存在，我们则需要更新数据，然后将结点插入到后面。

如果不存在，我们就需要查看当前的useSized 是不是已经达到最大容量了，如果达到最大容量，我们需要先删除前面的一个有效结点，再去插入新结点；如果没有达到最大容量，我们直接插入结点即可，同时 useSized + 1。

    //插入public void put(int key, int val) {Node node = get(key);Node newNode = new Node(key,val);if(node == null) {//如果不存在这个结点，需要插入到尾巴if(useSized == capacity) {//需要进行删除removeFrontNode();//插入insertToTail(newNode);} else {//插入insertToTail(newNode);useSized++;}} else {//如果存在这个结点，需要进行更新操作，并且最后要将结点插入到尾巴removeNode(node);insertToTail(newNode);}}

这时候剩下的就是链表的基本操作了：

    private void insertToTail(Node node) {Node prev = tail.prev;tail.prev = node;node.next = tail;node.prev = prev;prev.next = node;map.put(node.key,node);}private void removeFrontNode() {Node del = head.next;head.next = del.next;del.next.prev = head;map.remove(del.key);}

最终代码

import java.util.HashMap;public class LRUCache {HashMap<Integer,Node> map;int useSized; //使用空间int capacity; //容量//两个辅助结点，便于插入和删除操作Node head;Node tail;static class Node {int key;int val;Node prev;Node next;public Node(int key, int val) {this.key = key;this.val = val;}public Node() {}}//提供构造方法public LRUCache() {capacity = 3;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}//插入public void put(int key, int val) {Node node = get(key);Node newNode = new Node(key,val);if(node == null) {//如果不存在这个结点，需要插入到尾巴if(useSized == capacity) {//需要进行删除removeFrontNode();//插入insertToTail(newNode);} else {//插入insertToTail(newNode);useSized++;}} else {//如果存在这个结点，需要进行更新操作，并且最后要将结点插入到尾巴removeNode(node);insertToTail(newNode);}}public boolean remove(int key) {Node node = get(key);if(node == null) {return false;}removeNode(node);return true;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;map.remove(node.key);}private void insertToTail(Node node) {Node prev = tail.prev;tail.prev = node;node.next = tail;node.prev = prev;prev.next = node;map.put(node.key,node);}private void removeFrontNode() {Node del = head.next;head.next = del.next;del.next.prev = head;map.remove(del.key);}//查找public Node get(int key) {return map.get(key);}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1534627.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

eHR软件好用吗？人事管理系统的功能有哪些？

eHR软件好用吗？人事管理系统的功能有哪些？

随着科技的发展&#xff0c;企业管理方式也在不断变革。其中&#xff0c;电子人力资源管理&#xff08;eHR&#xff09;系统作为一种新兴的人力资源管理工具&#xff0c;受到了越来越多企业的关注。那么&#xff0c;eHR系统到底好不好用&#xff1f;它有哪些具体功能呢&#xf…
阅读更多...
Zotero使用（一）PDF文件导入不会自动识别

Zotero使用（一）PDF文件导入不会自动识别

上面两种&#xff0c;一种中文&#xff0c;一种英文&#xff0c;会发现&#xff0c;中文的导入进去之后不会自动识别&#xff0c;部分英文也是。不能自动识别就会缺少导出参考文献的功能&#xff0c;怎么办&#xff1f; 发现之前导入喜欢使用PDF格式 可以结合.ris格式&#xf…
阅读更多...
如何使用ssm实现基于VUE3+SSM框架的在线宠物商城+vue

如何使用ssm实现基于VUE3+SSM框架的在线宠物商城+vue

TOC ssm598基于VUE3SSM框架的在线宠物商城vue 第1章 绪论 1.1 研究背景 互联网概念的产生到如今的蓬勃发展&#xff0c;用了短短的几十年时间就风靡全球&#xff0c;使得全球各个行业都进行了互联网的改造升级&#xff0c;标志着互联网浪潮的来临。在这个新的时代&#xff…
阅读更多...
Python 课程5-NumPy库

Python 课程5-NumPy库

在数据处理和科学计算中&#xff0c;NumPy 是一个非常强大且基础的库。除了基本的创建数组功能之外&#xff0c;NumPy 提供了许多强大的函数和方法&#xff0c;用于执行高级的矩阵运算、统计分析、逻辑操作等。以下是一些常用且非常有用的 NumPy 指令&#xff0c;涵盖了创建数组…
阅读更多...
一个新目标：开始每日练习打字

一个新目标：开始每日练习打字

前言 每日10行代码写了183篇&#xff0c;比最开始预想的要多&#xff0c;但比我理想的篇数要少&#xff0c;我理想的篇数是300篇以上。 python每日学写到了18篇&#xff0c;本来是准备每日学的&#xff0c;但是架不住生活无常&#xff0c;最终还是没有达成目标&#xff0c;不过…
阅读更多...
软件研制功能点拆分

软件研制功能点拆分

最近需要进行软件研制概算明细表中的估算对象原始功能点&#xff0c;记录一下学习过程&#xff0c;共有EI(external input 外部输入)、EO(外部输出)、EQ(外部查询)、ILF(internal logic 内部逻辑文件)、EIF(外部接口文件)五个。 功能点计数项分为数据功能&#xff08;逻辑文件&…
阅读更多...
[linux基础知识]教你使用vim和ctags阅读linux内核源码

[linux基础知识]教你使用vim和ctags阅读linux内核源码

1 安装ctags apt install ctags 2 内核源码目录下添加索引 使用下面命令&#xff0c;添加索引成功后&#xff0c;内核目录下会生成tags 索引文件。 ctags -R 3 vim使用索引阅读源码 跳转到函数变量定义与返回 #跳到函数或者变量定义 Ctrl] #返回 Ctrlo 光标移动到需要…
阅读更多...
python画图|3D参数化图形输出

python画图|3D参数化图形输出

前面已经学习了基本的3D作图&#xff0c;具体链接如下&#xff1a; 基础教程&#xff1a;python画图|3D图基础教程-CSDN博客 直方图教程&#xff1a;python画图|3D直方图基础教程-CSDN博客 垂线标记教程&#xff1a;python画图|3D垂线标记-CSDN博客 3D surface教程&#xf…
阅读更多...
Kamailio-基于Homer与heplify的SIP信令监控-2

Kamailio-基于Homer与heplify的SIP信令监控-2

接上篇&#xff0c;我们已经顺利地完成了服务的安装&#xff0c;下面就来看看如何配置并启动。 跟着我&#xff0c;你将学会&#xff1a; 下载并安装 踩坑&#xff1a;按照官方步骤来&#xff0c;可是网络条件不允许 获取YUM源下载RPM包手动解压安装避坑 配置并启动&#xf…
阅读更多...
如何计算光伏在安装过程中的损耗程度？

如何计算光伏在安装过程中的损耗程度？

光伏系统在实际安装和运营过程中&#xff0c;会受到多种因素的影响&#xff0c;导致电能损耗。这些损耗包括线缆损耗、逆变器效率、组件品质、灰尘积累、入射角损失等。 一、光伏系统损耗的分类 光伏系统的损耗大致可以分为以下几类&#xff1a; 1、线缆损耗&#xff1a;光伏…
阅读更多...
文件外发怎么保证安全

文件外发怎么保证安全

为了确保文件在外发过程中的安全&#xff0c;金刚钻信息网站的防泄密系统支持以下多种措施来防止数据泄露和未经授权的访问&#xff1a; 1. 文件加密 加密文件&#xff1a;在文件外发前对其进行加密处理&#xff0c;确保只有持有解密密钥或密码的人才能访问文件内容。加密工具…
阅读更多...
uview-plus 表单校验 相关字段有数据有值的情况下非空验证失败问题

uview-plus 表单校验 相关字段有数据有值的情况下非空验证失败问题

你们好&#xff0c;我是金金金。 场景 uniapp编写h5及小程序&#xff0c;组件库用的uview-plus&#xff0c;在进行表单校验的过程中&#xff0c;数据回显 数量明明是有值的&#xff0c;还是依旧提示填写数量&#xff08;重新再次手动输入才能校验通过&#xff0c;明显是存在问题…
阅读更多...
电子电路产业园废水处理与资源回收的创新实践

电子电路产业园废水处理与资源回收的创新实践

随着电子产品的普及和技术革新步伐的加快&#xff0c;电子电路制造业已成为推动现代科技发展的关键力量之一。然而&#xff0c;随之而来的环保问题不容忽视。电镀工艺作为电子电路生产中的一个核心环节&#xff0c;其产生的含镍废水处理成为了企业必须面对的重要课题。本文将探…
阅读更多...
Oracle发邮件功能：设置的步骤与注意事项？

Oracle发邮件功能：设置的步骤与注意事项？

Oracle发邮件配置教程&#xff1f;如何实现Oracle发邮件功能&#xff1f; Oracle数据库作为企业级应用的核心&#xff0c;提供了内置的发邮件功能&#xff0c;使得数据库管理员和开发人员能够通过数据库直接发送邮件。AokSend将详细介绍如何设置Oracle发邮件功能。 Oracle发邮…
阅读更多...
悟空crm客户管理系统二次开发 单独新增表格字段

悟空crm客户管理系统二次开发 单独新增表格字段

1&#xff0c;仪表盘&#xff08;数据来源修改&#xff09; 注意点&#xff1a;有层级关系&#xff0c;管理员账号可以看到全部数据&#xff0c;主管只能看到下属数据。 2、在客户管理菜单里面 增加一个时间筛选、额度汇总 /*** 获取客户列表** param $type* param $content*…
阅读更多...
vagrant+virtualbox+ubuntu22.04无法上网问题

vagrant+virtualbox+ubuntu22.04无法上网问题

一、过程 vagrantfile配置私有网络 config.vm.network "private_network", ip: "192.168.56.10"启动虚拟机&#xff0c;可以ping通百度的实际IP&#xff0c;ping不通域名修改/etc/netplan/50-vagrant.yaml&#xff0c;配置DNS network:renderer: Networ…
阅读更多...
2024年9月一区SCI-神经种群动态优化算法NPDOA-附Matlab免费代码

2024年9月一区SCI-神经种群动态优化算法NPDOA-附Matlab免费代码

引言 本期介绍了一种受脑神经科学启发的元启发式算法&#xff0c;称为神经种群动态优化算法Neural population dynamics optimization algorithm(NPDOA)的元启发式算法。该成果于2024年9月最新发表在中科院1区 Top SCI期刊 Knowledge-Based Systems。 原文作者将NPDOA与其他9种…
阅读更多...
智慧体育场馆：科技引领未来运动体验

智慧体育场馆：科技引领未来运动体验

在当今数字化时代&#xff0c;​智慧体育场馆​的建设不仅提升了观众、运动员和管理者的体验质量&#xff0c;也为体育产业注入了新的活力和创新。通过整合先进科技和智能系统&#xff0c;体育场馆能够实现更高效的运营管理、提升赛事体验以及优化资源利用。以下是古河云科技构…
阅读更多...
JavaSE - 易错题集 - 006

JavaSE - 易错题集 - 006

1. 哪个正确 A abstract类只能用来派生子类&#xff0c;不能用来创建abstract类的对象。 B final类不但可以用来派生子类&#xff0c;也可以用来创建final类的对象。 C abstract不能与final同时修饰一个类。 D abstract类定义中可以没有abstract方法。 正确答案&#xff1…
阅读更多...
GMB外链是什么？

GMB外链是什么？

GMB外链其实就是百万外链&#xff0c;它是一种通过大量反向链接来提升网站页面权重的方法。如果你刚建了一个新网站&#xff0c;想在短时间内被收录并获得排名&#xff0c;GMB外链能帮你做到这点。它不像传统SEO那样需要等待好几个月的效果&#xff0c;GMB外链能在24小时内帮你…
阅读更多...
最新文章

Copyright @ 2022~2023