`
gogole_09
  • 浏览: 206039 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

缓存策略之LRU实现(基于双链表实现)

阅读更多
 

    缓存在应用中的作用,相信不用多说,对性能是具有质的提升的,而目前的缓存策略常用的FIFO,LRU等等。

   今天来探讨一下 LRU这种缓存策略的底层原理与实现。

 

  首先,来看看LRU的定义: Least recently used. 可以理解为, 最少使用的被淘汰。

  

  今天主要来讨论基于双链表的LRU算法的实现, 在讨论之前,我们需要了解一下,传统LRU算法的实现,与其的弊端。

 

   传统意义的LRU算法是为每一个Cache对象设置一个计数器,每次Cache命中则给计数器+1,而Cache用完,需要淘汰旧内容,放置新内容时,就查看所有的计数器,并将最少使用的内容替换掉。

    它的弊端很明显,如果Cache的数量少,问题不会很大, 但是如果Cache的空间过大,达到10W或者100W以上,一旦需要淘汰,则需要遍历所有计算器,其性能与资源消耗是巨大的。效率也就非常的慢了。

 

    基于这样的情况,所有就有新的LRU算法的实现----基于双链表 的LRU实现。

    它的原理: 将Cache的所有位置都用双连表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。

     这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,而想链表后面移动,链表尾则表示最近最少使用的Cache。

     当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘汰链表最后的部分即可。

 

  上面说了这么多的理论, 下面用代码来实现一个LRU策略的缓存。

    我们用一个对象来表示Cache,并实现双链表,

     

public class LRUCache {
	/**
	 * 链表节点
	 * @author Administrator
	 *
	 */
	class CacheNode {
		……
	}

	private int cacheSize;//缓存大小
	private Hashtable nodes;//缓存容器
	private int currentSize;//当前缓存对象数量
	private CacheNode first;//(实现双链表)链表头
	private CacheNode last;//(实现双链表)链表尾
}

 

 下面给出完整的实现,这个类也被Tomcat所使用( org.apache.tomcat.util.collections.LRUCache),但是在tomcat6.x版本中,已经被弃用,使用另外其他的缓存类来替代它。

 

public class LRUCache {
	/**
	 * 链表节点
	 * @author Administrator
	 *
	 */
	class CacheNode {
		CacheNode prev;//前一节点
		CacheNode next;//后一节点
		Object value;//值
		Object key;//键
		CacheNode() {
		}
	}

	public LRUCache(int i) {
		currentSize = 0;
		cacheSize = i;
		nodes = new Hashtable(i);//缓存容器
	}
	
	/**
	 * 获取缓存中对象
	 * @param key
	 * @return
	 */
	public Object get(Object key) {
		CacheNode node = (CacheNode) nodes.get(key);
		if (node != null) {
			moveToHead(node);
			return node.value;
		} else {
			return null;
		}
	}
	
	/**
	 * 添加缓存
	 * @param key
	 * @param value
	 */
	public void put(Object key, Object value) {
		CacheNode node = (CacheNode) nodes.get(key);
		
		if (node == null) {
			//缓存容器是否已经超过大小.
			if (currentSize >= cacheSize) {
				if (last != null)//将最少使用的删除
					nodes.remove(last.key);
				removeLast();
			} else {
				currentSize++;
			}
			
			node = new CacheNode();
		}
		node.value = value;
		node.key = key;
		//将最新使用的节点放到链表头,表示最新使用的.
		moveToHead(node);
		nodes.put(key, node);
	}

	/**
	 * 将缓存删除
	 * @param key
	 * @return
	 */
	public Object remove(Object key) {
		CacheNode node = (CacheNode) nodes.get(key);
		if (node != null) {
			if (node.prev != null) {
				node.prev.next = node.next;
			}
			if (node.next != null) {
				node.next.prev = node.prev;
			}
			if (last == node)
				last = node.prev;
			if (first == node)
				first = node.next;
		}
		return node;
	}

	public void clear() {
		first = null;
		last = null;
	}

	/**
	 * 删除链表尾部节点
	 *  表示 删除最少使用的缓存对象
	 */
	private void removeLast() {
		//链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象)
		if (last != null) {
			if (last.prev != null)
				last.prev.next = null;
			else
				first = null;
			last = last.prev;
		}
	}
	
	/**
	 * 移动到链表头,表示这个节点是最新使用过的
	 * @param node
	 */
	private void moveToHead(CacheNode node) {
		if (node == first)
			return;
		if (node.prev != null)
			node.prev.next = node.next;
		if (node.next != null)
			node.next.prev = node.prev;
		if (last == node)
			last = node.prev;
		if (first != null) {
			node.next = first;
			first.prev = node;
		}
		first = node;
		node.prev = null;
		if (last == null)
			last = first;
	}
	private int cacheSize;
	private Hashtable nodes;//缓存容器
	private int currentSize;
	private CacheNode first;//链表头
	private CacheNode last;//链表尾
}

 

 PS:

   首先感谢各位给帖子投票的朋友, 不管你是投的新手贴,还是精华帖,都是对我的鼓励,

    对于帖子中大量谈到的并发问题,这个实现在写之前确实是没有考虑的。 

   帖子的本意只是向不清楚LRU实现的朋友,展示这种算法的实现而已,并非是专门讲并发性问题的。

   对于帖子中谈到的并发问题, 稍后有时间,我会写一个稍微完善一点的实现,贴出来, 到时候,再跟大家探讨探讨。

分享到:
评论
32 楼 harim 2015-04-13  
思路十分不错,最近两家公司面试都问到了这个问题,我没有答出来,遗憾啊!
31 楼 hardPass 2010-06-21  
linliangyi2007 写道
hardPass 写道


linliangyi2007 写道
[
这是算法好贴,那个家伙投的“新手”,替楼主鄙视之~~

看了楼主的源码,似乎有并发问题,不是hashtable的并发问题,而是在对cache指针做移动时,存在并发问题,不知道是不是我没考虑周全。

不过原理是讲透了,给个精华!


linliangyi2007 写道
hardPass 写道
只能投新手帖,没有深度,双重链表,大学数据结构书里就有

HashTable本身是没有并发问题,但楼主的程序有明显的并发问题。
用HashTable就没有并发问题了吗?
讲cache,不提并发,等于没讲。

在并发的时候,moveToHead有明显的并发问题
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。


javaeye就是多这样的看客,有本事自己写几个深刻的啊!不要人家写了还这么不怀好意。

就算不深刻,也不用投个新手吧(要扣分的),你牛你飘过就好!

支持楼主的精神先



不错,对楼主的乐于分享的精神,还是值得肯定的。
说句实话,我之前从来没给谁投过新手帖,一般看到讨论,围观围观就算了。

虽然楼主的代码有问题,我可以不管,但是却被你这位仁兄说成是精华,那就是另外一回事情了。
如果我们默许、纵容你等乱投精华,岂不是误导新人?那才是真正的悲哀!
你可知道,楼主被扣分,也是因为你!

je这个地方,注重的是实事求是的讨论,吹嘘拍马的就不要了吧




楼上的搞清楚孰先孰后,是帖子先被投了新手,我才投个精华来做冲抵的,不要冤枉好人哈



反正我是先看到你说要投精......
30 楼 prowl 2010-06-18  
linliangyi2007 写道
prowl 写道
并发,建议使用ConcurrentHashMap吧。效率比HashTable高很多



美眉是吧,看清楚人家在讨论啥了木有啊,人家重点在LRU算法啊,不是在讲HashTable哦。


算法不包括效率和并发性吗?
29 楼 linliangyi2007 2010-06-18  
hardPass 写道


linliangyi2007 写道
[
这是算法好贴,那个家伙投的“新手”,替楼主鄙视之~~

看了楼主的源码,似乎有并发问题,不是hashtable的并发问题,而是在对cache指针做移动时,存在并发问题,不知道是不是我没考虑周全。

不过原理是讲透了,给个精华!


linliangyi2007 写道
hardPass 写道
只能投新手帖,没有深度,双重链表,大学数据结构书里就有

HashTable本身是没有并发问题,但楼主的程序有明显的并发问题。
用HashTable就没有并发问题了吗?
讲cache,不提并发,等于没讲。

在并发的时候,moveToHead有明显的并发问题
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。


javaeye就是多这样的看客,有本事自己写几个深刻的啊!不要人家写了还这么不怀好意。

就算不深刻,也不用投个新手吧(要扣分的),你牛你飘过就好!

支持楼主的精神先



不错,对楼主的乐于分享的精神,还是值得肯定的。
说句实话,我之前从来没给谁投过新手帖,一般看到讨论,围观围观就算了。

虽然楼主的代码有问题,我可以不管,但是却被你这位仁兄说成是精华,那就是另外一回事情了。
如果我们默许、纵容你等乱投精华,岂不是误导新人?那才是真正的悲哀!
你可知道,楼主被扣分,也是因为你!

je这个地方,注重的是实事求是的讨论,吹嘘拍马的就不要了吧




楼上的搞清楚孰先孰后,是帖子先被投了新手,我才投个精华来做冲抵的,不要冤枉好人哈
28 楼 hardPass 2010-06-18  


linliangyi2007 写道
[
这是算法好贴,那个家伙投的“新手”,替楼主鄙视之~~

看了楼主的源码,似乎有并发问题,不是hashtable的并发问题,而是在对cache指针做移动时,存在并发问题,不知道是不是我没考虑周全。

不过原理是讲透了,给个精华!


linliangyi2007 写道
hardPass 写道
只能投新手帖,没有深度,双重链表,大学数据结构书里就有

HashTable本身是没有并发问题,但楼主的程序有明显的并发问题。
用HashTable就没有并发问题了吗?
讲cache,不提并发,等于没讲。

在并发的时候,moveToHead有明显的并发问题
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。


javaeye就是多这样的看客,有本事自己写几个深刻的啊!不要人家写了还这么不怀好意。

就算不深刻,也不用投个新手吧(要扣分的),你牛你飘过就好!

支持楼主的精神先



不错,对楼主的乐于分享的精神,还是值得肯定的。
说句实话,我之前从来没给谁投过新手帖,一般看到讨论,围观围观就算了。

虽然楼主的代码有问题,我可以不管,但是却被你这位仁兄说成是精华,那就是另外一回事情了。
如果我们默许、纵容你等乱投精华,岂不是误导新人?那才是真正的悲哀!
你可知道,楼主被扣分,也是因为你!

je这个地方,注重的是实事求是的讨论,吹嘘拍马的就不要了吧




27 楼 lw1130 2010-06-18  
lru 这个是oracle在 库高速缓存中就是使用的这个策略,最近最少使用 算法 呵呵
26 楼 linliangyi2007 2010-06-17  
prowl 写道
并发,建议使用ConcurrentHashMap吧。效率比HashTable高很多



美眉是吧,看清楚人家在讨论啥了木有啊,人家重点在LRU算法啊,不是在讲HashTable哦。
25 楼 linliangyi2007 2010-06-17  
hardPass 写道
只能投新手帖,没有深度,双重链表,大学数据结构书里就有

HashTable本身是没有并发问题,但楼主的程序有明显的并发问题。
用HashTable就没有并发问题了吗?
讲cache,不提并发,等于没讲。

在并发的时候,moveToHead有明显的并发问题
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。


javaeye就是多这样的看客,有本事自己写几个深刻的啊!不要人家写了还这么不怀好意。

就算不深刻,也不用投个新手吧(要扣分的),你牛你飘过就好!

支持楼主的精神先
24 楼 prowl 2010-06-17  
并发,建议使用ConcurrentHashMap吧。效率比HashTable高很多
23 楼 kerrysk 2010-06-17  
可以看下OSCache的实现,JDK有相应数据结构的实现LinkedHashSet。
22 楼 jef 2010-06-17  
hardPass 写道
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。


插句嘴,我一直认为真正的LRU实现——兼顾性能和统计的准确性,是需要内部的独立线程完成命中统计及删除操作的,命中数不重要,重要的是单位时间内的命中率。不知道我的想法对不对。


21 楼 elam 2010-06-17  
hardPass 写道
只能投新手帖,没有深度,双重链表,大学数据结构书里就有

HashTable本身是没有并发问题,但楼主的程序有明显的并发问题。
用HashTable就没有并发问题了吗?
讲cache,不提并发,等于没讲。

在并发的时候,moveToHead有明显的并发问题
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。

我也同意这个链表会出现最近使用却被最先删除的情况,觉得这个实现很不完善。
20 楼 hardPass 2010-06-17  
只能投新手帖,没有深度,双重链表,大学数据结构书里就有

HashTable本身是没有并发问题,但楼主的程序有明显的并发问题。
用HashTable就没有并发问题了吗?
讲cache,不提并发,等于没讲。

在并发的时候,moveToHead有明显的并发问题
有可能出现最近使用,却被首先删除的情况。和LRU背道而驰。
19 楼 linliangyi2007 2010-06-17  
这是算法好贴,那个家伙投的“新手”,替楼主鄙视之~~

看了楼主的源码,似乎有并发问题,不是hashtable的并发问题,而是在对cache指针做移动时,存在并发问题,不知道是不是我没考虑周全。

不过原理是讲透了,给个精华!
18 楼 giginet 2010-06-17  
确实,这个是一个原理而已。真正实现的话,还需要考虑如下问题:
1.缓存大小设定
2.硬盘存储
3.快速查找
4.并发
5.hit
17 楼 gogole_09 2010-06-16  
kimmking 写道
yimlin 写道
不晓得并发的效率如何,感觉这样并发效率会相对慢些。
因为执行操作时需要加锁,而且锁的时间较长。

所以,必须要快速的命中,
否则,无法实用的。

如果是db来的数据缓存,一般很高的命中率(比如90%),才有使用价值。

 
上述提到的问题,确实是此实现需要解决的,也是我没有考虑的, 事实上我的初衷是将LRU缓存的原理解释一下, 对于并发性,命中率等还没有进行深入考虑,可以说只是将基本原理说明一下, 当然离一个真正投入使用的LRU缓存实现还差很多, 在此多谢此帖中各位朋友提出的相关问题与提供的解决方案的参考。
16 楼 gogole_09 2010-06-16  
<div class="quote_title">zhangshixi 写道</div>
<div class="quote_div">
<p>LinkedHashMap的LRU策略:<a href="http://zhangshixi.iteye.com/blog/673789" target="_self">http://zhangshixi.iteye.com/blog/673789</a></p>
</div>
<p><br>     此文分析很透彻, 受教.</p>
15 楼 gogole_09 2010-06-16  
icanfly 写道
我看这缓存实现没有带锁?

  实现利用Hashtable充当容器, Hashtable为线程安全,所以不需加锁.
14 楼 kimmking 2010-06-16  
yimlin 写道
不晓得并发的效率如何,感觉这样并发效率会相对慢些。
因为执行操作时需要加锁,而且锁的时间较长。

所以,必须要快速的命中,
否则,无法实用的。

如果是db来的数据缓存,一般很高的命中率(比如90%),才有使用价值。
13 楼 yimlin 2010-06-16  
不晓得并发的效率如何,感觉这样并发效率会相对慢些。
因为执行操作时需要加锁,而且锁的时间较长。

相关推荐

    链表(上):如何实现LRU缓存淘汰算法.pdf

    在众多缓存淘汰策略中,LRU算法因其较好的效果和较低的实现复杂度而受到青睐。 #### LRU算法的原理 LRU算法的基本思想是:当缓存空间不足时,优先淘汰那些最近最少被访问的数据项。这样做的理由是基于局部性原理...

    c语言实现的LRU算法

    LRU(Least Recently Used)算法是一种常用的页面替换策略,它基于“最近最少使用”的原则,即当内存空间不足时,最长时间未被访问过的页面优先被淘汰。在C语言中实现LRU算法,需要理解数据结构和算法的基础知识,...

    双向链表双向链表双向链表

    这使得双向链表在需要频繁进行双向导航的场景下比单链表更有优势,例如在实现LRU缓存淘汰策略时,或者在需要实现高效前向和后向迭代的集合中。 双向链表在内存管理上需要注意的是,由于每个节点需要存储额外的指针...

    实现了LRU算法的缓存

    LRU缓存通常基于哈希表和双向链表实现。哈希表用于快速查找,而双向链表则用来维护元素的顺序性,以便于执行删除和插入操作。在Java中,`HashMap`可以作为哈希表,而自定义的双向链表结构或者使用`LinkedList`稍加...

    双向链表(不用模板实现)

    此外,它们也被用在各种算法中,如LRU缓存淘汰策略,因为双向链表可以快速地在链表中移动节点。 通过以上代码,我们可以创建一个简单的C++双向链表,而无需使用模板。模板可以在处理多种数据类型时提供更多的灵活性...

    带头节点的双向链表

    在实际应用中,带头节点的双向链表常用于实现高效的数据结构和算法,如LRU缓存淘汰策略、实现高效的集合操作(如集合的并集、差集和交集)等。例如,在C++标准模板库(STL)中的`std::list`容器就是基于双向链表实现...

    hyperlru用60行代码快速LRU实现

    LRU是一种常见的缓存管理策略,它基于“最近最少使用的数据优先被替换”的原则。当缓存满时,最近最少使用的数据会被淘汰,以腾出空间给新数据。在编程中,LRU常用于提升数据访问速度,因为它能保证频繁访问的数据...

    东南大学操作系统实验——实现LRU算法及其近似算法

    实验的主要数据结构是一个模板类`lru_cache`,它基于关联容器`std::unordered_map`和双向链表`std::list`实现。`unordered_map`用于快速查找页面,而`list`则保持页面的访问顺序。`put()`方法用于插入或更新页面,`...

    LRU算法实现

    LRU(Least Recently Used,最近最久未使用)算法是一种常用的页面替换策略,广泛应用于操作系统内存管理和数据库...通过深入学习LRU的原理和实现,开发者可以更好地设计和优化缓存策略,以适应各种复杂的应用场景。

    c语言实现LRU缓存.zip

    LRU(Least Recently Used)缓存淘汰算法是一种常见的内存管理策略,用于在固定容量的缓存中决定何时替换数据。当缓存满时,最近最少使用的数据将被优先移除,以便为新数据腾出空间。C语言实现LRU缓存涉及到数据结构...

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

    ### Node.js 基于 LRU 算法实现的缓存处理操作示例 #### 一、引言 在现代软件系统特别是Web应用中,缓存技术的应用极为广泛。它能够显著提升系统的响应速度与整体性能。在Node.js开发环境中,LRU (Least Recently ...

    LRU算法的自编c++实现及源码。 .rar_LRU_lru算法

    1. **双向链表**:LRU算法通常基于双向链表,因为我们需要在任何时候都能够快速地找到最近使用的元素并将其移动到链表头部。双向链表允许我们高效地进行插入和删除操作。 2. **哈希表**:为了能够在常数时间内查找...

    Java对象缓存系统的实现,实现了LRU算法,并可以进行集群同步

    本项目实现了一个基于Java的对象缓存系统,其中包含了LRU(Least Recently Used)算法,以及支持集群同步功能。这里我们将深入探讨相关知识点。 **LRU算法** LRU是一种常用的页面替换算法,其核心思想是:当内存...

    双向链表源码.(C、C++、JAVA)

    双向链表是一种基础且重要的...它在实际编程中有很多应用场景,例如实现LRU缓存策略、编辑器的撤销/重做功能、实现某些排序算法等。在这些场景中,双向链表的高效遍历和灵活插入、删除能力使其成为首选数据结构之一。

    一个LRU算法的实现

    LRU(Least Recently Used)算法是一种常用的页面替换策略,它基于“最近最少使用”的原则,即当内存空间不足时,最长时间未被使用的数据会被优先淘汰。在操作系统、数据库管理系统和缓存系统等领域,LRU算法都有...

    Lru缓存代码

    1. **数据结构**:LRU缓存通常基于数据结构实现,如哈希表(用于快速查找)和双向链表(用于保持顺序)。哈希表存储键值对,而链表记录元素的访问顺序。 2. **插入操作**:当新数据插入缓存时,如果缓存未满,则...

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

    3. **LRU List**:所有在Buffer Pool中的数据页都会在一个双向链表中按LRU策略排序。新加载的页面插入链表尾部,每次页面被访问,都会被移动到链表头部。当需要替换页面时,链表头部的页面(即最近最少使用的页面)...

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

    LRU(Least Recently Used,最近最少使用)置换算法是一种常见的页面替换策略,广泛应用于操作系统、数据库和缓存系统中。在JavaScript(简称js)中实现LRU算法,可以帮助我们优化资源管理和提高性能,特别是在内存...

    LRU.rar_LRU_lru源码

    在计算机科学中,LRU(Least Recently Used)算法是一种广泛应用于缓存淘汰的策略,它基于这样的假设:如果数据最近被访问过,则未来被访问的可能性更高。因此,当缓存达到上限时,LRU算法会淘汰最长时间未被使用的...

Global site tag (gtag.js) - Google Analytics