LinkedHashMapを単純なLRU／FIFOキャッシュとして使う

以前書いたキャッシュのエントリに、"極軽量でクラス1個でほどよく動くようなのないの？"みたいなコメントをいただいたので、それならLinkedHashMapを使えば？ということでご紹介。

知ってるといえば知っていましたが、以前は「Javaのキャッシュライブラリについて」書いたエントリだったので、こちらはスルーしていました。
※そのエントリも、そろそろ新しく書き直してもいいかも…

せっかくなので、メモとして書いておきましょう。

java.util.LinkedHashMapをちょっと拡張すると、簡単なLRUキャッシュやFIFOキャッシュを実装することができます。

ポイントとなるのは、LinkedHashMapのコンストラクタの第3引数、そしてremoveEldestEntryメソッドです。

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

コンストラクタの第3引数であるaccessOrderは、順序付けモードで「アクセス順ならtrue。挿入順ならfalse」となります。デフォルトはfalseで挿入順です。

removeEldestEntryメソッドは、「このマップが一番古いエントリを削除するはずの場合にtrueを返す」ように実装すればOKです。Javadocにサンプルがありますが、こちらを利用することでキャッシュに格納する最大数を絞ることができます。

実装する

それでは、簡単なキャッシュを実装してみます。

注）
今回の実装では、スレッドセーフについては考慮していません。実際に使う際に複数スレッドからアクセスされる可能性があるのであれば、必要に応じて同期化した実装とするなりしましょう。

まずはLRUキャッシュ。LinkedHashMapを継承して実装します。

src/main/java/org/littlewings/simplecache/SimpleLruCache.java

package org.littlewings.simplecache;

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

public class SimpleLruCache<K, V> extends LinkedHashMap<K, V> {
    protected int limit = 5;

    public SimpleLruCache() {
        super(16, 0.75F, true);
    }

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

コンストラクタで、LinkedHashMapのコンストラクタを第3引数をtrueで呼び出します。それ以外は、デフォルト値です。

    public SimpleLruCache() {
        super(16, 0.75F, true);
    }

また、removeEldestEntryメソッドでは、指定のサイズを超えるとtrueを返すように実装します。

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

今回は、サイズは5で決め打ちとしました。

続いて、FIFOキャッシュ。
src/main/java/org/littlewings/simplecache/SimpleFifoCache.java

package org.littlewings.simplecache;

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

public class SimpleFifoCache<K, V> extends LinkedHashMap<K, V> {
    protected int limit = 5;

    public SimpleFifoCache() {
        super(16, 0.75F, false);
    }

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

先ほどのLRUキャッシュとほとんど同じなのですが、LinkedHashMapのコンストラクタについては呼び出していますがすべてデフォルト値です。

    public SimpleFifoCache() {
        super(16, 0.75F, false);
    }

つまり、別に書かなくてもよかったと…。

removeEldestEntryで数を絞っているところだけが、通常のLinkedHashMapと違うところですね。

確認してみる

それでは、挙動をテストコード（JUnit＋AssertJ）で確認してみます。

まずはLRUキャッシュ。

    @Test
    public void testSimpleLruCache() {
        Map<String, String> cache = new SimpleLruCache<>();

        cache.put("key111", "value111");
        cache.put("key222", "value222");
        cache.put("key333", "value333");
        cache.put("key444", "value444");
        cache.put("key555", "value555");

        cache.get("key111");
        cache.get("key333");

        cache.put("key666", "value666");
        cache.put("key777", "value777");
        cache.put("key888", "value888");

        assertThat(cache)
                .hasSize(5)
                .containsOnly(MapEntry.entry("key111", "value111"),
                        MapEntry.entry("key333", "value333"),
                        MapEntry.entry("key666", "value666"),
                        MapEntry.entry("key777", "value777"),
                        MapEntry.entry("key888", "value888"));
    }

なんか、それっぽい挙動になっていますね？

続いてFIFOキャッシュ。

