LRU cache的兑现

LRU cache的实现

最简单的LRU cache的实现：

import java.util.LinkedHashMap;import java.util.concurrent.locks.Lock;import java.util.concurrent.locks.ReentrantLock;public class LruCache<K, V> extends LinkedHashMap<K, V> {/** *  */private static final long serialVersionUID = -3923317621052085848L;private int maxCapacity;private Lock lock = new ReentrantLock();public LruCache(int maxCapacity ) { super(maxCapacity + 1, 1f, true);// make it do not rehash ever,this.maxCapacity  = maxCapacity ;}@Overrideprotected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {return size() > this.maxCapacity;}@Overridepublic V put(K key, V value) {try {lock.lock();return super.put(key, value);} finally {              lock.unlock();          }  }@Overridepublic V get(Object key) {try {lock.lock();return super.get(key);} finally {              lock.unlock();          }  }}

?

ibatis中最LRU cache的实现：

import java.util.concurrent.locks.ReadWriteLock;public interface Cache {  String getId();  int getSize();  void putObject(Object key, Object value);  Object getObject(Object key);  Object removeObject(Object key);  void clear();  ReadWriteLock getReadWriteLock();}

import org.apache.ibatis.cache.Cache;import java.util.LinkedHashMap;import java.util.Map;import java.util.concurrent.locks.ReadWriteLock;/** * Lru (first in, first out) cache decorator */public class LruCache implements Cache {  private final Cache delegate;  private Map keyMap;  private Object eldestKey;  public LruCache(Cache delegate) {    this.delegate = delegate;    setSize(1024);  }  public String getId() {    return delegate.getId();  }  public int getSize() {    return delegate.getSize();  }  public void setSize(final int size) {    keyMap = new LinkedHashMap(size, .75F, true) {      protected boolean removeEldestEntry(Map.Entry eldest) {        boolean tooBig = size() > size;        if (tooBig) {          eldestKey = eldest.getKey();        }        return tooBig;      }    };  }  public void putObject(Object key, Object value) {    delegate.putObject(key, value);    cycleKeyList(key);  }  public Object getObject(Object key) {    keyMap.get(key); //touch    return delegate.getObject(key);  }  public Object removeObject(Object key) {    return delegate.removeObject(key);  }  public void clear() {    delegate.clear();    keyMap.clear();  }  public ReadWriteLock getReadWriteLock() {    return delegate.getReadWriteLock();  }  private void cycleKeyList(Object key) {    keyMap.put(key, key);    if (eldestKey != null) {      delegate.removeObject(eldestKey);      eldestKey = null;    }  }}

?

上面都是最简单的实现，如果要实现一个比较完善的LRU 数据结构可以这样：

?

实现一个treemap（根据访问次数和最后一次访问时间排序）的entry 元素包含访问次数和最后一次访问时间字段，每次get操作更新这两个字段，每次put的时候发现size已经超过设置的capacity，则删除访问次数最少和最后一次访问时间最久的那个元素。