java 基于冷热数据分离的思想设计LRU链表

java 基于冷热数据分离的思想设计LRU链表

1. LRUCache 伪代码
import java.util.HashMap;
import java.util.Map;public class LRUCache {private final int capacity; // 缓存的最大容量private final Map<Integer, Node> map; // 用于快速查找节点的哈希表private final Node headHot, tailHot; // 热数据链表的头节点和尾节点private final Node headCold, tailCold; // 冷数据链表的头节点和尾节点private int hotSize, coldSize; // 热数据和冷数据的数量public LRUCache(int capacity) {this.capacity = capacity; // 初始化缓存容量this.map = new HashMap<>(); // 初始化哈希表this.headHot = new Node(0, 0); // 初始化热数据链表的头节点this.tailHot = new Node(0, 0); // 初始化热数据链表的尾节点this.headCold = new Node(0, 0); // 初始化冷数据链表的头节点this.tailCold = new Node(0, 0); // 初始化冷数据链表的尾节点headHot.next = tailHot; // 将头节点和尾节点连接起来tailHot.prev = headHot;headCold.next = tailCold; // 将头节点和尾节点连接起来tailCold.prev = headCold;this.hotSize = 0; // 初始化热数据数量为0this.coldSize = 0; // 初始化冷数据数量为0}public int get(int key) {Node node = map.get(key); // 从哈希表中查找节点if (node == null) return -1; // 如果节点不存在，返回-1if (node.isHot) {// 如果节点是热数据，将其移动到热数据链表头部removeNode(node);addToHeadHot(node);} else {// 如果节点是冷数据，将其移动到冷数据链表头部removeNode(node);addToHeadCold(node);// 如果冷数据链表的大小超过容量的一半，移除最久未使用的冷数据if (coldSize > capacity / 2) {Node lruCold = tailCold.prev;removeNode(lruCold);map.remove(lruCold.key);coldSize--;// 如果热数据链表的大小小于容量的一半，将最久未使用的冷数据提升为热数据if (hotSize < capacity / 2) {addToHeadHot(lruCold);lruCold.isHot = true;hotSize++;}}}return node.value; // 返回节点的值}public void put(int key, int value) {if (capacity == 0) return; // 如果缓存容量为0，直接返回Node node = map.get(key); // 从哈希表中查找节点if (node != null) {// 如果节点存在，更新其值node.value = value;if (node.isHot) {// 如果节点是热数据，将其移动到热数据链表头部removeNode(node);addToHeadHot(node);} else {// 如果节点是冷数据，将其移动到冷数据链表头部removeNode(node);addToHeadCold(node);// 如果冷数据链表的大小超过容量的一半，移除最久未使用的冷数据if (coldSize > capacity / 2) {Node lruCold = tailCold.prev;removeNode(lruCold);map.remove(lruCold.key);coldSize--;// 如果热数据链表的大小小于容量的一半，将最久未使用的冷数据提升为热数据if (hotSize < capacity / 2) {addToHeadHot(lruCold);lruCold.isHot = true;hotSize++;}}}} else {// 如果节点不存在，创建新节点if (hotSize + coldSize >= capacity) {// 如果缓存已满，移除最久未使用的节点if (coldSize > capacity / 2) {Node lruCold = tailCold.prev;removeNode(lruCold);map.remove(lruCold.key);coldSize--;} else {Node lruHot = tailHot.prev;removeNode(lruHot);map.remove(lruHot.key);hotSize--;}}Node newNode = new Node(key, value); // 创建新节点addToHeadHot(newNode); // 将新节点插入到热数据链表头部map.put(key, newNode); // 将新节点添加到哈希表中hotSize++; // 更新热数据数量}}private void addToHeadHot(Node node) {node.isHot = true; // 设置节点为热数据node.prev = headHot; // 将节点插入到热数据链表头部node.next = headHot.next;headHot.next.prev = node;headHot.next = node;hotSize++; // 更新热数据数量}private void addToHeadCold(Node node) {node.isHot = false; // 设置节点为冷数据node.prev = headCold; // 将节点插入到冷数据链表头部node.next = headCold.next;headCold.next.prev = node;headCold.next = node;coldSize++; // 更新冷数据数量}private void removeNode(Node node) {if (node.isHot) {hotSize--; // 如果节点是热数据，更新热数据数量} else {coldSize--; // 如果节点是冷数据，更新冷数据数量}node.prev.next = node.next; // 从链表中移除节点node.next.prev = node.prev;}private static class Node {int key; // 节点的键int value; // 节点的值boolean isHot; // 节点是否为热数据Node prev; // 前驱节点Node next; // 后继节点Node(int key, int value) {this.key = key;this.value = value;}}
}

