LinkedHashMapを応用した、意外と便利なLRUCacheの実装

※この記事の内容は古いです。実用されるならこちらの記事も参照ください。

アプリケーションのパフォーマンス向上にキャッシュが有効なケースがあります。
memcachedをはじめとした分散型キャッシュのAPIやJava標準（候補）のJCacheを利用しても良いのですが、小規模ならばJavaヒープ内で完結するキャッシュを作成するのが手軽で効果的でしょう。

単にMapをキャッシュとして使ってしまうとJavaヒープを圧迫するため、再利用可能性が低い要素を捨てる仕組みを実装しましょう。LinkedHashMapにはLRUアルゴリズムによるキャッシュアウトを実装するために有効な2つの特徴が備わっており、これを利用するのがおすすめです。
1つめはアクセス順に要素を並べる機能。コンストラクタの第3引数にtrueを渡すことで利用可能になります。
2つめは新しく要素を追加する際に最も古い要素を削除するためのメソッドremoveEldestEntry。メソッドをオーバーライドすることで容易にキャッシュアウトの機能を組み込むことができます。

新しいエントリが追加されるたびに、このメソッドは一番古いエントリを削除する機会を実装側に提供します。これは、マップがキャッシュを表す場合に有効です。それにより、無効になったエントリを削除して、マップがメモリー消費を低減することができます。

http://java.sun.com/javase/ja/6/docs/ja/api/java/util/LinkedHashMap.html#removeEldestEntry(java.util.Map.Entry)

シンプルな実装は以下の通り。1メソッドをオーバーライドしているだけなので、無名クラスとしてコードに埋め込んでも問題ないサイズです。
LinkedHashMapを継承しているため、スレッドセーフではないことに注意してください。場合に応じて排他制御を行う必要があります。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
	private static final long serialVersionUID = -1882071901467368406L;
	static final int DEFAULT_INITIAL_CAPACITY = 16;
	static final float DEFAULT_LOAD_FACTOR = 0.75f;
	static final int DEFAULT_CACHE_SIZE = 1024;

	private final int cacheSize;

	public LRUCache() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CACHE_SIZE);
	}

	public LRUCache(int capacity, float loadFactor, int cacheSize) {
		super(capacity, loadFactor, true);
		this.cacheSize = cacheSize;
	}

	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
		return size() > cacheSize;
	}
}

FIFO版

「うなの日記」さんで、FIFO版のキャッシュが紹介されています。コンストラクタの第3引数をfalseにするだけです。
getメソッドのオーバーライドによるLRUキャッシュも載っています。

• LinkedHashMapでFIFO方式のキャッシュをさくっと作る。 - うなの日記

GCと連動するキャッシュ実装

大型のオブジェクトを多く格納する場合はSoftReferenceやWeakReferenceの併用を検討すると良いでしょう。GCに連動してJavaヒープを開放することが可能になります。