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

目录
  • LRU概述
  • 使用LinkedHashMap实现
  • 使用LinkedHashMap简单方法实现
  • 双链表+hashmap

LRU概述

最近使用的放在前面,最近没用的放在后面,如果来了一个新的数,此时内存满了,就需要把旧的数淘汰,那为了方便移动数据,肯定就得使用链表类似的数据结构,再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构。

使用LinkedHashMap实现

package thread;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheTest {
    int capacity;
    Map<Integer,Integer> map;

    public LRUCacheTest(int capacity){
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }

    public int get(int key){
        //没有找到
       if(!map.containsKey(key)){
          return -1;
       }
       Integer value = map.remove(key);
       map.put(key,value);
       return value;
    }

    public void put(int key,int value){
        if(map.containsKey(key)){
           map.remove(key);
           map.put(key,value);
           return;
        }
        map.put(key,value);
        //超出capacity,删除最久没用的即第一个,或者可以复写removeEldestEntry方法
        if(map.size() > capacity){
           map.remove(map.entrySet().iterator().next().getKey());
        }

    }

    public static void main(String[] args) {
        LRUCacheTest lruCache = new LRUCacheTest(10);
        for (int i = 0; i < 10; i++) {
            lruCache.map.put(i,i);
            System.out.print(lruCache.map.size()+"\t");
        }
        System.out.println();
        System.out.println(lruCache.map);
        lruCache.put(10,200);
        System.out.println(lruCache.map);
        lruCache.put(11,100);
        System.out.println(lruCache.map);
        lruCache.get(2);
        System.out.println(lruCache.map);
    }

}

结果来看是正确的,距离当前时间最远的数据被淘汰

使用LinkedHashMap简单方法实现

LinkedHashMap是维护了双向链表的HashMap,保持了插入元素的顺序。

LinkedHashMap提供了一个钩子方法,在新插入元素后可以决定是否删除最老的元素。

复写removeEldestEntry实现

