キャッシュ追い出し
01 / 共通の仕組み
容量固定のストアで、get も put も O(1)。 鍵はデータ構造 — 各方針は同じ問いへの違う答えだ:満杯のときどれを捨てるか? 古典的な 2 つは同じ O(1) のトリックを共有する。LRU はハッシュマップと双方向連結リストを組み合わせ、直前にアクセスされたキーを定数時間で先頭に移す。LFU はキーごとの頻度をバケットで管理し、最小頻度バケットを常に O(1) で取り出せるようにする。
02 / 一文で言うと
キーごとの頻度を頻度別バケットで追跡し、minFreq ポインタが常に追い出し候補のバケットを指す —— 「LFU を見つける」が O(N) 走査から O(1) になる。 同頻度時のタイブレークはバケット内 LRU。問題O(1) の LFU キャッシュを構築する容量4操作8
空の LFU キャッシュ、容量 4。8 個の操作を実行。
ステップ
0 / 13
現在の操作
—
minFreq
—
サイズ
0 / 4
0 / 13
03 / パターンの骨格
# 状態:map[k] → ノード;buckets[freq] = DLL;minFreqdef get(k):if k not in map: return −1node ← map[k]buckets[node.freq].remove(node)if buckets[minFreq] が空 and node.freq == minFreq: minFreq += 1node.freq += 1; buckets[node.freq].push_head(node)return node.val def put(k, v):if k in map: map[k].val ← v; get(k); returnif size == capacity:victim ← buckets[minFreq].pop_tail()map.delete(victim.key)node ← Node(k, v, freq=1)buckets[1].push_head(node); map[k] ← node; minFreq ← 1
04 / このパターンを使うべき合図
「頻度が近接性より優先」
LRU ではなく LFU を選ぶ理由は、ワークロードに安定したホットセットがあるとき —— 一部のキーが圧倒的に多く参照され、しばらく触られなくても残しておきたい場合だ。 頻度カウンタが主信号、近接性はタイブレーク用。
「タイブレークは近接性」
同一頻度バケット内では、双方向リストが挿入 / 昇格の順序を保持する。 新規は先頭に入り、追い出しは末尾から。 結果、同頻度の 2 キーは「最後に触れたのが古いほう」が淘汰される —— バケット内は純粋な LRU。 LFU は頻度で階層化された LRU。
「minFreq ポインタ」
整数 1 個で O(1) を成立させる要。各昇格は
minFreq を変えないか、buckets[minFreq] を空にした場合のみ +1 する。 新規挿入は常に 1 にリセット。走査もヒープも log もなく、純粋な記帳のみ。05 / よくある落とし穴
新規挿入時に
minFreq = 1 へ戻し忘れる。新規挿入は必ず
buckets[1] に頻度 1 で入る —— 直前の minFreq が何であろうと 1 にリセットしなければならない。 忘れると次の追い出しが間違ったバケットから取り、本来残すべきホットなキーを落としてしまう。昇格でバケットが空いたのに
minFreq を進めない。get が buckets[minFreq] の最後のノードを抜いたら、そのバケットは空になる ——minFreq は次の非空頻度(通常 minFreq + 1)へ進める必要がある。 忘れると次の追い出しが空バケットを見にいき、クラッシュするか、間違ったエントリを落とす。 この判定は「旧バケットから除去」直後の 1 箇所に置く。容量を確認する前に追い出す。
追い出しは「
size == capacity かつキーが新しい」とき限定。 無条件に追い出すと、更新や満杯前の挿入でも 1 件落ちてしまう —— キャッシュが満たされず、ヒット率が壊滅する。 分岐順序は更新?追い出し?挿入?の順に厳守。06 / LeetCode で練習
4 問。LFU Cache はこの構造の標準実装問。残り 3 問は形こそ違うが、 同じ「頻度の記帳」筋肉を要求する —— ハッシュマップ + バケットリストの骨格は同じ、不変量だけが違う。
— / どれをいつ使うか
LRU
シグナルが アクセスの新しさ のとき用いる — 直近に使ったものは再び使われやすい。 ハッシュマップが key → ノードを保ち、双方向連結リストが順序を保つ。 get / put は数本のポインタ操作とハッシュ参照 1 回、堂々の O(1)。
ハッシュマップ + 双方向連結リスト · LC 146
LFU
シグナルが アクセス頻度 のとき用いる — 最近触っていなくても、よく使われていたキーは新規挿入の冷たいキーに押し出されるべきではない。 ハッシュマップ → ノード、頻度ごとのバケットリスト、追い出し候補のバケットを指す `minFreq` ポインタ。 O(1) を維持するコストは記帳の増加。
ハッシュマップ + 頻度バケット · LC 460