缓存在应用中的作用，相信不用多说，对性能是具有质的提升的，而目前的缓存策略常用的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算法的原理 LRU算法的基本思想是：当缓存空间不足时，优先淘汰那些最近最少被访问的数据项。这样做的理由是基于局部性原理...
LRU（Least Recently Used）算法是一种常用的页面替换策略，它基于“最近最少使用”的原则，即当内存空间不足时，最长时间未被访问过的页面优先被淘汰。在C语言中实现LRU算法，需要理解数据结构和算法的基础知识，...
这使得双向链表在需要频繁进行双向导航的场景下比单链表更有优势，例如在实现LRU缓存淘汰策略时，或者在需要实现高效前向和后向迭代的集合中。 双向链表在内存管理上需要注意的是，由于每个节点需要存储额外的指针...
LRU缓存通常基于哈希表和双向链表实现。哈希表用于快速查找，而双向链表则用来维护元素的顺序性，以便于执行删除和插入操作。在Java中，`HashMap`可以作为哈希表，而自定义的双向链表结构或者使用`LinkedList`稍加...
此外，它们也被用在各种算法中，如LRU缓存淘汰策略，因为双向链表可以快速地在链表中移动节点。 通过以上代码，我们可以创建一个简单的C++双向链表，而无需使用模板。模板可以在处理多种数据类型时提供更多的灵活性...
在实际应用中，带头节点的双向链表常用于实现高效的数据结构和算法，如LRU缓存淘汰策略、实现高效的集合操作（如集合的并集、差集和交集）等。例如，在C++标准模板库（STL）中的`std::list`容器就是基于双向链表实现...
LRU是一种常见的缓存管理策略，它基于“最近最少使用的数据优先被替换”的原则。当缓存满时，最近最少使用的数据会被淘汰，以腾出空间给新数据。在编程中，LRU常用于提升数据访问速度，因为它能保证频繁访问的数据...
实验的主要数据结构是一个模板类`lru_cache`，它基于关联容器`std::unordered_map`和双向链表`std::list`实现。`unordered_map`用于快速查找页面，而`list`则保持页面的访问顺序。`put()`方法用于插入或更新页面，`...
LRU（Least Recently Used，最近最久未使用）算法是一种常用的页面替换策略，广泛应用于操作系统内存管理和数据库...通过深入学习LRU的原理和实现，开发者可以更好地设计和优化缓存策略，以适应各种复杂的应用场景。
LRU（Least Recently Used）缓存淘汰算法是一种常见的内存管理策略，用于在固定容量的缓存中决定何时替换数据。当缓存满时，最近最少使用的数据将被优先移除，以便为新数据腾出空间。C语言实现LRU缓存涉及到数据结构...
### Node.js 基于 LRU 算法实现的缓存处理操作示例 #### 一、引言 在现代软件系统特别是Web应用中，缓存技术的应用极为广泛。它能够显著提升系统的响应速度与整体性能。在Node.js开发环境中，LRU (Least Recently ...
1. **双向链表**：LRU算法通常基于双向链表，因为我们需要在任何时候都能够快速地找到最近使用的元素并将其移动到链表头部。双向链表允许我们高效地进行插入和删除操作。 2. **哈希表**：为了能够在常数时间内查找...
本项目实现了一个基于Java的对象缓存系统，其中包含了LRU（Least Recently Used）算法，以及支持集群同步功能。这里我们将深入探讨相关知识点。 **LRU算法** LRU是一种常用的页面替换算法，其核心思想是：当内存...
双向链表是一种基础且重要的...它在实际编程中有很多应用场景，例如实现LRU缓存策略、编辑器的撤销/重做功能、实现某些排序算法等。在这些场景中，双向链表的高效遍历和灵活插入、删除能力使其成为首选数据结构之一。
LRU（Least Recently Used）算法是一种常用的页面替换策略，它基于“最近最少使用”的原则，即当内存空间不足时，最长时间未被使用的数据会被优先淘汰。在操作系统、数据库管理系统和缓存系统等领域，LRU算法都有...
1. **数据结构**：LRU缓存通常基于数据结构实现，如哈希表（用于快速查找）和双向链表（用于保持顺序）。哈希表存储键值对，而链表记录元素的访问顺序。 2. **插入操作**：当新数据插入缓存时，如果缓存未满，则...
3. **LRU List**：所有在Buffer Pool中的数据页都会在一个双向链表中按LRU策略排序。新加载的页面插入链表尾部，每次页面被访问，都会被移动到链表头部。当需要替换页面时，链表头部的页面（即最近最少使用的页面）...
LRU（Least Recently Used，最近最少使用）置换算法是一种常见的页面替换策略，广泛应用于操作系统、数据库和缓存系统中。在JavaScript（简称js）中实现LRU算法，可以帮助我们优化资源管理和提高性能，特别是在内存...
本项目是基于C++实现LRU算法及其近似算法，旨在让学生深入理解这种算法的原理并进行实践操作。 LRU算法的核心思想是：当内存满时，最近最少使用的页面将被替换出去。具体实现通常采用数据结构如哈希表与双向链表...