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

一、什么是 LRU 算法

就是一种缓存淘汰策略。

计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。

二、LRU的使用

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);    // 返回 1
    cache.put(3, 3);  // 该操作会使得密钥 2 作废

第一步:创建一个长度为2的LRUCache

第二步:cache.put(1, 1);放入key=1,value=1的数据

第三步:cache.put(2,2);放入key = 2,value = 2的数据
(因为2刚使用,所有把2移动到前面)

第四步:cache.get(1);获取key = 1的数据
(因为我们刚使用了1,所以把1移动到前面)

第五步:cache.put(3,3);放入key = 3,value = 3的数据
(因为3刚放进,所以放前面,又因为容量只有2,需要移除原先的1个。只因key = 2是最近最少使用的(key = 1刚get()过),所以移除2。

三、LRU的实现机制

算法:

LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

1)双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。

2)哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。

一、初始化:

二、cache.put(1,1):

三、cache.put(2,2):

四、cache.get(1):

五、cache.put(3,3):

四、代码如下

import java.io.*;
import java.util.HashMap;

public class test {

  public static void main(String args[]) throws IOException {

    LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);    // 返回 1
    cache.put(3, 3);  // 该操作会使得密钥 2 作废
    cache.get(2);    // 返回 -1 (未找到)
    cache.put(4, 4);  // 该操作会使得密钥 1 作废
    cache.get(1);    // 返回 -1 (未找到)
    cache.get(3);    // 返回 3
    cache.get(4);    // 返回 4
  }
}

/**
 * 设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put
 */
class LRUCache {

  private HashMap<Integer,LinkedNode> cache = new HashMap();//方便通过key快速定位结点
  private int size;
  private int capacity;
  private LinkedNode head,tail;
  class LinkedNode{
    int key;
    int value;
    LinkedNode pre;
    LinkedNode next;
  }
  public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;
    head = new LinkedNode();
    tail = new LinkedNode();
    head.next = tail;
    tail.pre = head;
  }

  /**
   * 移除节点
   * @param node
   */
  private void removeNode(LinkedNode node) {
    LinkedNode preNode = node.pre;
    LinkedNode nextNode = node.next;
    preNode.next = nextNode;
    nextNode.pre = preNode;
  }

  /**
   * 添加节点到头部
   * @param node
   */
  private void addNode(LinkedNode node) {
    node.pre = head;
    node.next = head.next;
    head.next.pre = node;
    head.next = node;
  }

  /**
   * 将节点移动到头部
   * @param node
   */
  private void moveToHead(LinkedNode node) {
    removeNode(node);
    addNode(node);
  }

  /**
   * 获取数据
   * @param key
   * @return
   */
  public int get(int key) {
    LinkedNode node = cache.get(key);
    if(node != null) {
      moveToHead(node);
    }else{
      return -1;
    }
    return node.value;
  }

  /**
   * 写入数据
   * @param key
   * @param value
   */
  public void put(int key, int value) {
    LinkedNode node = cache.get(key);
    //存在
    if(node != null) {
      node.value = value;//可能更新数据
      moveToHead(node);
    }
    //不存在
    else{
      LinkedNode newNode = new LinkedNode();
      newNode.key = key;
      newNode.value = value;
      cache.put(key,newNode);//更新Map
      addNode(newNode);//添加结点到头部
      size++;//更新结点数
      if(size > capacity) {//如果结点数超过容量大小
        LinkedNode tailPre = tail.pre;
        cache.remove(tailPre.key);//更新Map
        removeNode(tailPre);//删除最后一个结点(尾结点的前一个结点)
        size--;
      }
    }
  }
}

总结:自己实现的简单LRU总归太简单了,要是想完善或者实现更真实的LRU,不妨参考一下Redis中的LRU。(◔◡◔)

