浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存
作者:码农小麦 时间:2022-02-02 08:35:36
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
标签:Java,LRU,缓存
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java中transient关键字用法分析
2022-01-22 04:27:05
详解IntelliJ IDEA中TortoiseSVN修改服务器地址的方法
2023-11-25 04:51:04
![](https://img.aspxhome.com/file/2023/0/59490_0s.png)
解决fastjson从1.1.41升级到1.2.28后报错问题详解
2021-12-30 21:55:35
java中类与对象的使用详情
2023-09-27 17:10:43
Java Collection集合iterator方法解析
2022-11-17 06:43:29
Java数据结构与算法入门实例详解
2023-11-28 21:44:06
![](https://img.aspxhome.com/file/2023/0/60280_0s.png)
Spring组件开发模式支持SPEL表达式
2023-09-05 11:53:31
java isInterrupted()判断线程的实例讲解
2023-07-21 01:45:53
Mybatis MapperScannerConfigurer自动扫描Mapper接口生成代理注入到Spring的方法
2023-04-17 11:57:25
利用Spring Boot和JPA创建GraphQL API
2023-04-01 07:11:41
![](https://img.aspxhome.com/file/2023/7/69917_0s.png)
如何处理maven仓库中后缀LastUpdated文件
2022-01-21 22:15:44
@valid 无法触发BindingResult的解决
2023-08-10 09:16:12
Toolbar制作菜单条过程详解
2022-11-29 04:13:59
Hibernate实现批量添加数据的方法
2023-11-29 08:53:56
![](https://img.aspxhome.com/file/2023/5/60815_0s.jpg)
Java BufferWriter写文件写不进去或缺失数据的解决
2023-07-20 14:57:02
Struts2返回json格式数据代码实例
2023-10-12 13:15:32
详解tryAcquire()、addWaiter()、acquireQueued()
2022-07-30 10:24:05
Spring jackson原理及基本使用方法详解
2021-10-03 08:28:18
C#正则表达式分解和转换IP地址实例(C#正则表达式大全 c#正则表达式语法)
2023-07-17 07:11:25
mybatis-plus多表联查join的实现
2023-11-24 06:49:56