package thread;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUByLinkedHashMap extends LinkedHashMap<Integer,Integer> {
    /**
     * LRU中最大元素数量
     */
    private int maxSize;

    public LRUByLinkedHashMap(int maxSize) {
        // 容量为最大值/0.75,即最大负载容量为maxSize
        // accessOrder=true  根据查询排序,即最近被使用的放到后面
        super((int) Math.ceil(maxSize / 0.75) + 1, 0.75f, true);
        this.maxSize = maxSize;
    }

    /**
     * 此方法为钩子方法,map插入元素时会调用此方法
     * 此方法返回true则证明删除最老的因子
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRUByLinkedHashMap hashMap = new LRUByLinkedHashMap(10);
        for (int i = 0; i < 10; i++) {
            hashMap.put(i,i);
            System.out.print(hashMap.size()+"\t");
        }
        System.out.println();
        System.out.println(hashMap);
        hashMap.put(10,200);
        System.out.println(hashMap);
        hashMap.put(11,100);
        System.out.println(hashMap);
        hashMap.get(10);
        System.out.println(hashMap);
    }

}

双链表+hashmap

package thread;
import java.util.HashMap;
import java.util.Map;

public class LRURedis {
    private int capacity;
    private Map<Integer,ListNode> map;
    private ListNode head;
    private ListNode tail;

    public LRURedis(int capacity){
      this.capacity = capacity;
      map = new HashMap<>();
      head = new ListNode(-1,-1);
      tail = new ListNode(-1,-1);
      head.next = tail;
      tail.pre = head;
    }

    public int get(int key){
        if(!map.containsKey(key)){
           return -1;
        }
        ListNode node = map.get(key);
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node.val;
    }

    public void put(int key,int value){
        if (get(key)!=-1){
            map.get(key).val = value;
            return;
        }

        ListNode node = new ListNode(key,value);
        map.put(key,node);
        moveToTail(node);

        if (map.size() > capacity){
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }

    }

    //把节点移动到尾巴
    private void moveToTail(ListNode node) {
        node.pre = tail.pre;
        tail.pre = node;
        node.pre.next = node;
        node.next = tail;
    }

    //定义双向链表节点
    private class ListNode{
        int key;
        int val;
        ListNode pre;
        ListNode next;

        //初始化双向链表
        public ListNode(int key,int val){
          this.key = key;
          this.val = val;
          pre = null;
          next = null;
        }
    }
}

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

(0)

相关推荐

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

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

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

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

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

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

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

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

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

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

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

  • 浅谈Java分布式架构下如何实现分布式锁

    01分布式锁运用场景 互联网秒杀,抢优惠卷,接口幂等性校验.咱们以互联网秒杀为例. @RestController @Slf4j publicclassIndexController{ @Autowired privateRedissonredission; @Autowired privateStringRedisTemplatestringRedisTemplate; @RequestMapping("/deduct_stock") publicStringdeductStock(

  • 浅谈Java开发架构之领域驱动设计DDD落地

    目录 一.前言 二.开发目标 三.服务架构 3.1.应用层{application} 3.2.领域层{domain} 3.3.基础层{infrastructrue} 3.4.接口层{interfaces} 四.开发环境 五.代码示例 六.综上总结 一.前言 整个过程大概是这样的,开发团队和领域专家一起通过 通用语言(Ubiquitous Language)去理解和消化领域知识,从领域知识中提取和划分为一个一个的子领域(核心子域,通用子域,支撑子域),并在子领域上建立模型,再重复以上步骤,这样周而

  • 浅谈java接口的幂等性及解决方案

    目录 一.什么情况下需要幂等 二.幂等性解决方案 2.1 token机制(令牌) 2.2 各种锁机制 2.3 各种唯一约束 2.4 防重表 2.5 全局请求唯一id 总结 一.什么情况下需要幂等 用户多次点击按钮 用户页面回退再次提交 微服务相互调用,由于网络问题,导致请求失败,feign触发重试机制 二.幂等性解决方案 2.1 token机制(令牌) 在加载页面详情时候,服务器会顺便生成一个token一起返回给前端,服务端同时也在Redis中保存这个token数据,前端并不展示这个token,

  • 浅谈内存耗尽后Redis会发生什么

    前言 作为一台服务器来说,内存并不是无限的,所以总会存在内存耗尽的情况,那么当 Redis 服务器的内存耗尽后,如果继续执行请求命令,Redis 会如何处理呢? 内存回收 使用Redis 服务时,很多情况下某些键值对只会在特定的时间内有效,为了防止这种类型的数据一直占有内存,我们可以给键值对设置有效期.Redis 中可以通过 4 个独立的命令来给一个键设置过期时间: expire key ttl:将 key 值的过期时间设置为 ttl 秒. pexpire key ttl:将 key 值的过期时

  • 浅谈Java中Unicode的编码和实现

    Unicode的编码和实现 大概来说,Unicode编码系统可分为编码方式和实现方式两个层次. 编码方式 字符是抽象的最小文本单位.它没有固定的形状(可能是一个字形),而且没有值."A"是一个字符,"€"也是一个字符.字符集是字符的集合.编码字符集是一个字符集,它为每一个字符分配一个唯一数字. Unicode 最初设计是作为一种固定宽度的 16 位字符编码.也就是每个字符占用2个字节.这样理论上一共最多可以表示216(即65536)个字符.上述16位统一码字符构成基

  • 浅谈java常量池

    java常量池技术 java中常量池技术说的通俗点就是java级别的缓存技术,方便快捷的创建一个对象.当需要一个对象时,从池中去获取(如果池中没有,就创建一个并放入池中),当下次需要相同变量的时候,不用重新创建,从而节省空间. java八种基本类型的包装类和对象池 java中的基本类型的包装类.其中Byte.Boolean.Short.Character.Integer.Long实现了常量池技术,(除了Boolean,都只对小于128的值才支持) 比如,Integer对象 Integer i1

随机推荐