update1:第二個(gè)實(shí)現(xiàn)，讀操作不必要采用獨(dú)占鎖，緩存顯然是讀多于寫(xiě)，讀的時(shí)候一開(kāi)始用獨(dú)占鎖是考慮到要遞增計(jì)數(shù)和更新時(shí)間戳要加鎖，不過(guò)這兩個(gè)變量都是采用原子變量，因此也不必采用獨(dú)占鎖，修改為讀寫(xiě)鎖。
update2:一個(gè)錯(cuò)誤，老是寫(xiě)錯(cuò)關(guān)鍵字啊，
LRUCache的maxCapacity應(yīng)該聲明為volatile，而不是transient。
最簡(jiǎn)單的LRU算法實(shí)現(xiàn)，就是利用jdk的LinkedHashMap，覆寫(xiě)其中的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;
/**
* 類(lèi)說(shuō)明：利用LinkedHashMap實(shí)現(xiàn)簡(jiǎn)單的緩存， 必須實(shí)現(xiàn)removeEldestEntry方法，具體參見(jiàn)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算法是通過(guò)雙向鏈表來(lái)實(shí)現(xiàn)，當(dāng)某個(gè)位置被命中，通過(guò)調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到頭位置，新加入的內(nèi)容直接放在鏈表頭，如此一來(lái)，最近被命中的內(nèi)容就向鏈表頭移動(dòng)，需要替換時(shí)，鏈表最后的位置就是最近最少使用的位置。
LRU算法還可以通過(guò)計(jì)數(shù)來(lái)實(shí)現(xiàn)，緩存存儲(chǔ)的位置附帶一個(gè)計(jì)數(shù)器，當(dāng)命中時(shí)將計(jì)數(shù)器加1，替換時(shí)就查找計(jì)數(shù)最小的位置并替換，結(jié)合訪問(wèn)時(shí)間戳來(lái)實(shí)現(xiàn)。這種算法比較適合緩存數(shù)據(jù)量較小的場(chǎng)景，顯然，遍歷查找計(jì)數(shù)最小位置的時(shí)間復(fù)雜度為O(n)。我實(shí)現(xiàn)了一個(gè)，結(jié)合了訪問(wèn)時(shí)間戳，當(dāng)最小計(jì)數(shù)大于MINI_ACESS時(shí)(這個(gè)參數(shù)的調(diào)整對(duì)命中率有較大影響），就移除最久沒(méi)有被訪問(wèn)的項(xiàng)：
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 類(lèi)說(shuō)明：當(dāng)緩存數(shù)目不多時(shí)，才用緩存計(jì)數(shù)的傳統(tǒng)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; //保持可見(jiàn)性
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("開(kāi)始");
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();
}
}
/**
* 移除最近最少訪問(wèn)
*/
protected void removeRencentlyLeastAccess(
Set<Map.Entry<K, ValueEntry>> entries) {
// 最小使用次數(shù)
long least = 0;
// 訪問(wèn)時(shí)間最早
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);
// 如果最少使用次數(shù)大于MINI_ACCESS，那么移除訪問(wèn)時(shí)間最早的項(xiàng)(也就是最久沒(méi)有被訪問(wèn)的項(xiàng)）
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) {
// 更新訪問(wèn)時(shí)間戳
valueEntry.updateLastAccess();
// 更新訪問(wèn)次數(shù)
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());
}
}
}