LRUキャッシュ とは？

まさにそのとおり！キャッシュの容量には限りがあるから、いっぱいになったときに「一番長いこと使ってないデータ」を捨てるルールだよ。冷蔵庫の中身を整理するとき、一番古くて手をつけてない食材から処分するのと同じだね。

そう！アクセスされるたびにそのデータは「最近使った」として先頭に移動するんだ。だから常に末尾にいるデータが一番長く触られてない、追い出し候補ってわけだね。

定番の実装はハッシュマップと双方向連結リストの組み合わせだよ。ハッシュマップでO(1)の高速検索を実現して、連結リストで順序を管理する。アクセスされたノードをリストの先頭に移動させるだけだから、挿入も削除もO(1)で済むんだ。

あるよ！LFU（Least Frequently Used）は使用頻度が一番低いものを追い出す方式。FIFO（First In, First Out）は入った順番に追い出す。あとARC（Adaptive Replacement Cache）は最近使った頻度と回数を両方考慮する賢いやつだね。

有名な話だね。LeetCodeの「LRU Cache」は定番中の定番で、計算量O(1)で get と put を実装する問題だよ。データ構造の理解度を見るのにちょうどいいから、面接で頻出なんだ。

Linux のページキャッシュ、CPU の L1/L2 キャッシュの置換ポリシー、Redis の maxmemory-policy、CDN のコンテンツキャッシュなど、至るところで使われているよ。Webブラウザがページをキャッシュする仕組みにもLRUの考え方が入っていたりするね。知っておくとシステム設計の議論がスムーズになるよ。