java实现LRU缓存淘汰算法的方法

LRU算法:最近最少使用淘汰算法(Least Recently Used)。LRU是淘汰最长时间没有被使用的缓存(即使该缓存被访问的次数最多)。

如何实现LRU缓存淘汰算法
场景:

我们现在有这么个真实场景,我在爬取某个网站时,控制该网站的代理IP并发数,太多会搞垮对方网站的对吧,要蹲号子的呢。这里我需要维护一个代理IP代理池,而且这些IP肯定不是一直都很稳定的,但是又不能取一个就丢一个,这样太浪费资源。所以我会将这些IP缓存起来,进行按需提取,采用LRU最近最少使用的策略去管理代理IP。

代码如下:

import java.util.*;

public class LRUCache {

    int cap;//最大缓存的数量
    Map<String, String> values;//缓存
    Set<String> position;//缓存的key,按照存入的顺序存储

    public LRUCache(int cap) {
        this.cap = cap;
        values = new HashMap<>(cap);
        position = new LinkedHashSet<>(cap);
    }

    /**
     * 从缓存中获取值,缓存中没有则返回null
     */
    public String get(String key) {
        String value = null;
        if (values.containsKey(key)) {
            value = values.get(key);
            position.remove(key);
            position.add(key);
        }
        return value;
    }

    /**
     * 将值放入缓存中
     */
    public void put(String key, String value) {
        if (position.size() == cap) {
            //若达到缓存上限则将距今最久的缓存删除
            String firstKey = position.iterator().next();
            position.remove(firstKey);
            values.remove(firstKey);
        }
        position.add(key);
        values.put(key, value);
    }

    public Map<String, String> getValues() {
        return values;
    }

    public Set<String> getPosition() {
        return position;
    }
}

测试:

        LRUCache lruCache = new LRUCache(4);
        lruCache.put("a","a");
        lruCache.put("b","b");
        lruCache.put("c","c");
        lruCache.put("d","d");
        System.out.println("position:"+lruCache.getPosition());
        System.out.println("values:"+lruCache.getValues());

        //a将被淘汰
        lruCache.put("e","e");
        System.out.println("position:"+lruCache.getPosition());
        System.out.println("values:"+lruCache.getValues());

输出:

position:[a, b, c, d]
values:{a=a, b=b, c=c, d=d}
position:[b, c, d, e]
values:{b=b, c=c, d=d, e=e}

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

(0)

