缓存淘汰算法之LRU（转载）

 1import java.util.ArrayList;
 2import java.util.Collection;
 3import java.util.LinkedHashMap;
 4import java.util.concurrent.locks.Lock;
 5import java.util.concurrent.locks.ReentrantLock;
 6import java.util.Map;
 7
 8
 9/**
10 * 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档
11 *
12 * @author dennis
13 *
14 * @param <K>
15 * @param <V>
16 */
17public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
18    private final int maxCapacity;
19
20    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
21
22    private final Lock lock = new ReentrantLock();
23
24    public LRULinkedHashMap(int maxCapacity) {
25        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
26        this.maxCapacity = maxCapacity;
27    }
28
29    @Override
30    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
31        return size() > maxCapacity;
32    }
33    @Override
34    public boolean containsKey(Object key) {
35        try {
36            lock.lock();
37            return super.containsKey(key);
38        } finally {
39            lock.unlock();
40        }
41    }
42
43
44    @Override
45    public V get(Object key) {
46        try {
47            lock.lock();
48            return super.get(key);
49        } finally {
50            lock.unlock();
51        }
52    }
53
54    @Override
55    public V put(K key, V value) {
56        try {
57            lock.lock();
58            return super.put(key, value);
59        } finally {
60            lock.unlock();
61        }
62    }
63
64    public int size() {
65        try {
66            lock.lock();
67            return super.size();
68        } finally {
69            lock.unlock();
70        }
71    }
72
73    public void clear() {
74        try {
75            lock.lock();
76            super.clear();
77        } finally {
78            lock.unlock();
79        }
80    }
81
82    public Collection<Map.Entry<K, V>> getAll() {
83        try {
84            lock.lock();
85            return new ArrayList<Map.Entry<K, V>>(super.entrySet());
86        } finally {
87            lock.unlock();
88        }
89    }
90}

  1public class LRUCache {
  2	/**
  3	 * 链表节点
  4	 * @author Administrator
  5	 *
  6	 */
  7	class CacheNode {
  8		……
  9	}
 10	private int cacheSize;//缓存大小
 11	private Hashtable nodes;//缓存容器
 12	private int currentSize;//当前缓存对象数量
 13	private CacheNode first;//(实现双链表)链表头
 14	private CacheNode last;//(实现双链表)链表尾
 15}
 16
 17 下面给出完整的实现，这个类也被Tomcat所使用（ org.apache.tomcat.util.collections.LRUCache），但是在tomcat6.x版本中，已经被弃用，使用另外其他的缓存类来替代它。
 18
 19public class LRUCache {
 20	/**
 21	 * 链表节点
 22	 * @author Administrator
 23	 *
 24	 */
 25	class CacheNode {
 26		CacheNode prev;//前一节点
 27		CacheNode next;//后一节点
 28		Object value;//值
 29		Object key;//键
 30		CacheNode() {
 31		}
 32	}
 33	public LRUCache(int i) {
 34		currentSize = 0;
 35		cacheSize = i;
 36		nodes = new Hashtable(i);//缓存容器
 37	}
 38
 39	/**
 40	 * 获取缓存中对象
 41	 * @param key
 42	 * @return
 43	 */
 44	public Object get(Object key) {
 45		CacheNode node = (CacheNode) nodes.get(key);
 46		if (node != null) {
 47			moveToHead(node);
 48			return node.value;
 49		} else {
 50			return null;
 51		}
 52	}
 53
 54	/**
 55	 * 添加缓存
 56	 * @param key
 57	 * @param value
 58	 */
 59	public void put(Object key, Object value) {
 60		CacheNode node = (CacheNode) nodes.get(key);
 61
 62		if (node == null) {
 63			//缓存容器是否已经超过大小.
 64			if (currentSize >= cacheSize) {
 65				if (last != null)//将最少使用的删除
 66					nodes.remove(last.key);
 67				removeLast();
 68			} else {
 69				currentSize++;
 70			}
 71
 72			node = new CacheNode();
 73		}
 74		node.value = value;
 75		node.key = key;
 76		//将最新使用的节点放到链表头，表示最新使用的.
 77		moveToHead(node);
 78		nodes.put(key, node);
 79	}
 80	/**
 81	 * 将缓存删除
 82	 * @param key
 83	 * @return
 84	 */
 85	public Object remove(Object key) {
 86		CacheNode node = (CacheNode) nodes.get(key);
 87		if (node != null) {
 88			if (node.prev != null) {
 89				node.prev.next = node.next;
 90			}
 91			if (node.next != null) {
 92				node.next.prev = node.prev;
 93			}
 94			if (last == node)
 95				last = node.prev;
 96			if (first == node)
 97				first = node.next;
 98		}
 99		return node;
100	}
101	public void clear() {
102		first = null;
103		last = null;
104	}
105	/**
106	 * 删除链表尾部节点
107	 *  表示 删除最少使用的缓存对象
108	 */
109	private void removeLast() {
110		//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
111		if (last != null) {
112			if (last.prev != null)
113				last.prev.next = null;
114			else
115				first = null;
116			last = last.prev;
117		}
118	}
119
120	/**
121	 * 移动到链表头，表示这个节点是最新使用过的
122	 * @param node
123	 */
124	private void moveToHead(CacheNode node) {
125		if (node == first)
126			return;
127		if (node.prev != null)
128			node.prev.next = node.next;
129		if (node.next != null)
130			node.next.prev = node.prev;
131		if (last == node)
132			last = node.prev;
133		if (first != null) {
134			node.next = first;
135			first.prev = node;
136		}
137		first = node;
138		node.prev = null;
139		if (last == null)
140			last = first;
141	}
142	private int cacheSize;
143	private Hashtable nodes;//缓存容器
144	private int currentSize;
145	private CacheNode first;//链表头
146	private CacheNode last;//链表尾
147}