LinkedHashMapを使った簡単なLRU Cacheを実現する

LinkedHashMapを使うと簡単なLRU Cacheを作れるということを最近知ったので、使い方とどう実現されているかを書いていきます。

LRUとは

小容量で高速な記憶装置（例えば、キャッシュメモリ）がいっぱいになったとき、その中にあるデータのうち、未使用の時間が最も長いデータを大容量で低速な記憶装置（例えば、主記憶装置）に保存する、というのが基本のアルゴリズムである

LinkedHashMapでの実装方法

LinkedHashMapのコンストラクタの第三引数で要素をinsert順で保存するかアクセス順で保存するかを指定することができます。defaultはfalse(insert順)になっているのでこれをtrueに変更します。

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

また、LinkedHashMap.removeEldestEntry()はデフォルトで以下の実装になっているので、これをオーバーライドして、先頭の要素を削除したい場合のみtrueを返す実装を書きます。

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

以上を踏まえて実装したのが以下のサンプルコードです。

class LRUCache<K, V>(
    capacity: Int
) : LinkedHashMap<K, V>(capacity, 0.75f, true) {

    private val limit = 3

    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
        return this.size > limit
    }
}

LRU Cacheがどうやって実現されているか

まず、コンストラクタの第三引数で与えたtrueがどう作用するかをみていきます。コンストラクタで与えられたtrueはaccessOrderという変数に格納されます。このaccessOrderは、要素の参照時(LinkedHashMap.getとLinkedHashMap.getOrDefaultを呼び出したとき)に、参照した要素をリストの先頭に持ってくる処理を呼び出すかどうかを判定するフラグです。このフラグをtrueを指定することで、参照した要素をリストの先頭に持ってくる処理が呼ばれます。

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }

ちなみに要素を先頭に持ってくる処理はLinkedHashMap.afterNodeAccess()というメソッドで実装されています。

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

次に、LinkedHashMap.removeEldestEntry()がどこで呼ばれているのかをみていきます。 removeEldestEntry()はLinkedHashMap.afterNodeInsertion()の中で先頭要素を削除するかどうかを判定する条件式の中で呼ばれています。 afterNodeInsertion()は、put(), putIfAbsent(),putMapEntries(), merge(), compute(), computeIfAbsent()といった要素を追加するメソッドを呼び出したときに内部で呼ばれるメソッドです。

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

サンプルコードでは、要素が追加された時に、キャッシュに保存された要素の数がlimitで設定した値を上回った場合に先頭の要素を削除する実装になっています。

実際に動かしてみる

実際に動かしてみると、limit(=3)を超えた場合一番古いデータが削除されていることと、参照されたデータが一番最新のデータになっていることを確認できます。

fun main(){

    val cache = LRUCache<String, String>(5)

    cache["1"] = "one"
    cache["2"] = "two"
    cache["3"] = "three"
    println(cache)  // {1=one, 2=two, 3=three}

    cache["4"] = "four"
    println(cache)  // {2=two, 3=three, 4=four}

    cache["2"]
    println(cache)  // {3=three, 4=four, 2=two}

    cache["5"] = "five"
    println(cache)  {4=four, 2=two, 5=five}
}