浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存

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,线程安全等。

到此这篇关于浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存的文章就介绍到这了,更多相关Java基于LRU时间复杂度为O(1)的缓存内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java和Android的LRU缓存及实现原理

    一.概述 Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存.Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU算法. 二.Java的LRU算法 Java的LRU算法的基础是LinkedHashMap,LinkedHashMap继承了HashMap,并且在HashMap的基础上进行了一定的改动,以实现LRU算法. 1.Hash

  • Java实现简单LRU缓存机制的方法

    一.什么是 LRU 算法 就是一种缓存淘汰策略. 计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置.但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用. LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰. 二.LRU的使用 LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1,

  • Java实现LRU缓存的实例详解

    Java实现LRU缓存的实例详解 1.Cache Cache对于代码系统的加速与优化具有极大的作用,对于码农来说是一个很熟悉的概念.可以说,你在内存中new 了一个一段空间(比方说数组,list)存放一些冗余的结果数据,并利用这些数据完成了以空间换时间的优化目的,你就已经使用了cache. 有服务级的缓存框架,如memcache,Redis等.其实,很多时候,我们在自己同一个服务内,或者单个进程内也需要缓存,例如,lucene就对搜索做了缓存,而无须依赖外界.那么,我们如何实现我们自己的缓存?还

  • 详解Java实现缓存(LRU,FIFO)

    现在软件或者网页的并发量越来越大了,大量请求直接操作数据库会对数据库造成很大的压力,处理大量连接和请求就会需要很长时间,但是实际中百分之80的数据是很少更改的,这样就可以引入缓存来进行读取,减少数据库的压力. 常用的缓存有Redis和memcached,但是有时候一些小场景就可以直接使用Java实现缓存,就可以满足这部分服务的需求. 缓存主要有LRU和FIFO,LRU是Least Recently Used的缩写,即最近最久未使用,FIFO就是先进先出,下面就使用Java来实现这两种缓存. LR

  • 详解Java实现LRU缓存

    LRU是Least Recently Used 的缩写,翻译过来就是"最近最少使用",LRU缓存就是使用这种原理实现,简单的说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉,比如我们缓存10000条数据,当数据小于10000时可以随意添加,当超过10000时就需要把新的数据添加进来,同时要把过期数据删除,以确保我们最大缓存10000条,那怎么确定删除哪条过期数据呢,采用LRU算法实现的话就是将最老的数据删掉,废话不多说,下面来说下Java版的LRU缓存实现 Java里

  • Java资源缓存 之 LruCache

    例如对 网络加载图片进行缓存 : // 得到 应用程序 被分配的最大的内存 int maxMemory=(int) Runtime.getRuntime().maxMemory(); // 取处内存的 1/5 用来当 缓存 大小 int cachSize=maxMemory/5; // 实例化 LruCache lruCache=new lruCache<String, Bitmap>(cachSize){ //内部方法sizeOf设置每一张图片的缓存大小 protected int size

  • 浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存

    LRU:Least Recently Used最近最少使用,当缓存容量不足时,先淘汰最近最少使用的数据.就像JVM垃圾回收一样,希望将存活的对象移动到内存的一端,然后清除其余空间. 缓存基本操作就是读.写.淘汰删除. 读操作时间复杂度为O(1)的那就是hash操作了,可以使用HashMap索引 key. 写操作时间复杂度为O(1),使用链表结构,在链表的一端插入节点,是可以完成O(1)操作,但是为了配合读,还要再次将节点放入HashMap中,put操作最优是O(1),最差是O(n). 不少童鞋就

  • 浅谈java如何实现Redis的LRU缓存机制

    目录 LRU概述 使用LinkedHashMap实现 使用LinkedHashMap简单方法实现 双链表+hashmap LRU概述 最近使用的放在前面,最近没用的放在后面,如果来了一个新的数,此时内存满了,就需要把旧的数淘汰,那为了方便移动数据,肯定就得使用链表类似的数据结构,再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构. 使用LinkedHashMap实现 package thread; import java.util.Link

  • 浅谈Java线程间通信之wait/notify

    Java中的wait/notify/notifyAll可用来实现线程间通信,是Object类的方法,这三个方法都是native方法,是平台相关的,常用来实现生产者/消费者模式.先来我们来看下相关定义: wait() :调用该方法的线程进入WATTING状态,只有等待另外线程的通知或中断才会返回,调用wait()方法后,会释放对象的锁. wait(long):超时等待最多long毫秒,如果没有通知就超时返回. notify() :通知一个在对象上等待的线程,使其从wait()方法返回,而返回的前提

  • 浅谈java Collection中的排序问题

    这里讨论list.set.map的排序,包括按照map的value进行排序. 1)list排序 list排序可以直接采用Collections的sort方法,也可以使用Arrays的sort方法,归根结底Collections就是调用Arrays的sort方法. public static <T> void sort(List<T> list, Comparator<? super T> c) { Object[] a = list.toArray(); Arrays.

  • 浅谈Java 对于继承的初级理解

    概念:继承,是指一个类的定义可以基于另外一个已存在的类,即子类继承父类,从而实现父类的代码的重用.两个类的关系:父类一般具有各个子类共性的特征,而子类可以增加一些更具个性的方法.类的继承具有传递性,即子类还可以继续派生子类,位于上层的类概念更加抽象,位于下层的类的概念更加具体. 1.定义子类: 语法格式 [修饰符] class 子类名 extends 父类名{ 子类体 } 修饰符:public private protected default 子类体是子类在继承父类的内容基础上添加的新的特有内

  • 浅谈java指令重排序的问题

    指令重排序是个比较复杂.觉得有些不可思议的问题,同样是先以例子开头(建议大家跑下例子,这是实实在在可以重现的,重排序的概率还是挺高的),有个感性的认识 /** * 一个简单的展示Happen-Before的例子. * 这里有两个共享变量:a和flag,初始值分别为0和false.在ThreadA中先给 a=1,然后flag=true. * 如果按照有序的话,那么在ThreadB中如果if(flag)成功的话,则应该a=1,而a=a*1之后a仍然为1,下方的if(a==0)应该永远不会为 * 真,

  • 浅谈java中OO的概念和设计原则(必看)

    一.OO(面向对象)的设计基础 面向对象(OO):就是基于对象概念,以对象为中心,以类和继承为构造机制,充分利用接口和多态提供灵活性,来认识.理解.刻划客观世界和设计.构建相应的软件系统.面向对象的特征:虽然各种面向对象编程语言相互有别,但都能看到它们对面向对象基本特征的支持, 即 "抽象.封装.继承.多态" : – 抽象,先不考虑细节 – 封装,隐藏内部实现 – 继承,复用现有代码 – 多态,改写对象行为 面向对象设计模式:是"好的面向对象设计",所谓"

  • 浅谈Java中常用数据结构的实现类 Collection和Map

    线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中.本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一个C

  • 浅谈java面向对象(类,封装,this,构造方法)

    无论面向对象还是面向过程, 这俩都是解决问题的思路而已, 只是角度不同. 面向过程: 强调解决问题的每一个步骤都亲力亲为,每一个细节都自己手动实现. 面向对象: 使用特定功能对象去解决特定的问题, 每一个细节不需要关注,只需要创建对应的对象即可. 面向对象是基于面向过程的 类和对象及他们的关系 类: 具有相同特征和行为(功能)的事物的统称 , 是一个抽象概念 对象: 这类事物中某个确定的个体 类和对象的关系 一个类可以创建多个对象 , 类是对象的抽象, 对象是类的实例. 描述一个事物---->

  • 浅谈Java继承中的转型及其内存分配

    看书的时候被一段代码能凌乱啦,代码是这样的: package 继承; abstract class People { public String tag = "疯狂Java讲义"; //① public String name = "Parent"; String getName(){ return name; } } class Student extends People { //定义一个私有的tag实例变量来隐藏父类的tag实例变量 String tag =

随机推荐