说明
数据结构:
使用双向链表来存储热数据和冷数据。
使用哈希表来快速查找节点。
操作:
get(int key): 如果节点存在且是热数据，则将其移动到热数据链表头部；如果是冷数据，则将其移动到冷数据链表头部，并根据冷数据链表的大小决定是否将其提升为热数据。
put(int key, int value): 如果节点存在，则更新其值并根据其状态移动到相应链表的头部；如果节点不存在，则创建新节点并插入到热数据链表头部，同时根据缓存容量决定是否需要移除最久未使用的节点。
冷热数据分离:
通过维护两个链表分别存储热数据和冷数据，可以有效地分离冷热数据。
当冷数据链表的大小超过缓存容量的一半时，会将最久未使用的冷数据移除，并根据热数据链表的大小决定是否将其提升为热数据。
这种设计可以提高缓存的命中率和访问速度，特别是在访问模式存在明显冷热数据分离的情况下。

2. LRU 的单元测试
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;import static org.junit.jupiter.api.Assertions.*;public class LRUCacheTest {private LRUCache cache;@BeforeEachpublic void setUp() {cache = new LRUCache(3); // 初始化缓存容量为3}@Testpublic void testPutAndGet() {cache.put(1, 1);cache.put(2, 2);cache.put(3, 3);assertEquals(1, cache.get(1)); // 测试正常获取assertEquals(2, cache.get(2)); // 测试正常获取assertEquals(3, cache.get(3)); // 测试正常获取}@Testpublic void testEviction() {cache.put(1, 1);cache.put(2, 2);cache.put(3, 3);cache.put(4, 4); // 触发淘汰assertEquals(-1, cache.get(1)); // 测试淘汰最久未使用的元素assertEquals(2, cache.get(2)); // 测试正常获取assertEquals(3, cache.get(3)); // 测试正常获取assertEquals(4, cache.get(4)); // 测试正常获取}@Testpublic void testUpdate() {cache.put(1, 1);cache.put(2, 2);cache.put(1, 10); // 更新值assertEquals(10, cache.get(1)); // 测试更新后的值assertEquals(2, cache.get(2)); // 测试未更新的值}@Testpublic void testGetUpdatesOrder() {cache.put(1, 1);cache.put(2, 2);cache.put(3, 3);cache.get(1); // 访问1，变为最近使用cache.put(4, 4); // 触发淘汰assertEquals(1, cache.get(1)); // 测试正常获取assertEquals(-1, cache.get(2)); // 测试淘汰最久未使用的元素assertEquals(3, cache.get(3)); // 测试正常获取assertEquals(4, cache.get(4)); // 测试正常获取}@Testpublic void testCapacityZero() {LRUCache zeroCapacityCache = new LRUCache(0);zeroCapacityCache.put(1, 1);assertEquals(-1, zeroCapacityCache.get(1)); // 测试容量为0时无法存储元素}@Testpublic void testColdToHot() {cache.put(1, 1);cache.put(2, 2);cache.put(3, 3);cache.get(1); // 访问1，变为最近使用cache.get(2); // 访问2，变为最近使用cache.get(3); // 访问3，变为最近使用cache.put(4, 4); // 触发淘汰cache.put(5, 5); // 触发淘汰assertEquals(1, cache.get(1)); // 测试正常获取assertEquals(2, cache.get(2)); // 测试正常获取assertEquals(3, cache.get(3)); // 测试正常获取assertEquals(-1, cache.get(4)); // 测试淘汰最久未使用的元素assertEquals(5, cache.get(5)); // 测试正常获取}@Testpublic void testHotToCold() {cache.put(1, 1);cache.put(2, 2);cache.put(3, 3);cache.get(1); // 访问1，变为最近使用cache.get(2); // 访问2，变为最近使用cache.get(3); // 访问3，变为最近使用cache.put(4, 4); // 触发淘汰cache.get(1); // 访问1，变为最近使用cache.get(2); // 访问2，变为最近使用cache.put(5, 5); // 触发淘汰assertEquals(1, cache.get(1)); // 测试正常获取assertEquals(2, cache.get(2)); // 测试正常获取assertEquals(-1, cache.get(3)); // 测试淘汰最久未使用的元素assertEquals(4, cache.get(4)); // 测试正常获取assertEquals(5, cache.get(5)); // 测试正常获取}
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

go面试问题

go面试问题

1 Go的内存逃逸如何分析 go build -gcflags-m main_pointer.go 2 http状态码 300 请求的资源可包括多个位置&#xff0c;相应可返回一个资源特征与地址的列表用于用户终端&#xff08;例如&#xff1a;浏览器&#xff09;选择 301 永久移动。请求的资源已被永久的移动到新U…
阅读更多...
JVM性能优化一：初识内存泄露-内存溢出-垃圾回收

JVM性能优化一：初识内存泄露-内存溢出-垃圾回收

本文主要是让你充分的认识到什么叫做内存泄露&#xff0c;什么叫做内存溢出&#xff0c;别再傻傻分不清了&#xff0c;别再动不动的升级服务器的内存了。 文章目录 1.基本概念1.1.内存泄露1.2.内存溢出1.3.垃圾回收1.4.内存泄露-垃圾回收-内存溢出三者的关系关系 2.代码示例2.…
阅读更多...
安装milvus以及向量库增删改操作

安装milvus以及向量库增删改操作

首先电脑已经安装了docker windows电脑可下载yml文件 https://github.com/milvus-io/milvus/releases/download/v2.4.6/milvus-standalone-docker-compose.yml 创建milvus文件夹&#xff0c;并在这个目录下创建五个文件夹&#xff1a;conf、db、logs、pic、volumes、wal 然后…
阅读更多...
ARP..

ARP..

ARP 0 前言 真正接触到现网才发现ARP十分重要&#xff0c;无论是排错还是S-MLAG都需要用到ARP这个协议&#xff0c;以前对于ARP的理解比较混乱&#xff1b;所以这次对其中的主要内容做个梳理&#xff1b;一定要学好ARP&#xff01;&#xff01;&#xff01; 1 ARP的概念 Ar…
阅读更多...
单片机上电后程序不运行怎么排查问题？

单片机上电后程序不运行怎么排查问题？

1.电源检查。使用电压表测量单片机的电源电压是否正常&#xff0c;确保电压在规定的范围内&#xff0c;如常见的5V。 2.复位检查。检查复位引脚的电压是否正常&#xff0c;在单片机接通电源时&#xff0c;复位引脚通常会有一个高电平&#xff0c;按下复位按钮时&#xff0c;复位…
阅读更多...
SKETCHPAD——允许语言模型生成中间草图,在几何、函数、图算法和游戏策略等所有数学任务中持续提高基础模型的性能

SKETCHPAD——允许语言模型生成中间草图,在几何、函数、图算法和游戏策略等所有数学任务中持续提高基础模型的性能

概述 论文地址&#xff1a;https://arxiv.org/pdf/2406.09403 素描是一种应用广泛的有效工具&#xff0c;包括产生创意和解决问题。由于素描能直接传达无法用语言表达的视觉和空间信息&#xff0c;因此从古代岩画到现代建筑图纸&#xff0c;素描在世界各地被用于各种用途。儿童…
阅读更多...
Linux应用开发————mysql数据库表

Linux应用开发————mysql数据库表

mysql数据库表操作 查看表的结构 mysql> desc / describe 表名; 或者&#xff1a; mysql> show create table 表名; 常见数据库引擎&#xff1a; innodb, myISAM... 删除表 mysql> drop tabl…
阅读更多...
【C#】实现Json转Lua (Json2Lua)

【C#】实现Json转Lua (Json2Lua)

关键词: C#、JsonToLua、Json2Lua、对象序列化Lua 前提需引入NewtonsofJson&#xff0c;引入方法可先在Visual Studio 2019 将Newtonsoft.Json.dll文件导入Unity的Plugins下。 Json格式字符串转Lua格式字符串&#xff0c;效果如下&#xff1a; json字符串 {"1": &q…
阅读更多...
2.4 网络概念（分层、TCP）

2.4 网络概念（分层、TCP）

网络层与传输层概述 网络层&#xff1a; 抽象概念&#xff1a;网络层是基于 IP 的抽象概念&#xff0c;与数据链路层用 MAC 地址标记设备不同。MAC 地址是一种具体化的概念&#xff0c;绑定于所在的物理网络&#xff0c;而 IP 地址可以是固定的&#xff0c;也可以通过路由动态…
阅读更多...
LabVIEW伸缩臂参数监控系统

LabVIEW伸缩臂参数监控系统

LabVIEW开发伸缩臂越野叉车参数监控系统主要应用于工程机械中的越野叉车&#xff0c;以提高车辆的作业效率和故障诊断能力。系统通过PEAK CAN硬件接口和LabVIEW软件平台实现对叉车作业参数的实时监控和故障分析&#xff0c;具有良好的实用性和推广价值。 系统组成 系统主要由P…
阅读更多...
多目标优化常用方法：pareto最优解

多目标优化常用方法：pareto最优解

生产实际中的许多优化问题大都是多目标问题&#xff0c;举个例子&#xff1a;我们想换一份工资高、压力小、离家近的新工作&#xff0c;这里工资高、压力小、离家近就是我们的目标&#xff0c;显然这是一个多目标问题&#xff0c;那我们肯定想找到这三个目标同时最优的工作&…
阅读更多...
跨站脚本攻击的多种方式——以XSS-Labs为例二十关详解解题思路

跨站脚本攻击的多种方式——以XSS-Labs为例二十关详解解题思路

一、XSS-Labs靶场环境搭建 1.1、XSS介绍 跨站脚本攻击&#xff08;XSS&#xff09;_跨站脚本测试-CSDN博客https://coffeemilk.blog.csdn.net/article/details/142266454 1.2、XSS-Labs XSS-Labs是一个学习XSS攻击手法的靶场&#xff0c;方便我们系统性的学习掌握跨站脚本攻击…
阅读更多...
【win10+RAGFlow+Ollama】搭建本地大模型助手（教程+源码）

【win10+RAGFlow+Ollama】搭建本地大模型助手（教程+源码）

一、RAGFlow简介 RAGFlow是一个基于对文档深入理解的开源RAG&#xff08;Retrieval-augmented Generation&#xff0c;检索增强生成&#xff09;引擎。 主要作用&#xff1a; 让用户创建自有知识库&#xff0c;根据设定的参数对知识库中的文件进行切块处理&#xff0c;用户向大…
阅读更多...
54、库卡机器人轴的软限位设置

54、库卡机器人轴的软限位设置

步骤1&#xff1a;将用户组改为“专家”。 步骤2&#xff1a;点击“投入运行”----“售后服务”-----“软件限位开关” 步骤3&#xff1a;就可以针对每个轴修改对应的角度值&#xff0c;然后点击“保存”。
阅读更多...
0基础学前端-----CSS DAY9

0基础学前端-----CSS DAY9

0基础学前端-----CSS DAY9 视频参考&#xff1a;B站Pink老师 今天是CSS学习的第九天&#xff0c;今天开始的笔记对应Pink老师课程中的CSS第四天的内容。 本节重点&#xff1a;常见网页布局以及清除浮动 2. 常见网页布局 2.1 常见网页布局 有以下三种&#xff1a; 参考代码…
阅读更多...
【自动化】Python SeleniumUtil 工具 开启开发者模式 自动安装油猴用户脚本等

【自动化】Python SeleniumUtil 工具 开启开发者模式 自动安装油猴用户脚本等

【自动化】Python SeleniumUtil 工具 【Python】使用Selenium 操作浏览器 自动化测试 记录-CSDN博客文章浏览阅读58次。文章浏览阅读42次。【附件】Selenium chromedriver 驱动及浏览器下载。【附件】Selenium chromedriver 驱动及浏览器下载-CSDN博客。3.安装Chrome浏览器驱动…
阅读更多...
UE5 移植Editor或Developer模块到Runtime

UE5 移植Editor或Developer模块到Runtime

要将源码中的非运行时模块移植到Runtime下使用&#xff0c;个人理解就是一个解决编译报错的过程&#xff0c;先将目标模块复制到项目的source目录内&#xff0c;然后修改模块文件夹名称&#xff0c;修改模块.build.cs与文件夹名称保持一致 修改build.cs内的类名 &#xff0c;每…
阅读更多...
全志H618 Android12修改doucmentsui选中图片资源详情信息

全志H618 Android12修改doucmentsui选中图片资源详情信息

背景： 由于当前的文件管理器在我们的产品定义当中，某些界面有改动的需求，所以需要在Android12 rom中进行定制以符合当前产品定义。 需求: 进入file文件管理器后，点击选中图片资源，选中功能按钮，获取信息，不显示“调试信息(仅开发者)”；现状是，获取信息，显示“调试信…
阅读更多...
【WPS安装】WPS编译错误总结：WPS编译失败+仅编译成功ungrib等

【WPS安装】WPS编译错误总结：WPS编译失败+仅编译成功ungrib等

WPS编译错误总结&#xff1a;WPS编译失败仅编译成功ungrib等 WPS编译过程问题1&#xff1a;WPS编译失败错误1&#xff1a;gfortran: error: unrecognized command-line option ‘-convert’; did you mean ‘-fconvert’?解决方案 问题2&#xff1a;WPS编译三个exe文件只出现u…
阅读更多...
Spring（二）---基于注解的方式实现Bean管理和注入属性

Spring（二）---基于注解的方式实现Bean管理和注入属性

目录 引入 什么是注解 Spring针对Bean管理中创建对象提供的注解 用注解的方式创建对象 ①&#xff1a;编写接口和实现类 ②&#xff1a;在需要管理的类上添加Component注解&#xff08;上边四个都可以&#xff09; ③&#xff1a;编写配置文件&#xff0c;重点是开启注解…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023