缓存淘汰算法之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; 

 1/**
 2 * 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档
 3 * 
 4 * @author dennis
 5 * 
 6 * @param <K>
 7 * @param <V>
 8 */ 
 9public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { 
10    private final int maxCapacity; 

1    public LRULinkedHashMap(int maxCapacity) { 
2        super(maxCapacity, DEFAULT_LOAD_FACTOR, true); 
3        this.maxCapacity = maxCapacity; 
4    } 

 1    @Override 
 2    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { 
 3        return size() > maxCapacity; 
 4    } 
 5    @Override 
 6    public boolean containsKey(Object key) { 
 7        try { 
 8            lock.lock(); 
 9            return super.containsKey(key); 
10        } finally { 
11            lock.unlock(); 
12        } 
13    } 

1    @Override 
2    public V get(Object key) { 
3        try { 
4            lock.lock(); 
5            return super.get(key); 
6        } finally { 
7            lock.unlock(); 
8        } 
9    } 

1    @Override 
2    public V put(K key, V value) { 
3        try { 
4            lock.lock(); 
5            return super.put(key, value); 
6        } finally { 
7            lock.unlock(); 
8        } 
9    } 

1    public int size() { 
2        try { 
3            lock.lock(); 
4            return super.size(); 
5        } finally { 
6            lock.unlock(); 
7        } 
8    } 

1    public void clear() { 
2        try { 
3            lock.lock(); 
4            super.clear(); 
5        } finally { 
6            lock.unlock(); 
7        } 
8    } 

1    public Collection<Map.Entry<K, V>> getAll() { 
2        try { 
3            lock.lock(); 
4            return new ArrayList<Map.Entry<K, V>>(super.entrySet()); 
5        } finally { 
6            lock.unlock(); 
7        } 
8    } 
9}

 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}

 1public class LRUCache {
 2	/**
 3	 * 链表节点
 4	 * @author Administrator
 5	 *
 6	 */
 7	class CacheNode {
 8		CacheNode prev;//前一节点
 9		CacheNode next;//后一节点
10		Object value;//值
11		Object key;//键
12		CacheNode() {
13		}
14	}
15	public LRUCache(int i) {
16		currentSize = 0;
17		cacheSize = i;
18		nodes = new Hashtable(i);//缓存容器
19	}

 1	/**
 2	 * 获取缓存中对象
 3	 * @param key
 4	 * @return
 5	 */
 6	public Object get(Object key) {
 7		CacheNode node = (CacheNode) nodes.get(key);
 8		if (node != null) {
 9			moveToHead(node);
10			return node.value;
11		} else {
12			return null;
13		}
14	}

1	/**
2	 * 添加缓存
3	 * @param key
4	 * @param value
5	 */
6	public void put(Object key, Object value) {
7		CacheNode node = (CacheNode) nodes.get(key);

1		if (node == null) {
2			//缓存容器是否已经超过大小.
3			if (currentSize >= cacheSize) {
4				if (last != null)//将最少使用的删除
5					nodes.remove(last.key);
6				removeLast();
7			} else {
8				currentSize++;
9			}

 1			node = new CacheNode();
 2		}
 3		node.value = value;
 4		node.key = key;
 5		//将最新使用的节点放到链表头，表示最新使用的.
 6		moveToHead(node);
 7		nodes.put(key, node);
 8	}
 9	/**
10	 * 将缓存删除
11	 * @param key
12	 * @return
13	 */
14	public Object remove(Object key) {
15		CacheNode node = (CacheNode) nodes.get(key);
16		if (node != null) {
17			if (node.prev != null) {
18				node.prev.next = node.next;
19			}
20			if (node.next != null) {
21				node.next.prev = node.prev;
22			}
23			if (last == node)
24				last = node.prev;
25			if (first == node)
26				first = node.next;
27		}
28		return node;
29	}
30	public void clear() {
31		first = null;
32		last = null;
33	}
34	/**
35	 * 删除链表尾部节点
36	 *  表示 删除最少使用的缓存对象
37	 */
38	private void removeLast() {
39		//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
40		if (last != null) {
41			if (last.prev != null)
42				last.prev.next = null;
43			else
44				first = null;
45			last = last.prev;
46		}
47	}

 1	/**
 2	 * 移动到链表头，表示这个节点是最新使用过的
 3	 * @param node
 4	 */
 5	private void moveToHead(CacheNode node) {
 6		if (node == first)
 7			return;
 8		if (node.prev != null)
 9			node.prev.next = node.next;
10		if (node.next != null)
11			node.next.prev = node.prev;
12		if (last == node)
13			last = node.prev;
14		if (first != null) {
15			node.next = first;
16			first.prev = node;
17		}
18		first = node;
19		node.prev = null;
20		if (last == null)
21			last = first;
22	}
23	private int cacheSize;
24	private Hashtable nodes;//缓存容器
25	private int currentSize;
26	private CacheNode first;//链表头
27	private CacheNode last;//链表尾
28}