始める無料で始める

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) {}
}
コードを編集して実行