`
eriol
  • 浏览: 407264 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

LRU的实现思想

    博客分类:
  • OS
阅读更多

LRU表示Least Recently Used,即最近最少被使用的页面替换算法。其理论基础是局部性原理,也就是说最近被访问的对象将在不久以后再次被访问。

 

对于LRU算法,可以使用一个链表和hashmap来实现。链表中的节点表示缓存的页面,链表中的第一个元素就是要被替换的元素,所以替换的复杂度是O(1)。同时,还维护一个hashmap来建立访问对象和缓存页面的映射关系。

 

当需要访问某个对象时,先从hashmap中查看该对象是否在缓存中,如果在,则将该缓存页面从链表中取出并插入到链表尾部,并访问对象。否则,从链表头取出一个缓存页面,将要访问的对象写入该缓存并插入到链表尾部,并且在hashmap中更新该项。这样,所有最近被访问的页面总是处于链表的尾部,即表头的元素表示最近最少被使用的可替换的页面。

 

 

LRU的实现

 

在JDK1.5中,LinkedHashMap已经实现了LRU的功能,只需要根据需要重写removeEldestEntry就行了。LinkedHashMap维护着一个运行于所有条目的双向链表。有了这个双向链表,就可以在迭代的时候按照插入的顺序迭代出元素,或者通过LRU算法迭代元素。

 

在LinkedHashMap的构造方法中,你可以指定accessOrder参数,当其为true时,将按照LRU算法对entry进行遍历;当其为false时,按照插入的顺序进行遍历。其值默认为true。想要详细了解LinkedHashMap可参见 http://boy00fly.iteye.com/blog/1144691

 

这里贴一个使用LinkedHashMap实现LRU的线程安全的代码

http://www.iteye.com/topic/123856

 

 

import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V>
{
    private final int maxCapacity;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private final Lock lock = new ReentrantLock();

    public LRULinkedHashMap(int maxCapacity)
    {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest)
    {
        return size() > maxCapacity;
    }

    @Override
    public V get(Object key)
    {
        try {
            lock.lock();
            return super.get(key);
        }
        finally {
            lock.unlock();
        }
    }

    @Override
    public V put(K key, V value)
    {
        try {
            lock.lock();
            return super.put(key, value);
        }
        finally {
            lock.unlock();
        }
    }
}
 
0
3
分享到:
评论
2 楼 eriol 2011-09-05  
deepnighttwo 写道
LinkedHashMap已经实现这个了,跟你说的差不多,你可以去看看源代码。

你说的很对,可以使用LinkedHashMap来实现LRU的功能
1 楼 deepnighttwo 2011-09-05  
LinkedHashMap已经实现这个了,跟你说的差不多,你可以去看看源代码。

相关推荐

    LRU算法四种实现方式介绍.docx

    LRU-K 的主要目的是为了解决 LRU 算法“缓存污染”的问题,其核心思想是将“最近使用过 1 次”的判断标准扩展为“最近使用过 K 次”。相比 LRU,LRU-K 需要多维护一个队列,用于记录所有缓存数据被访问的历史。 LRU...

    c语言的hash-lru实现

    LRU策略的核心思想是当缓存满时,最近最少使用的数据将被优先淘汰。 首先,我们来看看`hash_table.c`这个源文件。它应该包含了LRU哈希表的具体实现代码。在C语言中,哈希表通常由数组和链表组成,数组提供快速访问...

    LRU算法 C++实现

    LRU算法的实现通常依赖于数据结构,如哈希表和双向链表。在C++中,我们可以使用`std::unordered_map`来存储页面及其访问时间,同时使用`std::list`来维护页面的顺序。以下是一个简单的C++实现概述: ```cpp #...

    lru算法C语言实现

    LRU算法的核心思想是:当缓存满时,优先淘汰最近最少使用的数据。这里的“最近最少使用”是指在最近一段时间内被访问次数最少的数据项。 #### 三、实验代码分析 ##### 3.1 定义内存结构 ```c typedef struct page...

    LRU的实现代码(C语言编写)

    自己写的,虽然比较简单,但已经实现了LRU的思想

    LRU算法C语言版本

    LRU算法的基本思想是:如果一个页面最近被访问过,那么它在不久的将来可能还会被再次访问。因此,当需要替换页面时,LRU算法会优先选择那些长时间未被访问的页面。实现LRU通常需要一个数据结构来记录每个页面的访问...

    三级缓存和Lru实现视频笔记

    本视频笔记主要探讨了三级缓存的实现和Least Recently Used (LRU)算法的应用。以下是对这些主题的详细解析。 首先,我们来理解三级缓存的概念。在Android应用中,通常采用三级缓存策略来高效地管理数据: 1. 内存...

    LRU算法实现

    在C语言中实现LRU算法,需要定义结构体来表示页面节点(包括页面号、数据以及前后指针),创建哈希表和链表,实现插入、查找和淘汰操作的函数。`www.pudn.com.txt`可能包含示例代码或进一步的解释,而`用C语言实现...

    LRU算法实现_实验报告

    LRU (Least Recently Used) 算法是一种常用的页面替换策略,它的核心思想是优先淘汰最近最久未使用的页面。在操作系统中,由于内存资源有限,无法将所有的虚拟页面都映射到物理内存中,因此需要通过页面替换算法来...

    一个LRU算法的实现

    首先,我们需要理解LRU算法的核心思想。假设有一个固定大小的缓存(或内存),当新的数据请求进来而缓存已满时,LRU算法会选择最近最少使用的数据进行替换。这里的“最近”和“最少使用”是通过记录每个数据项的访问...

    LRU算法 lru算法

    LRU算法的基本思想是:当内存满时,新进来的页面会替换掉最近最少使用的页面。这里的“最近”是指最近一次被访问的时间,“最少使用”是指在这段时间内被访问的次数最少。这个策略的假设是,最近经常使用的数据在...

    js实现操作系统LRU置换算法

    LRU算法的基本思想是优先淘汰最近最久未使用的数据。当内存空间不足时,需要将一部分数据移到磁盘中,LRU算法会选择最近最少使用的数据进行淘汰。它的核心逻辑是基于数据的访问历史来决定哪些数据更可能在未来被频繁...

    LRU算法实现1

    LRU的核心思想是:最近最少使用的数据在将来被使用的可能性最小,因此应该优先被淘汰。在Java中,LRU缓存的实现通常有两种方式:使用`LinkedHashMap`或自定义数据结构(链表+HashMap)。 ### LRU Cache的`...

    LRU算法LRU算法LRU算法LRU算法

    LRU算法的核心思想是:当内存满时,最近最少使用的数据会被优先淘汰。也就是说,如果一个数据最近被访问过,那么它在未来被访问的可能性相对较高,而那些很久没有被访问的数据则可能不再需要,因此应该优先移除。 ...

    JAVA实现FIFO、LRU、OPT页面置换算法,有界面

    FIFO是最简单的页面置换算法,它的基本思想是:当需要替换一个页面时,选择最早进入内存的页面进行替换。这种算法基于假设"早来的页面不常用",但并不总是有效,可能会导致Belady's异常,即增加物理内存反而使得...

    LRU.rar_LRU_LRU java_lru.java

    LRU算法的基本思想是:如果一个数据最近被访问过,那么将来被访问的可能性会更高。在内存管理中,LRU用于决定何时将页面交换到磁盘上,以腾出内存供其他进程使用。当一个新页面需要加载但内存已满时,LRU会移除最近...

    lru算法实验报告

    实验的主要目标包括理解和实现 LRU 算法的调度过程,并计算出访问页面时的命中率。 实验内容分为以下部分: 1. 设计一个虚拟存储系统,其中包含一个可以容纳一定数量页面的驻留集(内存)。在实验中,驻留集的大小...

    操作系统页面置换LRU,FIFO,OPT算法实现代码

    它的核心思想是,如果一个页面最近被访问过,那么它在短期内被再次访问的可能性较大。因此,当需要淘汰页面时,LRU会选择最近最久未使用的页面。实现上,通常通过维护一个双向链表,将最近访问的页面移动到链表头部...

    基于LRU算法的数据库buffer manager实现

    LRU算法的基本思想是,最近最久未使用的数据应该优先被淘汰。当内存空间不足时,LRU算法会选择最近最少使用的数据页进行淘汰,因为这些数据页被认为在未来最不可能被访问。在数据库中,这意味着如果一个数据页最近...

    LRU算法.zip

    LRU(Least Recently Used)算法是一种常用的页面替换算法,用于管理有限的内存资源。...通过深入研究这个LRU算法的实现,你不仅可以掌握LRU算法的工作原理,还能了解到如何在实际项目中应用和优化这种缓存策略。

Global site tag (gtag.js) - Google Analytics