引子：
我们平时总会有一个电话本记录所有朋友的电话，但是，如果有朋友经常联系，那些朋友的电话号码不用翻电话本我们也能记住，但是，如果长时间没有联系了，要再次联系那位朋友的时候，我们又不得不求助电话本，但是，通过电话本查找还是很费时间的。但是，我们大脑能够记住的东西是一定的，我们只能记住自己最熟悉的，而长时间不熟悉的自然就忘记了。
其实，计算机也用到了同样的一个概念，我们用缓存来存放以前读取的数据，而不是直接丢掉，这样，再次读取的时候，可以直接在缓存里面取，而不用再重新查找一遍，这样系统的反应能力会有很大提高。但是，当我们读取的个数特别大的时候，我们不可能把所有已经读取的数据都放在缓存里，毕竟内存大小是一定的，我们一般把最近常读取的放在缓存里（相当于我们把最近联系的朋友的姓名和电话放在大脑里一样）。现在，我们就来研究这样一种缓存机制。
LRU缓存：
LRU缓存利用了这样的一种思想。LRU是Least Recently Used 的缩写，翻译过来就是“最近最少使用”，也就是说，LRU缓存把最近最少使用的数据移除，让给最新读取的数据。而往往最常读取的，也是读取次数最多的，所以，利用LRU缓存，我们能够提高系统的performance.
实现：
要实现LRU缓存，我们首先要用到一个类LinkedHashMap。 用这个类有两大好处：一是它本身已经实现了按照访问顺序的存储，也就是说，最近读取的会放在最前面，最最不常读取的会放在最后（当然，它也可以实现按照插入顺序存储）。第二，LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数，但是，原始方法默认不需要移除（这是，LinkedHashMap相当于一个linkedlist），所以，我们需要override这样一个方法，使得当缓存里存放的数据个数超过规定个数后，就把最不常用的移除掉。LinkedHashMap的API写得很清楚，推荐大家可以先读一下。
要基于LinkedHashMap来实现LRU缓存，我们可以选择inheritance, 也可以选择 delegation， 我更喜欢delegation。基于delegation的实现已经有人写出来了，而且写得很漂亮，我就不班门弄斧了。代码如下：
import java.util.LinkedHashMap;
import java.util.Collection;
import java.util.Map;
import java.util.ArrayList;
/**
* An LRU cache, based on <code>LinkedHashMap</code>.
*
* <p>
* This cache has a fixed maximum number of elements (<code>cacheSize</code>).
* If the cache is full and another entry is added, the LRU (least recently used) entry is dropped.
*
* <p>
* This class is thread-safe. All methods of this class are synchronized.
*
* <p>
* Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br>
* Multi-licensed: EPL / LGPL / GPL / AL / BSD.
*/
public class LRUCache<K,V> {
private static final float hashTableLoadFactor = 0.75f;
private LinkedHashMap<K,V> map;
private int cacheSize;
/**
* Creates a new LRU cache.
* @param cacheSize the maximum number of entries that will be kept in this cache.
*/
public LRUCache (int cacheSize) {
this.cacheSize = cacheSize;
int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1;
map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) {
// (an anonymous inner class)
private static final long serialVersionUID = 1;
@Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {
return size() > LRUCache.this.cacheSize; }}; }
/**
* Retrieves an entry from the cache.<br>
* The retrieved entry becomes the MRU (most recently used) entry.
* @param key the key whose associated value is to be returned.
* @return the value associated to this key, or null if no value with this key exists in the cache.
*/
public synchronized V get (K key) {
return map.get(key); }
/**
* Adds an entry to this cache.
* The new entry becomes the MRU (most recently used) entry.
* If an entry with the specified key already exists in the cache, it is replaced by the new entry.
* If the cache is full, the LRU (least recently used) entry is removed from the cache.
* @param key the key with which the specified value is to be associated.
* @param value a value to be associated with the specified key.
*/
public synchronized void put (K key, V value) {
map.put (key, value); }
/**
* Clears the cache.
*/
public synchronized void clear() {
map.clear(); }
/**
* Returns the number of used entries in the cache.
* @return the number of entries currently in the cache.
*/
public synchronized int usedEntries() {
return map.size(); }
/**
* Returns a <code>Collection</code> that contains a copy of all cache entries.
* @return a <code>Collection</code> with a copy of the cache content.
*/
public synchronized Collection<Map.Entry<K,V>> getAll() {
return new ArrayList<Map.Entry<K,V>>(map.entrySet()); }
} // end class LRUCache
------------------------------------------------------------------------------------------
// Test routine for the LRUCache class.
public static void main (String[] args) {
LRUCache<String,String> c = new LRUCache<String, String>(3);
c.put ("1", "one"); // 1
c.put ("2", "two"); // 2 1
c.put ("3", "three"); // 3 2 1
c.put ("4", "four"); // 4 3 2
if (c.get("2") == null) throw new Error(); // 2 4 3
c.put ("5", "five"); // 5 2 4
c.put ("4", "second four"); // 4 5 2
// Verify cache content.
if (c.usedEntries() != 3) throw new Error();
if (!c.get("4").equals("second four")) throw new Error();
if (!c.get("5").equals("five")) throw new Error();
if (!c.get("2").equals("two")) throw new Error();
// List cache content.
for (Map.Entry<String, String> e : c.getAll())
System.out.println (e.getKey() + " : " + e.getValue()); }
代码出自：
http://www.source-code.biz/snippets/java/6.htm
下面有一个是用inheritance实现的，也贴出来。
LRULinkedHashMap
package com.xiaoc.cache;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
/**
* Least Recently Used LinkedHashMap based on LinkedHashMap
* @author wenchang872
* */
public class LRULinkedHashMap extends LinkedHashMap {
private static final long serialVersionUID = -1468138250444907129L;
private int maxCapacity;//max amount of key-value pairs
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
public LRULinkedHashMap(int maxCapacity) {
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
this.maxCapacity = maxCapacity;
}
/**
* remove the oldest element when size becomes larger than maxCapacity
*
* */
@Override
protected boolean removeEldestEntry(Entry eldest) {
return size() > this.maxCapacity;
}
}
BaseCache 基础缓存类，实际上是对LRULinkedHashMap添加同步包装, 并且只暴露需要的方法
get/put/cleanUp/toString
package com.xiaoc.cache;
import java.util.Collections;
import java.util.Map;
/**
* A Simple LRU Cache based on LRULinkedHashMap
* @author wenchang872
* */
public class BaseCache {
private Map cache = null;
private static final int DEFAULT_CAPACITY = 64;
public BaseCache(int capacity) {
//the cache should be synchronized
cache = Collections.synchronizedMap(new LRULinkedHashMap(capacity));
}
public BaseCache(){
this(DEFAULT_CAPACITY);
}
public void put(Object key, Object value) {
cache.put(key, value);
}
public Object get(Object key) {
return cache.get(key);
}
public void cleanUp() {
cache.clear();
}
public String toString() {
return cache.toString();
}
}
使用
/**
* useage:
* BaseCache cache = new BaseCache(1024);
* cache.get();
* cache.put(K,V);
* cache.cleanUp();
*/
代码出自：
http://www.qqread.com/java/2010/10/w496122.html
分享到：
相关推荐
LRU 缓存机制(java代码).docx
该资源是Java实现LRU算法的相关代码，将页面序号和进程分配的模块数，运行出具体的变化过程，真实可靠，可实现。
详细介绍了四种LRU算法，并有代码实现。
操作系统os 页面置换算法 （java实现） Clock.java Lru.java Opt.java Fifo.java
这是一个用java实现的 操作系统的 LRU算法
LRU_缓存策略_LRU_缓存.zip
c语言实现LRU缓存
LRU算法的java实现
“Python—LRU缓存.zip”是一个压缩文件，其中包含了使用Python实现的最近最少使用（Least Recently Used, LRU）缓存算法的代码和相关文档。LRU缓存算法是一种常用的缓存淘汰策略，它根据数据项最近被使用的时间来...
操作系统课设 lru算法的实现文档良心出品.pdf
链表（上）：如何实现LRU缓存淘汰算法
node-lru-native, 面向 node.js的高性能LRU缓存 node-lru-native这是 node.js 内存缓存的简单实现，支持 LRU ( least-recently-used ) 备份和 TTL expirations 。它是作为与( 精彩) node-lru-cache库的替代
java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例
资源来自pypi官网。 资源全名：lru-dict-1.1.6.tar.gz
资源来自pypi官网。 资源全名：backports.functools_lru_cache-1.3.tar.gz
java编的两种算法，word写的，看不懂，大家帮忙
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能: 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 2. get(key)：如果关键字 ...
LRU 缓存机制.md
LRU算法实现LRU算法实现LRU算法实现LRU算法实现LRU算法实现