    @Test
    public void testSimpleFifoCache() {
        Map<String, String> cache = new SimpleFifoCache<>();

        cache.put("key111", "value111");
        cache.put("key222", "value222");
        cache.put("key333", "value333");
        cache.put("key444", "value444");
        cache.put("key555", "value555");

        cache.get("key111");
        cache.get("key333");

        cache.put("key666", "value666");
        cache.put("key777", "value777");
        cache.put("key888", "value888");

        assertThat(cache)
                .hasSize(5)
                .containsOnly(MapEntry.entry("key444", "value444"),
                        MapEntry.entry("key555", "value555"),
                        MapEntry.entry("key666", "value666"),
                        MapEntry.entry("key777", "value777"),
                        MapEntry.entry("key888", "value888"));
    }

とどのつまり、要素数が制限されたLinkedHashMapですね。

ところで、LRUキャッシュの場合ですが、この実装にすると通常のLinkedHashMapとしては使えないケースが出てきます。

accessOrder（コンストラクタ第3引数）をtrueにすると、「アクセス時にMapの状態が変わる」ことを意味するので、Map#keySetとか使ったりすると結果が微妙なことになります。

確認コードは、こちら。

    @Test
    public void testLruCacheBreakLinkedHashMap() {
        Map<String, String> cache = new SimpleLruCache<>();

        cache.put("key111", "value111");
        cache.put("key222", "value222");
        cache.put("key333", "value333");
        cache.put("key444", "value444");
        cache.put("key555", "value555");

        assertThatThrownBy(() -> {
            cache.keySet().forEach(k -> cache.get(k));
        })
                .isInstanceOf(ConcurrentModificationException.class)
                .hasMessage(null);

        cache.entrySet().forEach(e -> System.out.println(e));

        cache.get("key555");
        cache.get("key333");

        Map.Entry<?, ?>[] entries = cache.entrySet().toArray(new Map.Entry<?, ?>[cache.size()]);
        assertThat(entries[0].getKey()).isEqualTo("key222");
        assertThat(entries[1].getKey()).isEqualTo("key444");
        assertThat(entries[2].getKey()).isEqualTo("key111");
        assertThat(entries[3].getKey()).isEqualTo("key555");
        assertThat(entries[4].getKey()).isEqualTo("key333");
    }

Map#keySetでのループでMap#getとかすると、状態が変わるのでConcurrentModificationExceptionが飛ぶ、と…。

        assertThatThrownBy(() -> {
            cache.keySet().forEach(k -> cache.get(k));
        })
                .isInstanceOf(ConcurrentModificationException.class)
                .hasMessage(null);

Map#entrySetならOKです。

        cache.entrySet().forEach(e -> System.out.println(e));

イテレーションなら、たいていentrySetな気はしますが。

登録順も覚えておりません、と。なにせアクセス順で順序付けされていますので。

        Map.Entry<?, ?>[] entries = cache.entrySet().toArray(new Map.Entry<?, ?>[cache.size()]);
        assertThat(entries[0].getKey()).isEqualTo("key222");
        assertThat(entries[1].getKey()).isEqualTo("key444");
        assertThat(entries[2].getKey()).isEqualTo("key111");
        assertThat(entries[3].getKey()).isEqualTo("key555");
        assertThat(entries[4].getKey()).isEqualTo("key333");

FIFOキャッシュの場合は、単に数を絞ったLinkedHashMapなので、そのあたりは変わりません。

    @Test
    public void testFifoCacheOrdered() {
        Map<String, String> cache = new SimpleFifoCache<>();

        cache.put("key111", "value111");
        cache.put("key222", "value222");
        cache.put("key333", "value333");
        cache.put("key444", "value444");
        cache.put("key555", "value555");

        cache.keySet().forEach(k -> cache.get(k));
        cache.entrySet().forEach(e -> System.out.println(e));

        cache.get("key555");
        cache.get("key333");

        Map.Entry<?, ?>[] entries = cache.entrySet().toArray(new Map.Entry<?, ?>[cache.size()]);
        assertThat(entries[0].getKey()).isEqualTo("key111");
        assertThat(entries[1].getKey()).isEqualTo("key222");
        assertThat(entries[2].getKey()).isEqualTo("key333");
        assertThat(entries[3].getKey()).isEqualTo("key444");
        assertThat(entries[4].getKey()).isEqualTo("key555");
    }

その他

お手軽なキャッシュとして、WeakReferenceなど（ホントにお手軽かどうかはさておき…）が紹介されることもありますが、java.utilパッケージの身近な実装として、LinkedHashMapを使った例を書いてみました。

とはいえ、なんだかんだで有効期限くらいは欲しくなったりするような気がするので、単一NodeのシンプルなキャッシュならGuava Cache、もしくは無難にEhcache 2あたりを選ぶような気がしますけど。

できるなら、そうそう自作するものでもないかと。

CLOVER🍀

That was when it all began.

LinkedHashMapを単純なLRU／FIFOキャッシュとして使う

実装する

確認してみる

その他