LRU キャッシュを実装する

文字列としてユーザープロファイル情報を頻繁に取得する Web アプリケーションを開発しています。パフォーマンスを改善するため、これらのプロファイル文字列を保存し、どのエントリが最も最近使われていないかを判定できるシンプルなキャッシュを実装したいと考えています。

CacheEntry クラスはあらかじめ読み込まれています。

この演習はコースの一部です

Javaコード最適化

コースを見る

演習の手順

get() メソッド内で、指定された key に対応する cache のエントリを取得します。
key を取得したら、そのアクセス時刻を更新します。
エントリをキャッシュに追加した後、容量を超えていれば、最も最近使われていないエントリを削除します。

実践的なインタラクティブ演習

このサンプルコードを完成させて、この演習に挑戦してみましょう。

public class StringCache {
    private final int capacity = 100;
    private final Map cache = new HashMap<>();
    
    public String get(String key) {
        // Get the entry for the specified key
        CacheEntry entry = ____.get(____);
        if (entry == null) return null;
        // Update its access time
        entry.____();
        return entry.value;
    }
    
    public void put(String key, String value) {
        cache.put(key, new CacheEntry(value));
        if (cache.size() > capacity) {
            // If capacity exceeded, remove least recently used
            ____();
        }
    }

    void removeLeastRecentlyUsed() {
        String lruKey = null;
        long oldest = Long.MAX_VALUE;
        for (Map.Entry e : cache.entrySet()) {
            if (e.getValue().lastAccessed < oldest) {
                oldest = e.getValue().lastAccessed;
                lruKey = e.getKey();
            }
        }
        if (lruKey != null) { cache.remove(lruKey); }
    }

    public static void main(String[] args) {}
}

コードを編集して実行