LRUキャッシュ入門 - ハッシュマップ+双方向連結リストでget/putをO(1)にする仕組み

メモリは有限です。データベースの問い合わせ結果も、計算した関数の戻り値も、キャッシュにためておけば速くなりますが、際限なく貯め込むことはできません。どこかで「これ以上入らないので何かを捨てる」判断が必要になります。その「何を捨てるか」を決める最も定番のポリシーがLRU（Least Recently Used、最も長く使われていない）です。この記事では、LRUというポリシーの定義から、ハッシュマップと双方向連結リストを組み合わせてget/putを両方O(1)にする仕組み、Pythonでの自作実装、Redisや標準ライブラリでの実際の使われ方、LFU・FIFO・CLOCKといった他の置換アルゴリズムとの比較までを整理します。ハッシュテーブルの仕組みとヒープと優先度付きキュー入門と同じアルゴリズム入門シリーズの1本です。

キャッシュはなぜ「あふれる」のか

キャッシュの目的は、重い処理（DB問い合わせ・ネットワーク越しのAPI呼び出し・重い計算）の結果を保存しておき、同じ要求が来たときに再利用して高速に返すことです。ただしキャッシュ用のメモリは常に有限で、元データ（データベースやオリジンサーバー）の全量よりはるかに小さいのが普通です。したがって、容量が上限に達したら新しいデータを入れる前に、既存のどれかを追い出す必要があります。この「追い出す対象を決める規則」をキャッシュ置換ポリシー（cache replacement policy / eviction policy）と呼びます。

LRUというポリシー — 「最も長く使われていないもの」を捨てる

LRU（Least Recently Used）は、直近で最も長い間アクセスされていない要素を追い出す、というポリシーです。根底にあるのは時間的局所性（temporal locality）という経験則です。「最近使われたデータは、近い将来にもまた使われる可能性が高い」という仮定に立てば、逆に「最近まったく使われていないデータ」は将来も使われにくいと予測でき、それを優先して捨てるのが合理的というわけです。

他の代表的なポリシーとの違いを整理すると次のようになります。

FIFO（First In, First Out）: 入れた順番だけを見て、最も古く入れたものを追い出します。実装は単純ですが、「古いのに今もよく使われているデータ」まで追い出してしまう弱点があります
LFU（Least Frequently Used）: アクセス頻度が最も低いものを追い出します。頻度は覚えていますが「最近は使われていない」という時間の情報を直接は見ていないため、過去に集中的に使われて頻度だけ高くなった古いデータが居座り続けることがあります
LRU: 「最後に使われた時刻」という時間の情報だけを見ます。頻度は見ないので、1回だけ集中的にアクセスされたデータをすぐには追い出しにくい場面もあります

どれも「未来にまた使われそうなデータ」を予測しているだけで、正解を保証するものではありません。実際にどれが有利かはアクセスパターンに依存します。この記事の最後に、FIFO・LFUに加えて実装で近似的に使われるCLOCK（Second-Chance）も含めた比較表を用意しています。

なぜハッシュテーブルだけ・連結リストだけではO(1)にならないのか

LRUキャッシュに求められる操作は次の2つです。

get(key): キーに対応する値を取得する。取得できたら、そのキーは「今使われた」ので最新扱いにする
put(key, value): キーと値を登録する。容量を超える場合は、最も長く使われていないキーを追い出す

この両方をO(1)で実現したいのですが、片方のデータ構造だけでは足りません。

ハッシュテーブル（ハッシュテーブルの仕組みを参照）はキーから値への平均O(1)アクセスを提供しますが、「どのキーが最も古くから使われていないか」という使用順序の情報は持っていません。順序を知るには全キーの最終アクセス時刻を比べて回る必要があり、O(n)かかってしまいます。

一方、連結リストで使用順序を管理するだけなら、先頭を最新、末尾を最古として、アクセスされたノードを先頭へ動かせば順序は保てます。ただし、「キーXに対応するノードはどれか」を探すには先頭から辿るしかなく、これもO(n)です。さらに、単方向の連結リストだとノードを取り除くのに1つ前のノードへの参照が必要で、それを得るにも先頭から辿らねばなりません。

つまり、片方だけでは「速い検索」と「速い順序更新」のどちらかしか手に入りません。この2つを両立させるのが、次の組み合わせです。

ハッシュマップ+双方向連結リストで両方をO(1)にする

LRUキャッシュの定石は、次の2つを組み合わせる構成です。

