update1:第二个实现，读操作不必要采用独占锁，缓存显然是读多于写，读的时候一开始用独占锁是考虑到要递增计数和更新时间戳要加锁，不过这两个变量都是采用原子变量，因此也不必采用独占锁，修改为读写锁。
update2:一个错误，老是写错关键字啊，LRUCache的maxCapacity应该声明为volatile，而不是transient。 最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，如下所示： import java.util.ArrayList; import java.util.Collection; import java.util.LinkedHashMap; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; import java.util.Map; /** * 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档 * * @author dennis * * @param <K> * @param <V> */ public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { private final int maxCapacity; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final Lock lock = new ReentrantLock(); public LRULinkedHashMap( int maxCapacity) { super(maxCapacity, DEFAULT_LOAD_FACTOR, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { return size() > maxCapacity; } @Override public boolean containsKey(Object key) { try { lock.lock(); return super.containsKey(key); } finally { lock.unlock(); } } @Override public V get(Object key) { try { lock.lock(); return super.get(key); } finally { lock.unlock(); } } @Override public V put(K key, V value) { try { lock.lock(); return super.put(key, value); } finally { lock.unlock(); } } public int size() { try { lock.lock(); return super.size(); } finally { lock.unlock(); } } public void clear() { try { lock.lock(); super.clear(); } finally { lock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { lock.lock(); return new ArrayList<Map.Entry<K, V>>( super.entrySet()); } finally { lock.unlock(); } } }
如果你去看LinkedHashMap的源码可知，LRU算法是通过双向链表来实现，当某个位置被命中，通过调整链表的指向将该位置调整到头位置，新加入的内容直接放在链表头，如此一来，最近被命中的内容就向链表头移动，需要替换时，链表最后的位置就是最近最少使用的位置。
LRU算法还可以通过计数来实现，缓存存储的位置附带一个计数器，当命中时将计数器加1，替换时就查找计数最小的位置并替换，结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景，显然，遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个，结合了访问时间戳，当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响），就移除最久没有被访问的项： package net.rubyeye.codelib.util.concurrency.cache; import java.io.Serializable; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantLock; import java.util.concurrent.locks.ReentrantReadWriteLock; /** * * @author dennis 类说明：当缓存数目不多时，才用缓存计数的传统LRU算法 * @param <K> * @param <V> */ public class LRUCache<K, V> implements Serializable { private static final int DEFAULT_CAPACITY = 100; protected Map<K, ValueEntry> map; private final ReadWriteLock lock = new ReentrantReadWriteLock(); private final Lock readLock = lock.readLock(); private final Lock writeLock = lock.writeLock(); private final volatile int maxCapacity; //保持可见性 public static int MINI_ACCESS = 5; public LRUCache() { this(DEFAULT_CAPACITY); } public LRUCache( int capacity) { if (capacity <= 0) throw new RuntimeException("缓存容量不得小于0"); this.maxCapacity = capacity; this.map = new HashMap<K, ValueEntry>(maxCapacity); } public boolean ContainsKey(K key) { try { readLock.lock(); return this.map.containsKey(key); } finally { readLock.unlock(); } } public V put(K key, V value) { try { writeLock.lock(); if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) { // System.out.println("开始"); Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet(); removeRencentlyLeastAccess(entries); } ValueEntry new_value = new ValueEntry(value); ValueEntry old_value = map.put(key, new_value); if (old_value != null) { new_value.count = old_value.count; return old_value.value; } else return null; } finally { writeLock.unlock(); } } /** * 移除最近最少访问 */ protected void removeRencentlyLeastAccess( Set<Map.Entry<K, ValueEntry>> entries) { // 最小使用次数 long least = 0; // 访问时间最早 long earliest = 0; K toBeRemovedByCount = null; K toBeRemovedByTime = null; Iterator<Map.Entry<K, ValueEntry>> it = entries.iterator(); if (it.hasNext()) { Map.Entry<K, ValueEntry> valueEntry = it.next(); least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); earliest = valueEntry.getValue().lastAccess.get(); toBeRemovedByTime = valueEntry.getKey(); } while (it.hasNext()) { Map.Entry<K, ValueEntry> valueEntry = it.next(); if (valueEntry.getValue().count.get() < least) { least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); } if (valueEntry.getValue().lastAccess.get() < earliest) { earliest = valueEntry.getValue().count.get(); toBeRemovedByTime = valueEntry.getKey(); } } // System.out.println("remove:" + toBeRemoved); // 如果最少使用次数大于MINI_ACCESS，那么移除访问时间最早的项(也就是最久没有被访问的项） if (least > MINI_ACCESS) { map.remove(toBeRemovedByTime); } else { map.remove(toBeRemovedByCount); } } public V get(K key) { try { readLock.lock(); V value = null; ValueEntry valueEntry = map.get(key); if (valueEntry != null) { // 更新访问时间戳 valueEntry.updateLastAccess(); // 更新访问次数 valueEntry.count.incrementAndGet(); value = valueEntry.value; } return value; } finally { readLock.unlock(); } } public void clear() { try { writeLock.lock(); map.clear(); } finally { writeLock.unlock(); } } public int size() { try { readLock.lock(); return map.size(); } finally { readLock.unlock(); } } public long getCount(K key) { try { readLock.lock(); ValueEntry valueEntry = map.get(key); if (valueEntry != null) { return valueEntry.count.get(); } return 0; } finally { readLock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { readLock.lock(); Set<K> keys = map.keySet(); Map<K, V> tmp = new HashMap<K, V>(); for (K key : keys) { tmp.put(key, map.get(key).value); } return new ArrayList<Map.Entry<K, V>>(tmp.entrySet()); } finally { readLock.unlock(); } } class ValueEntry implements Serializable { private V value; private AtomicLong count; private AtomicLong lastAccess; public ValueEntry(V value) { this.value = value; this.count = new AtomicLong(0); lastAccess = new AtomicLong(System.nanoTime()); } public void updateLastAccess() { this.lastAccess.set(System.nanoTime()); } } }