相关推荐

  • JAVA实现LRU算法的参考示例

    LRU简介 LRU是Least Recently Used 近期最少使用算法,它就可以将长时间没有被利用的数据进行删除. 实现 最近面了阿里的外包吧,居然也要在线敲代码了,那叫一个紧张啊.题目就是实现一个LRU算法的缓存.外包居然要求也这么高了,哎.还好,LRU是我大学老师布置的一道题目,当然我用C语言实现的,算法原理那是一清二楚,可是面试的时候就脑子一片空白了.好在,边敲代码,边思考,就慢慢想起来了,下面是我的代码.仅供参考 /** * 设计和构建一个"最近最少使用"LRU 缓存,该

  • java LRU算法介绍与用法示例

    本文实例讲述了java LRU算法介绍与用法.分享给大家供大家参考,具体如下: 1.前言 在用户使用联网的软件的时候,总会从网络上获取数据,当在一段时间内要多次使用同一个数据的时候,用户不可能每次用的时候都去联网进行请求,既浪费时间又浪费网络 这时就可以将用户请求过的数据进行保存,但不是任意数据都进行保存,这样会造成内存浪费的.LRU算法的思想就可以运用了. 2.LRU简介 LRU是Least Recently Used 近期最少使用算法,它就可以将长时间没有被利用的数据进行删除. LRU在人们

  • Java 手写LRU缓存淘汰算法

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

  • Java之理解Redis回收算法LRU案例讲解

    如何通俗易懂的理解LRU算法? 1.LRU是什么? LRU全称Least Recently Used,也就是最近最少使用的意思,是一种内存管理算法,最早应用于Linux操作系统. LRU算法基于一种假设:长期不被使用的数据,在未来被用到的几率也不大.因此,当数据所占内存达到一定阈值时,我们要移除掉最近最少被使用的数据. LRU算法应用:可以在内存不够时,从哈希表移除一部分很少访问的用户. LRU是什么?按照英文的直接原义就是Least Recently Used,最近最久未使用法,它是按照一个非

  • java实现LRU缓存淘汰算法的方法

    LRU算法:最近最少使用淘汰算法(Least Recently Used).LRU是淘汰最长时间没有被使用的缓存(即使该缓存被访问的次数最多). 如何实现LRU缓存淘汰算法 场景: 我们现在有这么个真实场景,我在爬取某个网站时,控制该网站的代理IP并发数,太多会搞垮对方网站的对吧,要蹲号子的呢.这里我需要维护一个代理IP代理池,而且这些IP肯定不是一直都很稳定的,但是又不能取一个就丢一个,这样太浪费资源.所以我会将这些IP缓存起来,进行按需提取,采用LRU最近最少使用的策略去管理代理IP. 代码

  • Java实现常用缓存淘汰算法:FIFO、LRU、LFU

    目录 缓存淘汰算法 FIFO LRU LFU 总结 缓存淘汰算法 在高并发.高性能的质量要求不断提高时,我们首先会想到的就是利用缓存予以应对. 第一次请求时把计算好的结果存放在缓存中,下次遇到同样的请求时,把之前保存在缓存中的数据直接拿来使用. 但是,缓存的空间一般都是有限,不可能把所有的结果全部保存下来.那么,当缓存空间全部被占满再有新的数据需要被保存,就要决定删除原来的哪些数据.如何做这样决定需要使用缓存淘汰算法. 常用的缓存淘汰算法有:FIFO.LRU.LFU,下面我们就逐一介绍一下. F

  • golang实现LRU缓存淘汰算法的示例代码

    LRU缓存淘汰算法 LRU是最近最少使用策略的缩写,是根据数据的历史访问记录来进行淘汰数据,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高". 双向链表实现LRU 将Cache的所有位置都用双链表连接起来,当一个位置被访问(get/put)之后,通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中. 这样,在多次操作后,最近被访问(get/put)的,就会被向链表头方向移动,而没有访问的,向链表后方移动,链表尾则表示最近最少使用的Cache

  • 工程师必须了解的LRU缓存淘汰算法以及python实现过程

    大家好,欢迎大家来到算法数据结构专题,今天我们和大家聊一个非常常用的算法,叫做LRU. LRU的英文全称是Least Recently Used,也即最不经常使用.我们看着好像挺迷糊的,其实这个含义要结合缓存一起使用.对于工程而言,缓存是非常非常重要的机制,尤其是在当下的互联网应用环境当中,起到的作用非常重要.为了便于大家更好地理解,我们从缓存的机制开始说起. 缓存 缓存的英文是cache,最早其实指的是用于CPU和主存数据交互的.早年这块存储被称为高速缓存,最近已经听不到这个词了,不知道是不是

  • 详解Java实现LRU缓存

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

  • Python 如何手动编写一个自己的LRU缓存装饰器的方法实现

    LRU缓存算法,指的是近期最少使用算法,大体逻辑就是淘汰最长时间没有用的那个缓存,这里我们使用有序字典,来实现自己的LRU缓存算法,并将其包装成一个装饰器. 1.首先创建一个my_cache.py文件 编写自己我们自己的LRU缓存算法,代码如下: import time from collections import OrderedDict ''' 基于LRU,近期最少用缓存算法写的装饰器. ''' class LRUCacheDict: def __init__(self, max_size=

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

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

  • java使用hashMap缓存保存数据的方法

    本文实例讲述了java使用hashMap缓存保存数据的方法.分享给大家供大家参考,具体如下: private static final HashMap<Long, XXX> sCache = new HashMap<Long, XXX>(); private static int sId = -1; public static void initAlbumArtCache() { try { //... if (id != sId) { clearCache(); sId = id

  • 图文讲解Java中实现quickSort快速排序算法的方法

    相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

随机推荐