浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存
作者:码农小麦 发布时间:2022-02-02 08:35:36
标签:Java,LRU,缓存
LRU:Least Recently Used最近最少使用,当缓存容量不足时,先淘汰最近最少使用的数据。就像JVM垃圾回收一样,希望将存活的对象移动到内存的一端,然后清除其余空间。
缓存基本操作就是读、写、淘汰删除。
读操作时间复杂度为O(1)的那就是hash操作了,可以使用HashMap索引 key。
写操作时间复杂度为O(1),使用链表结构,在链表的一端插入节点,是可以完成O(1)操作,但是为了配合读,还要再次将节点放入HashMap中,put操作最优是O(1),最差是O(n)。
不少童鞋就有疑问了,写入时又使用map进行了put操作,为何缓存不直接使用map?没错,首先使用map存储了节点数据就是采用空间换时间,但是淘汰删除不好处理,使用map如何去记录最近最少使用(涉及到时间、频次问题)。so,使用链表可以将活跃节点移动到链表的一端,淘汰时直接从另一端进行删除。
public class LruCache<K,V> {
/** 这里简单点直接初始化了*/
private int capacity = 2;
private int size = 0;
private HashMap<K,DoubleListNode<K,V>> cache = new HashMap<>(capacity);
private DoubleListNode<K,V> lruNode = new DoubleListNode<K, V>(null,null,null,null);
private DoubleListNode<K,V> mruNode = new DoubleListNode<K, V>(null,null,null,null);
public V get(K key){
DoubleListNode<K,V> target = cache.get(key);
if (target == null) {
return null;
}
/** 使用过就移动到右侧 */
move2mru(target);
return target.value;
}
public void put(K key,V value){
if(cache.containsKey(key)){
DoubleListNode<K,V> temp = cache.get(key);
temp.value = value;
/** 使用过就移动到右侧 */
move2mru(temp);
return;
}
/** 容量满了清除左侧 */
if(size >= capacity){
evict4lru();
}
DoubleListNode<K,V> newNode = new DoubleListNode<>(mruNode,null,key,value);
if(size == 0){
lruNode.next = newNode;
}
mruNode.next = newNode;
mruNode = newNode;
cache.put(key,newNode);
size++;
}
private void move2mru(DoubleListNode<K,V> newMru){
DoubleListNode<K,V> pre = newMru.pre;
DoubleListNode<K,V> next = newMru.next;
pre.next = next;
newMru.pre = mruNode;
mruNode.next = newMru;
mruNode = newMru;
}
private void evict4lru(){
cache.remove(lruNode.next.key);
lruNode.next = lruNode.next.next;
size--;
}
public String toString(){
StringBuffer sb = new StringBuffer("lru -> ");
DoubleListNode<K,V> temp = lruNode;
while(temp!=null){
sb.append(temp.key).append(":").append(temp.value);
sb.append(" -> ");
temp = temp.next;
}
sb.append(" -> mru ");
return sb.toString();
}
public static void main(String[] args) {
LruCache<String,String> cache = new LruCache<>();
cache.put("1","1");
System.out.println(cache);
cache.get("1");
cache.put("2","2");
System.out.println(cache);
cache.put("3","3");
System.out.println(cache);
cache.put("4","4");
System.out.println(cache);
}
}
class DoubleListNode<K,V>{
K key;
V value;
DoubleListNode<K,V> pre;
DoubleListNode<K,V> next;
public DoubleListNode(K key,V value){
this.key = key;
this.value = value;
}
public DoubleListNode(DoubleListNode<K,V> pre,DoubleListNode<K,V> next,K key,V value){
this.pre = pre;
this.next = next;
this.key = key;
this.value = value;
}
}
这里使用链表,及HashMap完成了基于LRU的缓存,其中HashMap主要用来快速索引key,链表用来完成LRU机制。当然尚有许多不足,包括缓存移除remove,缓存ttl,线程安全等。
来源:https://blog.csdn.net/weixin_43275277/article/details/107740004
0
投稿
猜你喜欢
- 概述什么是动态编程?动态编程解决什么问题?Java中如何使用?什么原理?如何改进?(需要我们一起探索,由于自己也是比较菜,一般深入不到这个程
- 介绍环境配置Jdk1.8 + Tomcat8.5 + mysql + Eclispe(IntelliJ IDEA,Eclispe,MyEcl
- IDEA安装阿里巴巴编码规范插件的两种方式:在线安装和离线安装。1.在线安装:打开file-settings-Plugins.如图:搜索到点
- 什么是递归?用Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来
- java 接口回调实例详解首先官方对接口回调的定义是这样的,所谓回调:就是A类中调用B类中的某个方法C,然后B类中反过来调用A类中的方法D,
- 本文实例完成人机猜拳互动游戏的开发,供大家参考,具体内容如下阶段一:实验——分析业务,创建用户类1.分析业务,抽象出类、类的特征和行为2.创
- Java栈之链式栈存储结构实现一、链栈采用单链表来保存栈中所有元素,这种链式结构的栈称为链栈。二、栈的链式存储结构实现package com
- 本文向您展示了在 Flutter 中实现完美的验证码输入框几种不同方法。重点是什么?真实世界的 完美的验证码输入框或 PIN 输入 UI 通
- 引言♀ 小AD:明哥,我终于出了这口恶气了。♂ 明世隐:打爽了是吧。♀ 小AD:那必须的,打十盘我赢九盘,我随意。♂ 明世隐:那小朋友不是搞
- 本文实例为大家分享了java实现简单的猜数字的具体代码,供大家参考,具体内容如下题目描述:猜数字(又称 Bulls and Cows )是一
- File类File类事java.io包中唯一代表磁盘文件本身的对象。File类定义了一些与平台无关的方法来操作文件,可以通过调用File类中
- 在基于UI元素的自动化测试中, 无论是桌面的UI自动化测试,还是Web的UI自动化测试. 首先我们需要查找和识别UI
- Struts2简介Struts2是一个基于MVC设计模式的Web应用框架,它本质上相当于一个servlet,在MVC设计模式中,Struts
- Springmvc+hibernate成为现在很多人用的框架整合,最近自己也在学习摸索,由于我们在开发项目中很多项目都用到列表分页功能,在此
- 什么是Mapping同样的,我们先讲基本概念,什么是mapping,上节给大家简要的举了一个例子,还有印象吗?mapping是es中一个比较
- 1. 二叉树的顺序存储1.1 存储方式使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。一般只适合表示完全二叉树,这种方式
- static表示“全局”或者“静态”的意思,用来修饰成员变量和成员方法,也可以形成静态static代码块,但是Java语言中没有全局变量的概
- 对象内存分配与回收策略对象的内存分配,往大方向讲,就是在堆上分配〔但也可能经过JIT编译后被拆散为标量类型并间接地栈上分配),对象主要分配在
- 原理是使用LinkedHashMap来实现,当缓存超过大小时,将会删除最老的一个元组。实现代码如下所示import java.util.Li
- 做Java编程,难免会遇到多线程的开发,但是JDK8这个CompletableFuture类很多开发者目前还没听说过,但是这个类实在是太好用