[Java] LRUキャッシュの実装

目的

• Java で LRUキャッシュを作る
• LRU は Least Recently Used の略で「捨てるのは、最も使われていないものから」という意味

参考: wikipedia: Least Recently Used

java.util.LinkedHashMapクラスを活用

LinkedHashMapクラスには以下のようなコンストラクタが存在します。

public LinkedHashMap(
        int initialCapacity,
        float loadFactor,
        boolean accessOrder)

前の２つの引数は HashMap 系ではおなじみですが、３つめの引数が特徴的なもので「順序付けモード」を指定します。

この「順序付けモード」は false だと「挿入順」（＝通常の LinkedHashMap と同じ動作）、true だと「アクセス順」になります。

つまり通常の LinkedHashMap のイテレータは挿入した順番に返しますが、これを true にすると、アクセス順（の逆順）で結果を返します。

もっと簡単に言えば「get() をすると該当の要素は一番後ろに移動する」ということです。

Map<String, String> map = new LinkedHashMap<>(15, 0.75f, true);

map.put("one", "1st");
map.put("two", "2nd");
map.put("three", "3rd");
System.out.println(map);

map.get("one");
System.out.println(map);

map.get("two");
System.out.println(map);

{one=1st, two=2nd, three=3rd}
{two=2nd, three=3rd, one=1st}
{three=3rd, one=1st, two=2nd}

また、LinkedHashMapには以下のようなメソッドが存在します。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

デフォルト実装では false を返しますが、このメソッドが true を返すとマップの一番古いもの（先頭の要素）が削除されます。

この２つを組み合わせると、個数を指定したLRUキャッシュを作成することができます。

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

/**
 * LRUキャッシュマップ
 */
public class LruCacheMap<K, V> extends LinkedHashMap<K, V> {
	/** シリアライズバージョン */
	private static final long serialVersionUID = 1L;

	/** キャッシュエントリ最大数 */
	private final int maxSize;

	/**
	 * 指定された最大数でインスタンスを生成
	 * @param maxSize 最大数
	 */
	public LruCacheMap(int maxSize) {
		super(15, 0.75f, true);
		this.maxSize = maxSize;
	}

	/** エントリの削除要否を判断 */
	@Override
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return size() > maxSize;
	}
}

gist: LruCacheMap.java

（順序付けモードを false にすれば、登録が古いものから捨てるキャッシュになります）

イテレータでの取得時の注意

この LRU キャッシュ、というか「順序付けモード」を「アクセス順」にした LinkedHashMap の場合には、get() でマップ構造が変わるので注意が必要になります。

具体的には、以下のようなアクセスをすると java.util.ConcurrentModificationException 例外が発生します。

Map<String, String> map = new LruCacheMap<>(10);
map.put("one", "1st");
map.put("two", "2nd");
map.put("three", "3rd");

for (String key : map.keySet()) {
    System.out.println(key + "=" + map.get(key));
    // ★ map.get() でマップ構造が変わるので、次の取得で例外発生！
}

一般的に、マップのキーと値をあわせて取得する場合には keySet() ではなく entrySet() を使うのが性能的に良いとされていると思います。

しかし、「順序付けモード」を「アクセス順」にしたときには性能うんぬんではなく、イテレータを使っている間に get() したら例外が発生するということは覚えておいたほうが良いと思います。

Map<String, String> map = new LruCacheMap<>(10);
map.put("one", "1st");
map.put("two", "2nd");
map.put("three", "3rd");

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
    // これなら OK!
}