LRU cache緩存簡單實現
LRU cache
LRU（最近最少使用）是一種常用的緩存淘汰機制。當緩存大小容量到達最大分配容量的時候，就會將緩存中最近訪問最少的對象刪除掉，以騰出空間給新來的數據。
實現
（1）單線程簡單版本
( 來源：力扣（LeetCode）鏈接： leetcode題目 )
題目： 設計和構建一個“最近最少使用”緩存，該緩存會刪除最近最少使用的項目。緩存應該從鍵映射到值(允許你插入和檢索特定鍵對應的值)，並在初始化時指定最大容量。當緩存被填滿時，它應該刪除最近最少使用的項目。它應該支持以下操作： 獲取數據 get 和 寫入數據 put 。
獲取數據 get(key) - 如果密鑰 (key) 存在於緩存中，則獲取密鑰的值（總是正數），否則返回 -1。
寫入數據 put(key, value) - 如果密鑰不存在，則寫入其數據值。當緩存容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而爲新的數據值留出空間。
思路： LinkedList + HashMap : LinkedList用來保存key的訪問情況，最近訪問的key將會放置到鏈表的最尾端，如果鏈表大小超過容量，移除鏈表的第一個節點，同時移除該key在hashmap中對應的鍵值對。程序如下：
class LRUCache {
private HashMap<Integer, Integer> hashMap = null;
private LinkedList<Integer> list = null;
private int capacity;
public LRUCache(int capacity) {
hashMap = new HashMap<>(capacity);
list = new LinkedList<Integer>();
this.capacity = capacity;
}
public int get(int key) {
if(hashMap.containsKey(key)){
list.remove((Object)key);
list.addLast(key);
return hashMap.get(key);
}
return -1;
}
public void put(int key, int value) {
if(list.contains((Integer)key)){
list.remove((Integer)key);
list.addLast((Integer)key);
hashMap.put(key, value);
return;
}
if(list.size() == capacity){
Integer v = list.get(0);
list.remove(0);
hashMap.remove((Object)v);
}
list.addLast(key);
hashMap.put(key, value);
}
}
（2）多線程併發版LRU Cache
與單線程思路類似，將HashMap和LinkedList換成支持線程安全的容器 ConcurrentHashMap和ConcurrentLinkedQueue結構。 ConcurrentLinkedQueue是一個基於鏈表，支持先進先出的的隊列結構，處理方法同單線程類似，只不過爲了保證多線程下的安全問題，我們會使用支持讀寫分離鎖的ReadWiterLock來保證線程安全。它可以實現：
1.同一時刻，多個線程同時讀取共享資源。
2.同一時刻，只允許單個線程進行寫操作。
/*
* 泛型中通配符
* ？ 表示不確定的 java 類型
* T (type) 表示具體的一個java類型
* K V (key value) 分別代表java鍵值中的Key Value
* E (element) 代表Element
*/
public class MyLRUCache<K, V> {
private final int capacity;
private ConcurrentHashMap<K, V> cacheMap;
private ConcurrentLinkedQueue<K> keys;
ReadWriteLock RWLock = new ReentrantReadWriteLock();
/*
* 讀寫鎖
*/
private Lock readLock = RWLock.readLock();
private Lock writeLock = RWLock.writeLock();
private ScheduledExecutorService scheduledExecutorService;
public MyLRUCache(int capacity) {
this.capacity = capacity;
cacheMap = new ConcurrentHashMap<>(capacity);
keys = new ConcurrentLinkedQueue<>();
scheduledExecutorService = Executors.newScheduledThreadPool(10);
}
public boolean put(K key, V value, long expireTime){
writeLock.lock();
try {
//需要注意containsKey和contains方法方法的區別
if(cacheMap.containsKey(key)){
keys.remove(key);
keys.add(key);
cacheMap.put(key, value);
return true;
}
if(cacheMap.size() == capacity){
K tmp = keys.poll();
if( key != null){
cacheMap.remove(tmp);
}
}
cacheMap.put(key, value);
keys.add(key);
if(expireTime > 0){
removeAfterExpireTime(key, expireTime);
}
return true;
}finally {
writeLock.unlock();
}
}
public V get(K key){
readLock.lock();
try {
if(cacheMap.containsKey(key)){
keys.remove(key);
keys.add(key);
return cacheMap.get(key);
}
return null;
}finally {
readLock.unlock();
}
}
public boolean remove(K key){
writeLock.lock();
try {
if(cacheMap.containsKey(key)){
cacheMap.remove(key);
keys.remove(key);
return true;
}
return false;
}finally {
writeLock.unlock();
}
}
private void removeAfterExpireTime(K key, long expireTime){
scheduledExecutorService.schedule(new Runnable() {
@Override
public void run() {
cacheMap.remove(key);
keys.remove(key);
}
}, expireTime, TimeUnit.MILLISECONDS);
}
public int size(){
return cacheMap.size();
}
}
在代碼中添加了設置鍵值對失效的put方法，通過使用一個定時器線程池保證過期鍵值對的及時清理。測試代碼如下：
public class LRUTest {
public static void main(String[] args) throws InterruptedException {
/*
MyLRUCache<String, Integer> myLruCache = new MyLRUCache(100000);
ExecutorService es = Executors.newFixedThreadPool(10);
AtomicInteger atomicInteger = new AtomicInteger(1);
CountDownLatch latch = new CountDownLatch(10);
long starttime = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
es.submit(new Runnable() {
@Override
public void run() {
for (int j = 0; j < 100000; j++) {
int v = atomicInteger.getAndIncrement();
myLruCache.put(Thread.currentThread().getName() + "_" + v, v, 200000);
}
latch.countDown();
}
});
}
latch.await();
long endtime = System.currentTimeMillis();
es.shutdown();
System.out.println("Cache size:" + myLruCache.size()); //Cache size:1000000
System.out.println("Time cost: " + (endtime - starttime));
*/
MyLRUCache<Integer, String> myLruCache = new MyLRUCache<>( 10);
myLruCache.put(1, "Java", 1000);
myLruCache.put(2, "C++", 2000);
myLruCache.put(3, "Java", 3000);
System.out.println(myLruCache.size());//3
Thread.sleep(2200);
System.out.println(myLruCache.size());//1
}
}
