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 ;
	}
	
	@Override
	protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
		return size() > this.maxCapacity;
	}
	
	@Override
	public V put(K key, V value) {
		try {
			lock.lock();
			return super.put(key, value);
		} finally {  
            lock.unlock();  
        }  
	}
	
	@Override
	public 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，则删除访问次数最少和最后一次访问时间最久的那个元素。