到此这篇关于Java实现简单LRU缓存机制的方法的文章就介绍到这了,更多相关Java LRU缓存内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

  • 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缓存的实例详解

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

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

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

  • Java手动实现Redis的LRU缓存机制

    前言 最近在逛博客的时候看到了有关Redis方面的面试题,其中提到了Redis在内存达到最大限制的时候会使用LRU等淘汰机制,然后找了这方面的一些资料与大家分享一下. LRU总体大概是这样的,最近使用的放在前面,最近没用的放在后面,如果来了一个新的数,此时内存满了,就需要把旧的数淘汰,那为了方便移动数据,肯定就得使用链表类似的数据结构,再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构. 第一种实现(使用LinkedHashMap) pub

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

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

  • spring-boot整合ehcache实现缓存机制的方法

    EhCache 是一个纯Java的进程内缓存框架,具有快速.精干等特点,是Hibernate中默认的CacheProvider. ehcache提供了多种缓存策略,主要分为内存和磁盘两级,所以无需担心容量问题. spring-boot是一个快速的集成框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程.该框架使用了特定的方式来进行配置,从而使开发人员不再需要定义样板化的配置. 由于spring-boot无需任何样板化的配置文件,所以spring-boot集成一些其他框架时会有略微的

  • 手动实现Redis的LRU缓存机制示例详解

    前言 最近在逛博客的时候看到了有关Redis方面的面试题,其中提到了Redis在内存达到最大限制的时候会使用LRU等淘汰机制,然后找了这方面的一些资料与大家分享一下. LRU总体大概是这样的,最近使用的放在前面,最近没用的放在后面,如果来了一个新的数,此时内存满了,就需要把旧的数淘汰,那为了方便移动数据,肯定就得使用链表类似的数据结构,再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构. 第一种实现(使用LinkedHashMap) pub

  • Java 手写LRU缓存淘汰算法

    概述 LRU 算法全称为 Least Recently Used 是一种常见的页面缓存淘汰算法,当缓存空间达到达到预设空间的情况下会删除那些最久没有被使用的数据 . 常见的页面缓存淘汰算法主要有一下几种: LRU 最近最久未使用 FIFO 先进先出置换算法 类似队列 OPT 最佳置换算法 (理想中存在的) NRU Clock 置换算法 LFU 最少使用置换算法 PBA 页面缓冲算法 LRU 的原理 LRU 算法的设计原理其实就是计算机的 局部性原理(这个 局部性原理 包含了 空间局部性 和 时间

  • java编程简单获取图片像素的方法

    本文实例讲述了java获取图片像素的方法.分享给大家供大家参考,具体如下: package cn.net.comsys.sso; import java.awt.image.BufferedImage; import javax.imageio.ImageIO; import java.io.*; public class Test { public static void main(String args[]) { File file = new File("a.bmp"); Buf

  • JAVA项目字典与缓存搭配使用方法解析

    字典数据是什么? 这里说了字典不是软件工程中说的数据字典. 字典数据:用于动态设置某对象的属性是属于在一个可列举的数据范围内的某一类型数据,使用字典类型作为该类别属性的唯一标识 如:用户类型:学生,老师,家长,校长等 有什么作用? 字典数据由两个表组成:字典类型表 dict_type,字典类型数据表 dict_data 这个数据相当于java中的枚举类,可以被使用于前端的数据展示,下拉框数据集使用. 没有数据字典时业务操作方法: 定义学生枚举类,在代码中使用枚举类的key进行数据保存,在查询数据

  • 详解Java实现LRU缓存

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

  • 详解springboot整合ehcache实现缓存机制

    EhCache 是一个纯Java的进程内缓存框架,具有快速.精干等特点,是Hibernate中默认的CacheProvider. ehcache提供了多种缓存策略,主要分为内存和磁盘两级,所以无需担心容量问题. spring-boot是一个快速的集成框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程.该框架使用了特定的方式来进行配置,从而使开发人员不再需要定义样板化的配置. 由于spring-boot无需任何样板化的配置文件,所以spring-boot集成一些其他框架时会有略微的

随机推荐