缓存在应用中的作用，相信不用多说，对性能是具有质的提升的，而目前的缓存策略常用的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实现的朋友，展示这种算法的实现而已，并非是专门讲并发性问题的。
对于帖子中谈到的并发问题， 稍后有时间，我会写一个稍微完善一点的实现，贴出来， 到时候，再跟大家探讨探讨。
分享到：
相关推荐
LRU_缓存策略_LRU_缓存.zip
LRU缓存HashMap+双向链表实现，java版本，导入即用
LRU_缓存策略_LRU_缓存_源码.rar
LRU算法实现LRU算法实现LRU算法实现LRU算法实现LRU算法实现
链表（上）：如何实现LRU缓存淘汰算法
文件中包含三级缓存（内存缓存、本地缓存、网络缓存）的实现和Lru实现视频笔记
缓存淘汰算法之LRU
使用LRU算法实现页面置换算法。LRU算法基于一种假设，长期不使用的数据，在未来的使用性也不大。因此，当数据占用内存达到一定的阙值时，我们要移除最近最少使用的数据。LRU算法中，使用了一种有趣的数据结构，叫做...
这里的LRUCache类维护了一个双向链表和一个哈希表，用于实现LRU算法。具体实现细节如下： - get方法：首先在哈希表中查找对应的键值对，如果不存在，则返回-1；如果存在，则将对应的节点从双向链表中删除，并将其...
基于双向链表和哈希表实现的LRU进程内缓存包，C语言实现。改编自Features测试全面LRU淘汰算法双向链表和哈希表的存储模型基于键值对，键和值的数据类型为字符串对全局存储结构的写操作上锁，并发安全Usage#include ...
盘阵列中基于分组LRU的缓存调度策略设计与实现，张梦龙，陈俭喜，盘阵列系统由于面向多用户的访问请求，传统的缓存调度策略不能很好的发挥作用。本文提出了基于分组的LRU缓存调度优化策略，既可以
使用c语言是实现的LRU算法，带测试用例，供大家学习参考使用
Go业务层缓存，自带内存LRU存储,支持自定义Redis存储实现
该资源是Java实现LRU算法的相关代码，将页面序号和进程分配的模块数，运行出具体的变化过程，真实可靠，可实现。
LRU算法的java实现
近期最少使用算法
java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例
Nodejs基于LRU算法实现的缓存处理操作示例.docx
c语言实现LRU缓存