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データ構造をより完全なものにするには、次のようにします.
 
1つのtreemap(アクセス回数と最後のアクセス時間に基づいてソート)を実現するentry要素には、アクセス回数と最後のアクセス時間フィールドが含まれ、get操作のたびにこの2つのフィールドが更新され、putのたびにsizeが設定されたcapacityを超えていることが判明すると、アクセス回数が最も少なく、最後のアクセス時間が最も長い要素が削除されます.