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

  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	}
 20
 21	/**
 22	 * 获取缓存中对象
 23	 * @param key
 24	 * @return
 25	 */
 26	public Object get(Object key) {
 27		CacheNode node = (CacheNode) nodes.get(key);
 28		if (node != null) {
 29			moveToHead(node);
 30			return node.value;
 31		} else {
 32			return null;
 33		}
 34	}
 35
 36	/**
 37	 * 添加缓存
 38	 * @param key
 39	 * @param value
 40	 */
 41	public void put(Object key, Object value) {
 42		CacheNode node = (CacheNode) nodes.get(key);
 43
 44		if (node == null) {
 45			//缓存容器是否已经超过大小.
 46			if (currentSize >= cacheSize) {
 47				if (last != null)//将最少使用的删除
 48					nodes.remove(last.key);
 49				removeLast();
 50			} else {
 51				currentSize++;
 52			}
 53
 54			node = new CacheNode();
 55		}
 56		node.value = value;
 57		node.key = key;
 58		//将最新使用的节点放到链表头，表示最新使用的.
 59		moveToHead(node);
 60		nodes.put(key, node);
 61	}
 62	/**
 63	 * 将缓存删除
 64	 * @param key
 65	 * @return
 66	 */
 67	public Object remove(Object key) {
 68		CacheNode node = (CacheNode) nodes.get(key);
 69		if (node != null) {
 70			if (node.prev != null) {
 71				node.prev.next = node.next;
 72			}
 73			if (node.next != null) {
 74				node.next.prev = node.prev;
 75			}
 76			if (last == node)
 77				last = node.prev;
 78			if (first == node)
 79				first = node.next;
 80		}
 81		return node;
 82	}
 83	public void clear() {
 84		first = null;
 85		last = null;
 86	}
 87	/**
 88	 * 删除链表尾部节点
 89	 *  表示 删除最少使用的缓存对象
 90	 */
 91	private void removeLast() {
 92		//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
 93		if (last != null) {
 94			if (last.prev != null)
 95				last.prev.next = null;
 96			else
 97				first = null;
 98			last = last.prev;
 99		}
100	}
101
102	/**
103	 * 移动到链表头，表示这个节点是最新使用过的
104	 * @param node
105	 */
106	private void moveToHead(CacheNode node) {
107		if (node == first)
108			return;
109		if (node.prev != null)
110			node.prev.next = node.next;
111		if (node.next != null)
112			node.next.prev = node.prev;
113		if (last == node)
114			last = node.prev;
115		if (first != null) {
116			node.next = first;
117			first.prev = node;
118		}
119		first = node;
120		node.prev = null;
121		if (last == null)
122			last = first;
123	}
124	private int cacheSize;
125	private Hashtable nodes;//缓存容器
126	private int currentSize;
127	private CacheNode first;//链表头
128	private CacheNode last;//链表尾
129}