ハッシュマップ: キーから、連結リスト上のノードへの参照をO(1)で引く
双方向連結リスト: ノードをアクセス順（先頭=最新、末尾=最古）に並べておく

ハッシュマップが「ノードの場所」を即座に教えてくれるので、連結リストを先頭から辿る必要がなくなります。そして連結リストが双方向（各ノードがprevとnextの両方を持つ）であることが重要です。ノードへの参照さえ手元にあれば、そのprevとnextをつなぎ替えるだけでノードをO(1)で取り除け、先頭にO(1)で挿入し直せます。単方向リストではこの「参照だけで取り除く」操作ができません。

処理の流れは次のようになります。

get(key): ハッシュマップでノードをO(1)で見つける -> リストからノードをO(1)で外す -> 先頭にO(1)で挿入し直す
put(key, value): 既存キーなら値を更新して先頭へ移動。新規キーで容量超過なら、末尾（最古）のノードをO(1)で取り除いてハッシュマップからも削除し、新しいノードを先頭にO(1)で追加する

すべての操作がノード数に依存しない定数時間で完結するため、get・putともにO(1)が実現できます。

Pythonで自作するLRUCache

実際に手を動かして組んでみます。境界条件（先頭・末尾の付け外し）を素直に書けるように、実データを持たないダミーの先頭ノード（head）と末尾ノード（tail）を用意するのが定石です。

