`

LRU算法解析

LRU 
阅读更多

在项目中用到了common-collections中LRUMap,最近有空看了一下源码,对LRU算法有了更具体的认识,LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

LRUMap实现的核心思想是使用一个链表,将经常使用的放在链表的尾部,如果LRUMap的size已经到最大值时不会像传统的Map会进行自动容量扩充,而是从链表的头部覆盖数据,覆盖后以前头部的数据就相当于被淘汰。LRUMap

中使用了一个固定大小的数组来存放数据,数组中每个元素都是一个LinkEntry数据结构,除了key和value外还多了一个after和before,这样就形成了一个双向链表

protected static class LinkEntry extends HashEntry {
        protected AbstractLinkedMap.LinkEntry before;
        protected AbstractLinkedMap.LinkEntry after;

        protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
            super(next, hashCode, key, value);
        }
    }

 get操作时如果找到对应的对象,会修改相关对象的after和before的引用将该对象移到链表的末尾,表示最近刚被访问过

public Object get(Object key) {
        LinkEntry entry = (LinkEntry)this.getEntry(key);
        if(entry == null) {
            return null;
        } else {
            this.moveToMRU(entry);
            return entry.getValue();
        }
    }

 其中moveToMRU方法就是移动对象到链表的末尾

put操作时会执行以下几步:

  1. 如果链表中存在key,会替换对应的value并将该对象设置成链表的末尾
  2. 如果size没有到最大值,会根据计算hashcode放入到在数组中,并将该对象设置成链表的末尾
  3. 如果size达到最大值,会从链表的头部开始覆盖数据,并将该对象修改成链表的末尾

LRUMap是非线程安全的,如果需要线程安全可以使用Collections.synchronizeMap()获取一个线程安全的Map

或者使用goole提供的一个ConcurrentLinkedHashMap,一个基于ConcurrentHashMap实现的LRU算法,性能跟ConcurrentHashMap相差无几,源代码地址:https://github.com/ben-manes/concurrentlinkedhashmap

相关链接:

http://flychao88.iteye.com/blog/1977653 LRU算法详解和优化算法

http://janeky.iteye.com/blog/1534352 线程安全的LRUMap-ConcurrentLinkedHashMap

分享到:
评论

相关推荐

    LRU算法的实现

    近期最少使用算法

    页面置换算法FIFO:先进先出 NUR: 最近未使用算法

    介绍LFU使用数据的访问频率,有利于数据的总体优化使用,但不利于数据访问方式的变化和猝... .LRU-K算法则是使用最后第K次访问时间来扩展LRU算法,依靠K值的大小进行平衡.它们都是对访问时间的修正,是对LRU算法的改进.

    python题目(1).rar

    1.问题描述:假设有一个6x6的棋盘,每个格子里有一个奖品(每...解析:所谓LRU算法,是指在发生缺页并且没有空闲主存块时,把最近最少使用的页面换出主存块,腾出地方来调入新页面。提示:可用列表切片模拟LRU算法的用法。

    Android Json数据的解析+ListView图文混排+缓存算法Lrucache 仿知乎

    开发知乎的第一步,首先熟悉看知乎的API以及Json数据的解析,才能进行下一步。

    ASL.rar_ASL _Alpha_alpha算法指令_ini_游戏

    文显示模块用LRU算法的Cache管理字模,支持平滑字体显示(反锯齿),MMX指令优 化,成倍提高绘制速度。强大的可扩展GUI系统,模仿VCL的层次和接口,使用起来 类似在C++ Builder下的开发,实现了各种常用控件。另有...

    Azure Star Game Engine 蓝星游戏引擎

    文显示模块用LRU算法的Cache管理字模,支持平滑字体显示(反锯齿),MMX指令优 化,成倍提高绘制速度。强大的可扩展GUI系统,模仿VCL的层次和接口,使用起来 类似在C++ Builder下的开发,实现了各种常用控件。另有...

    json解析,异步下载(listview仅滑动时加载)Demo

    异步加载的练习demo 主要涉及知识点: 1.解析json格式数据,主要包括图片,文本 2.使用线程和AsynTask俩种异步方式从网络下载图片...4.使用Lru缓存算法 5.改进加载:仅在listview滑动停止后才加载可见项,滑动中不加载

    nodejs写的HTTP静态文件的引擎(轻量级)

    支持小文件内存缓存(LRU算法,可配置尺寸) 支持304木有修改(静态服务器最重要的就是这个了吧) 支持gzip、deflate压缩 支持分段下载(支持部分,可用迅雷等多线程下载工具) 提供动态解析的接口 最后由于是本人...

    ASL游戏引擎及其DEMO泡泡堂(含源码)

    中文显示模块用LRU算法的Cache管理字模,支持平滑字体显示(反锯齿),MMX指令优化,成倍提高绘制速度。强大的可扩展GUI系统,模仿VCL的层次和接口,使用起来类似在C++ Builder下的开发,实现了各种常用控件。另有...

    操作系统课设.zip+解析

    通过用c++语言来模拟实现操作系统的页面置换算法,包括FIFO、LRU、LFU、时钟算法、NRU、OPT

    pagesim:操作系统用于管理内存使用的常见页面替换算法的模拟

    实现的算法最佳随机的先进先出LRU 钟NFU NFU 老化去做提升配置能力配置文件(json 解析器?或者只是 VAR=meh。我有点喜欢的功能集) 从文件中读取页面调用或在配置文件中定义(硬编码页面引用不是 beuno) 最优算法...

    lrucacheleetcode-leetcode:leetcode算法学习记录golang版

    经典题目解析&golang版代码 简单难度 中等难度 困难难度 算法专项 KMP 算法 动态规划: 887. 鸡蛋掉落 5. 最长回文子串 494. 目标和 322. 零钱兑换 279. 完全平方数 198. 打家劫舍 152. 乘积最大子序列 139. 单词拆分...

    leetcode安卓-jfson.github.io:关于安卓

    LRU算法 9 Window、ViewRootImpl ... 待续 ... 待续 ... Binder Framework 梳理Android Binder的IPC机制,如何进行进程间通信 序号 文章名 概述 0 Linux IPC 机制 & 为何选 Binder 1 Android 中的序列化 2 使用AIDL...

    javalruleetcode-leetcode:力扣算法题解

    力扣算法解题,java语言 题解 简单 序号(力扣题序号) 题名 题解 两数之和 整数反转 相同的树 最长回文串 链表的中间节点 三维形体的表面积 卡牌分组 可以被一步捕获的棋子数 不用加号的加法 最小的K个数 不用加减...

    TestPrograms:围绕DS和算法的各种测试程序

    Dom解析器示例 观察者模式示例 异体平衡算法 快速排序示例 递归示例 日期格式示例 从适当的位置删除字符串中的重复项。 反向链接的第一个例子 跳过总和。 字符串中所有可能的组合 所有Tree遍历示例。 添加以字符...

    Android 常用六大框架

    FinalBitmap的内存管理使用lru算法, 没有使用弱引用(android2.3以后google已经不建议使用弱引用,android2.3后强行回收软引用和弱引用,详情查看android官方文档), 更好的管理bitmap内存。FinalBitmap可以...

    C语言实战105例源码

    实例25 模拟LRU页面置换算法 79 实例26 大整数阶乘新思路 82 实例27 银行事件驱动模拟程序 84 实例28 模拟迷宫探路 87 实例29 实现高随机度随机序列 89 实例30 停车场管理系统 91 第3部分 文本屏幕与...

    android_interviews::rocket:Everything you need to know to find a android job. 算法 面试题 Android 知识点 :fire::fire::fire: 总结不易,你的 star 是我最大的动力!

    每片文章都结合了 「解析 + 视频 + 代码」 三大模块,工程量非常之大 为了防止更新速度过快,文章质量下降的问题,宁可更新速度慢,也要保证质量 不求快,只求优质,每篇文章将以 2 ~ 3 天的周期进行更新,力求保持...

    c语言实战105例源码

    25 模拟LRU页面置换算法  26 大整数阶乘新思路  27 银行事件驱动模拟程序  28 模拟迷宫探路  29 实现高随机度随机序列  30 停车场管理系统 31 菜单实现 32 窗口制作  33 模拟屏幕保护程序 ...

Global site tag (gtag.js) - Google Analytics