LinkedHashMapでキャッシュを実現する

はじめに

LinkedHashMapを使えば、LRUキャッシュでもFIFOキャッシュでも簡単に実現できる。 ユーザプログラムの違いは微々たるものであっても、 内部処理には大きな差があるためパフォーマンスは異なる

使用事例

下のプログラムでは、エントリの上限を 700 としている。 上限を超えると自動的に削除される。

どれを削除するかについては、super の第三引数で、 最も参照時間が古いもの(LRU)とするか、登録が一番古いもの(FIFO)とするかを選べる。 第一引数は初期サイズ、HashMap ではハッシュ表に空きを作っておく必要がある。 第二引数は充足率を表す。0.75 は 25％の空きを残しておくことを意味する。

class NodeCache<K,V> extends LinkedHashMap<K,V> {
    protected int limit = 700;

    public NodeCache() {
        super(501, 0.75F, true);    // true: LRU, false: FIFO
    }

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

使い方は、次のようにして、インスタンスを生成する。

    static NodeCache<Integer,NodeBlock> cacheNodes = new NodeCache<>();

取り出しは cacheNodes.get(キー) とする。なかったときは null が返る。 下のプログラムでは、存在しなかった場合はファイルから読み込み、 cacheNodes.put(キー, 値) によって登録する。

        NodeBlock blk = cacheNodes.get(blockNumber);
        if (blk == null) {
            blk = load(blockNumber);
            if (blk == null) {
                System.out.printf("no file: blockNumber=%d\n", blockNumber);
                return Long.MIN_VALUE;   // エラー
            }
            cacheNodes.put(blockNumber, blk);
        }

リファレンス