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

呵呵，除了自己写还可以使用JDK的LinkedHashMap 只需要覆盖

protected boolean removeEldestEntry(Map.Entry<K,V> eldest);

方法即可得到一个最近最少使用的容器

LinkedHashMap的LRU策略：http://zhangshixi.iteye.com/blog/673789

一个好的LRU实现，需要解决的问题:

1\ 最近数据的快速命中、旧数据+不常用的快速淘汰

2\ 一般数据的快速查找

 

传统的HashMap+调用计数解决了问题2，

仅仅用一个双链表，并不能解决cache数据量大的效率问题，解决了问题1，因为从这个表里查一个数据，还是很耗时的。

楼上给的LinkedHashMap是一个好的方案。

 

不晓得并发的效率如何，感觉这样并发效率会相对慢些。
因为执行操作时需要加锁，而且锁的时间较长。

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

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

  实现利用Hashtable充当容器， Hashtable为线程安全，所以不需加锁.

     此文分析很透彻， 受教.

 
上述提到的问题，确实是此实现需要解决的，也是我没有考虑的， 事实上我的初衷是将LRU缓存的原理解释一下， 对于并发性，命中率等还没有进行深入考虑，可以说只是将基本原理说明一下， 当然离一个真正投入使用的LRU缓存实现还差很多， 在此多谢此帖中各位朋友提出的相关问题与提供的解决方案的参考。

确实，这个是一个原理而已。真正实现的话，还需要考虑如下问题：
1.缓存大小设定
2.硬盘存储
3.快速查找
4.并发
5.hit

这是算法好贴，那个家伙投的“新手”，替楼主鄙视之~~

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

不过原理是讲透了，给个精华！