class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
 
 
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                # key -> Node、O(1)でノードを探すためのハッシュマップ
        self.head = Node()           # ダミーの先頭。head.next側が最新
        self.tail = Node()           # ダミーの末尾。tail.prev側が最古
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node):
        # ノードを双方向リストから外す。参照があるのでO(1)
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_to_front(self, node):
        # head の直後（=最新の位置）にノードを挿入する。O(1)
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)     # アクセスされたので最新扱いに更新
        return node.value
 
    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.map) >= self.capacity:
            lru = self.tail.prev     # tail.prev = 最も長く使われていないノード
            self._remove(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_to_front(node)

これだけで、get・putともにO(1)のLRUキャッシュになります。容量はcapacity引数で決め、超過時はtail.prev（末尾の直前、つまり最古のノード）を追い出します。

実行してみる

操作列を1つずつ実行し、その都度の挙動を確認します。

cache = LRUCache(2)
 
cache.put(1, "A")
cache.put(2, "B")
print(cache.get(1))    # "A" -- 1が最新扱いになり、順序は [1, 2]（1が最新）
cache.put(3, "C")       # 容量2を超えるので、最も長く使われていない2が追い出される -> [3, 1]
print(cache.get(2))     # -1 -- 2はすでに追い出されている
cache.put(4, "D")       # さらに追加。今度は1が追い出される -> [4, 3]
print(cache.get(1))     # -1 -- 1も追い出し済み
print(cache.get(3))     # "C" -- 3は残っている
print(cache.get(4))     # "D"

cache.get(1)を呼んだ時点で1が「最新」に更新されるため、その後put(3, "C")で追い出されるのは2になります。1を先に触ったおかげで1が生き残る、というのがLRUの効きどころです。

実世界での使われ方

Redisのeviction policy

Redisはmaxmemoryでメモリ上限を設定でき、上限に達するとmaxmemory-policyで指定したポリシーに従ってキーを追い出します。公式ドキュメントによれば、主なポリシーは次の通りです。

noeviction: 追い出しをせず、新規データを書き込むコマンドはエラーを返す（読み取りは可能）
allkeys-lru: 全キーの中からLRUで追い出す
volatile-lru: 有効期限（TTL）が設定されたキーの中からLRUで追い出す
allkeys-lfu / volatile-lfu: LFU（頻度）で追い出す（Redis 4.0以降）
allkeys-random / volatile-random: ランダムに追い出す
volatile-ttl: TTLが設定されたキーの中から、残りTTLが最も短いものを追い出す

公式ドキュメントは「アクセスの一部（Pareto principleに沿うような偏った一部のキー）が頻繁にアクセスされる典型的なケースではallkeys-lruが良いデフォルトの選択肢」としています。

ここで重要な注意点があります。RedisのLRUは厳密なLRUではなく近似LRU（approximated LRU）です。公式ドキュメントの説明では、追い出しのたびに全キーの最終アクセス時刻を比べるのはコストが高いため、Redisは少数のキーをランダムにサンプリングし、その中で最もアクセスされていないものを追い出すという近似で済ませています。サンプリングするキー数はmaxmemory-samples（デフォルト5）で調整でき、Redis 3.0以降は候補プールを保持する改良により、サンプル数を増やすほど厳密なLRUに近づくとされています。なお2026年7月時点の公式ドキュメントでは、Redis 8.6以降で書き込み時のみタイムスタンプを更新するLRM（Least Recently Modified）という新しいポリシー（allkeys-lrm/volatile-lrm）も追加されていることが確認できました。

Pythonの functools.lru_cache

Python標準ライブラリのfunctools.lru_cacheは、関数の戻り値をLRU方式でキャッシュするデコレータです。公式ドキュメントで確認できる仕様は次の通りです。

デフォルトのmaxsizeは128。maxsize=NoneにするとLRUによる追い出しが無効になり、キャッシュは無制限に増え続けます
typed=Trueにすると、引数の型が違う呼び出し（例: f(3)とf(3.0)）を別々のキャッシュエントリとして扱います
キャッシュ状況はcache_info()（hits/misses/maxsize/currsizeを持つ名前付きタプル）で確認でき、cache_clear()でクリアできます
Python 3.9で追加されたfunctools.cacheは、lru_cache(maxsize=None)と同じ動作をする、追い出し処理を持たないシンプルな無制限キャッシュです

from functools import lru_cache, cache
 
@lru_cache(maxsize=128)
def slow_square(n):
    return n * n
 
slow_square(4)
slow_square(4)          # 2回目はキャッシュから即返る
print(slow_square.cache_info())   # CacheInfo(hits=1, misses=1, maxsize=128, currsize=1)
 
@cache                  # lru_cache(maxsize=None) と同義（Python 3.9+）
def factorial(n):
    return n * factorial(n - 1) if n else 1

内部実装も、この記事のPython自作版と同じ発想です。CPythonのfunctools.pyのソースを確認すると、_lru_cache_wrapperはキーからノードを引くための辞書（cache）と、アクセス順を保持する循環双方向連結リスト（rootを起点とするリンク構造）を組み合わせて実装されています。関数キャッシュという用途向けの実装ですが、構成要素は本記事のハッシュマップ+双方向連結リストとまったく同じです。

OSのページキャッシュ・CPUキャッシュ、ブラウザのHTTPキャッシュ

OSのページキャッシュやCPUキャッシュでも「これから使われそうなデータを残す」という考え方は共通ですが、アクセスのたびに厳密な順序を更新するコストが高いため、実装では近似LRUが使われることが一般的です。代表例が参照ビットを使うCLOCK（Second-Chance）アルゴリズムで、円環状に並んだページを巡回しながら、参照ビットが立っていなければ追い出し対象にし、立っていればビットを下ろして次の候補に進める、という安価な近似です。この仕組みとFIFO・LRUとの違い、Beladyの不都合（アノマリー）については仮想メモリとページングの仕組みで図解しています。

ブラウザのHTTPキャッシュも、保存容量の上限に達すれば古い（使われていない）リソースから破棄していく点でLRU的な発想を採用していますが、具体的な実装アルゴリズムやパラメータはブラウザ・バージョンごとに異なり、本記事執筆時点で単一の一次ソースから断定できる共通仕様は確認できませんでした（未確認）。HTTPキャッシュそのものの制御（Cache-Control・TTL設計）についてはCDNキャッシュ設計の基本で扱っています。

他の置換アルゴリズムとの比較

ポリシー	判定基準	実装コスト	特徴・弱点
LRU	最後に使われた時刻が最も古いもの	厳密版は高い（本記事の構成が必要）	時間的局所性に強いが、1回だけ大量アクセスされた直後のデータを過大評価しやすい
LFU	アクセス頻度が最も低いもの	カウンタ管理が必要	長期的な人気を捉えやすいが、過去に人気だった古いデータが居座りやすい
FIFO	最も古く入れたもの	単純（キューだけで済む）	実装は簡単だが、古くても今も使われているデータまで追い出しうる
CLOCK（Second-Chance）	参照ビットで近似的に選ぶ	低い（ビット1つと巡回ポインタ）	厳密なLRUを安価に近似。OSのページ置換やRedisの近似LRUで広く使われる
Random	ランダムに選ぶ	最も単純	アクセス頻度がほぼ均等な場合に有効。予測不能な劣化はしにくい

Redisのように「厳密なLRUをそのまま実装するとコストが高いので、サンプリングやビットで近似する」という判断は、CPUキャッシュやOSのページ置換でも共通して見られる考え方です。厳密さと実装コストのトレードオフを常に意識しておくと、なぜ多くの実システムが「LRUそのもの」ではなく「LRU的な近似」を採用しているのかが腑に落ちます。

よくある落とし穴

ハッシュマップだけ、連結リストだけではO(1)にならない: 検索が速いか順序更新が速いかのどちらかしか得られません。両方を組み合わせる必要があります
単方向連結リストでは不十分: ノードを取り除くには1つ前のノードへの参照が要るため、双方向でなければO(1)削除ができません
厳密なLRUと近似LRUの混同: Redisのように実運用では多くがサンプリングベースの近似です。「LRU」という名前だけで厳密な順序保証を期待すると挙動の見え方が変わります
キャッシュに向かない関数をlru_cacheで包む: 副作用のある関数、毎回異なるミュータブルオブジェクトを返す関数、time()やrandom()のような非純粋関数はキャッシュに向きません（Python公式ドキュメントの注意点）
容量を大きくしすぎる/小さくしすぎる: 容量が小さすぎるとヒット率が上がらず、大きすぎるとメモリを圧迫します。RedisのINFOが返すkeyspace_hits/keyspace_missesのようなヒット率の指標を見ながら調整するのが定石です

データ構造としての土台を押さえたいならハッシュテーブルの仕組み、優先度に基づく取り出しの発想を広げたいならヒープと優先度付きキュー入門、計算量の記法に不安があれば計算量とBig-O記法入門も合わせて読むと理解が深まります。

まとめ

LRUは「最も長く使われていないもの」を追い出すキャッシュ置換ポリシーで、時間的局所性の仮定に基づく
ハッシュマップ単体では使用順序が分からず、連結リスト単体ではキーからノードを探すのにO(n)かかる。ハッシュマップ+双方向連結リストの組み合わせで、get・putともにO(1)が実現できる
双方向であることが重要。ノードへの参照だけでO(1)で取り除き、先頭にO(1)で挿入し直せるのはprev/nextの両方があるからこそ
Redisのallkeys-lru等は近似LRU（サンプリングベース）、Pythonのfunctools.lru_cacheは内部で辞書+循環双方向連結リストを使い、maxsizeのデフォルトは128
LFU（頻度）・FIFO（挿入順）・CLOCK（参照ビットによる近似）など、置換アルゴリズムには複数の選択肢があり、それぞれ得意なアクセスパターンが異なる

まずは自作のLRUCacheクラスを手元で動かし、getのたびにノードが先頭へ動いていく様子と、容量超過時に末尾のノードが追い出される様子を1行ずつ追ってみてください。ハッシュマップと双方向連結リストがそれぞれ何を担っているかが、体感としてつながるはずです。

LRUキャッシュ入門 - ハッシュマップ+双方向連結リストでget/putをO(1)にする仕組み

キャッシュはなぜ「あふれる」のか

LRUというポリシー — 「最も長く使われていないもの」を捨てる

なぜハッシュテーブルだけ・連結リストだけではO(1)にならないのか

ハッシュマップ+双方向連結リストで両方をO(1)にする

Pythonで自作するLRUCache

実行してみる

実世界での使われ方

Redisのeviction policy

Pythonの functools.lru_cache

OSのページキャッシュ・CPUキャッシュ、ブラウザのHTTPキャッシュ

他の置換アルゴリズムとの比較

よくある落とし穴

まとめ

参考リンク

Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

ヒープと優先度付きキュー入門 - O(log n)で最小・最大を取り出すデータ構造

二分探索(バイナリサーチ)入門 - O(log n) で探索範囲を半分ずつ狭める

キャッシュはなぜ「あふれる」のか

LRUというポリシー — 「最も長く使われていないもの」を捨てる

なぜハッシュテーブルだけ・連結リストだけではO(1)にならないのか

ハッシュマップ+双方向連結リストで両方をO(1)にする

Pythonで自作するLRUCache

実行してみる

実世界での使われ方

Redisのeviction policy

Pythonの functools.lru_cache

OSのページキャッシュ・CPUキャッシュ、ブラウザのHTTPキャッシュ

他の置換アルゴリズムとの比較

よくある落とし穴

まとめ

参考リンク

関連記事

Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

ヒープと優先度付きキュー入門 - O(log n)で最小・最大を取り出すデータ構造

二分探索(バイナリサーチ)入門 - O(log n) で探索範囲を半分ずつ狭める