JAVA实现LRU算法的参考示例

LRU简介

LRU是Least Recently Used 近期最少使用算法,它就可以将长时间没有被利用的数据进行删除。

实现

最近面了阿里的外包吧,居然也要在线敲代码了,那叫一个紧张啊。题目就是实现一个LRU算法的缓存。外包居然要求也这么高了,哎。还好,LRU是我大学老师布置的一道题目,当然我用C语言实现的,算法原理那是一清二楚,可是面试的时候就脑子一片空白了。好在,边敲代码,边思考,就慢慢想起来了,下面是我的代码。仅供参考

/**
 * 设计和构建一个“最近最少使用”LRU 缓存,该缓存会删除最近最少使用的项目。
 * 缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。
 * 当缓存被填满时,它应该删除最近最少使用的项目。
 * 考虑多线程操作下的操作安全和性能。
 */
public class LRUCache{

 private int maxSize;

 /**
 * 存储缓存数据
 */
 private ConcurrentHashMap<String,Object> map = new ConcurrentHashMap<>();

 /**
 **存储缓存key列表
 */
 private LinkedList<String> list;

 LRUCache(){
 }

 LRUCache(int maxSize){
   this.maxSize = maxSize;
  this.list = new LinkedList<>(maxSize);
 }

 /**
 * @param key 缓存key
  @return 缓存值
 */
 synchronized Object getVal(String key){
  //1.从map里取数据
  Object obj = map.get(key);

  //2.将key置于list的尾部(表示最近被访问过了)
  if(obj != null){
    addOrRefreshKey(key);
  }
 }

 synchronized void putVal(String key,Object val){
   //1.设置val到map中

  //2.将key置于list的尾部(表示最近被访问过了)

   //3.需要做判断是否list.size()>maxSize。如果满了就删除头部(最近最少使用)的数据后再执行1-2步骤
 }

 /**
 * 添加或刷新key
 */
 private void addOrRefreshKey(String key){
   this.list.remove(key); //管他三七二十一,先删除掉
  this.list.add(key); //然后添加这个可以,保证key置于list的尾部
 }

}

以上就是JAVA实现LRU算法的参考示例的详细内容,更多关于Java LRU算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • Nodejs基于LRU算法实现的缓存处理操作示例

    本文实例讲述了Nodejs基于LRU算法实现的缓存处理操作.分享给大家供大家参考,具体如下: LRU是Least Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,是根据页面调入内存后的使用情况进行决策了.由于无法预测各页面将来的使用情况,只能利用"最近的过去"作为"最近的将来"的近似,因此,LRU算法就是将最近最久未使用的页面予以淘汰. 可以用一个特殊的栈来保存当前正在使用的各个页面的页面号.当一个新的进程访问某页面时,便将

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

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

  • JS 实现缓存算法的示例(FIFO/LRU)

    FIFO 最简单的一种缓存算法,设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 k-v . 使用了一个对象作为缓存,一个数组配合着记录添加进对象时的顺序,判断是否到达上限,若到达上限取数组中的第一个元素key,对应删除对象中的键值. /** * FIFO队列算法实现缓存 * 需要一个对象和一个数组作为辅助 * 数组记录进入顺序 */ class FifoCache{ constructor(limit){ this.limit = limit || 10 this

  • Android图片缓存之Lru算法(二)

    前言: 上篇我们总结了Bitmap的处理,同时对比了各种处理的效率以及对内存占用大小,点击查看.我们得知一个应用如果使用大量图片就会导致OOM(out of memory),那该如何处理才能近可能的降低oom发生的概率呢?之前我们一直在使用SoftReference软引用,SoftReference是一种现在已经不再推荐使用的方式,因为从 Android 2.3 (API Level 9)开始,垃圾回收器会更倾向于回收持有软引用或弱引用的对象,这让软引用变得不再可靠,所以今天我们来认识一种新的缓

  • c++实现的常见缓存算法和LRU

    前言 对于web开发而言,缓存必不可少,也是提高性能最常用的方式.无论是浏览器缓存(如果是chrome浏览器,可以通过chrome:://cache查看),还是服务端的缓存(通过memcached或者redis等内存数据库).缓存不仅可以加速用户的访问,同时也可以降低服务器的负载和压力.那么,了解常见的缓存淘汰算法的策略和原理就显得特别重要. 常见的缓存算法 LRU (Least recently used) 最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高. LFU (Least

  • Python实现LRU算法的2种方法

    LRU:least recently used,最近最少使用算法.它的使用场景是:在有限的空间中存储对象时,当空间满时,会按一定的原则删除原有的对象,常用的原则(算法)有LRU,FIFO,LFU等.在计算机的Cache硬件,以及主存到虚拟内存的页面置换,还有Redis缓存系统中都用到了该算法.我在一次面试和一个笔试时,也遇到过这个问题. LRU的算法是比较简单的,当对key进行访问时(一般有查询,更新,增加,在get()和set()两个方法中实现即可)时,将该key放到队列的最前端(或最后端)就

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

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

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

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

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

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

  • Java实现插入排序算法可视化的示例代码

    参考文章 图解Java中插入排序算法的原理与实现 实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 40; private InsertionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ // 初始化数据 data =

  • Java实现快速排序算法可视化的示例代码

    实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 100; private SelectionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ data = new SelectionSortData(N, sceneHe

  • Java实现快速排序算法的完整示例

    首先,来看一下,快速排序的实现的动态图: 快速排序介绍: 快速排序,根据教科书说法来看,是冒泡排序的一种改进. 快速排序,由一个待排序的数组(array),以及找准三个变量: 中枢值(pivot) 左值(left) 右值(right) 根据中枢值(pivot)来做调整,将数组(array)分为三个部分: 第一部分:中枢值(pivot),单独数字构成,这个值在每次排序好的"最中间": 第二部分:左边数组(由array的一部分组成),这个数组在第一部分 中枢值(pivot) 的"

  • JAVA版排序算法之快速排序示例

    本文实例讲述了JAVA快速排序实现方法.分享给大家供大家参考,具体如下: package com.ethan.sort.java; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class QuickSort { public static <E extends Comparable<? super E>>

  • JAVA实现KMP算法理论和示例代码

    一.理论准备KMP算法为什么比传统的字符串匹配算法快?KMP算法是通过分析模式串,预先计算每个位置发生不匹配的时候,可以省去重新匹配的的字符个数.整理出来发到一个next数组, 然后进行比较,这样可以避免字串的回溯,模式串中部分结果还可以复用,减少了循环次数,提高匹配效率.通俗的说就是KMP算法主要利用模式串某些字符与模式串开头位置的字符一样避免这些位置的重复比较的.例如 主串: abcabcabcabed ,模式串:abcabed.当比较到模式串'e'字符时不同的时候完全没有必要从模式串开始位

  • Java使用分治算法实现排序数索引功能示例【二分搜索】

    本文实例讲述了Java使用分治算法实现排序数索引功能.分享给大家供大家参考,具体如下: /** * Find the first q and return the index * First method is brutal force * Second may * be Divid and Conquer * * @author open201 * */ public class Ono { /** * f(n) = s.length = n; * * @param s * @param q

  • java数据结构与算法之插入算法实现数值排序示例

    本文实例讲述了java数据结构与算法之插入算法实现数值排序.分享给大家供大家参考,具体如下: 写在这里做个纪念,关键是要理解插入点,在插入点,初始的in和out都在这个插入点,然后通过in自减对数组进行重新排序 public static void insertSort(){ for(int out=1; out<a.length; out++){ int temp = a[out]; int in = out; while(in>0&& a[in-1]>temp){ a

随机推荐