「バックグラウンドアプリはなぜ勝手に閉じる?」
スマホを使っていると一度は経験します。ずっと前に開いたアプリに戻ると最初の画面から起動し直すあれです。メモリが足りないので、OSが最も長く使っていないアプリをそっと終了したのです。
この動作を自分で作るとしましょう。ルールは単純です。
- •メモリには最近使ったアプリを最大N個だけ残す。
- •新しいアプリを起動して空きがなければ → 最も長く使っていないアプリを終了する。
- •アプリに切り替えると → そのアプリは再び『たった今使ったアプリ』になる。
例: N=3で
MAP → CAM → MSGの順に起動するとメモリは[MSG, CAM, MAP]。ここでMAPに切り替えるとMAPが最前面に上がり[MAP, MSG, CAM]。次に新しいアプリWEBを起動すると、最後尾にいたCAMが終了します。
気づきましたか? この「最近N個だけ残す」ルールこそがLRU（Least Recently Used）キャッシュです。
最初に思いつく解法 (そしてその限界)
最も単純には配列（リスト）1つで解きたくなります。使用順に並べておくのです。
アプリを使うたび: 配列から探して最前面へ移す
空きがなければ: 配列の最後尾を切り落とす順序はきれいに保たれます。でも「配列から探す」その一行が問題です。アプリがN個なら毎回最大Nマスを走査し、最前面へ移すために後ろの要素を順にずらす必要があります。動作1つがO(n)。呼び出しが10万回ならすぐ遅くなります。
では逆にハッシュマップはどうでしょう? 名前で探すのはO(1)で一瞬です。ところが決定的なものが抜けています。ハッシュマップは順序を覚えません。「今生きているアプリで最も古いのは誰?」に答えられないのです。終了するアプリを選べません。
| 方法 | 名前で探す | 最も古いアプリを知る |
|---|---|---|
| 配列だけ | O(n) ❌ | O(1) ✓ |
| ハッシュマップだけ | O(1) ✓ | 不可能 ❌ |
一方は検索が遅く、一方は順序が分からない。両方必要なのに。
なぜ「ハッシュマップ + 双方向連結リスト」?
ここで発想の転換が必要です。2つの構造の長所だけを合わせればいいのでは?
- •双方向連結リストで使用順を表します。最前面(HEAD)はたった今使ったアプリ、最後尾(TAIL)は最も古いアプリ。双方向（前後両方向）連結なので、どのノード1つでもO(1)で外して付け替えられます。
- •ハッシュマップで「アプリ名 → そのノードの位置」を保存します。だからリストを最初から走査せずに、目的のノードへO(1)でジャンプできます。
この2つが出会うと、魔法のようなことが起こります。
- •アプリ切替/再起動 → ハッシュマップでノードを探し(O(1))、そのノードをHEADの直後へ移動(O(1))。
- •メモリ超過 → TAILの直前のノードを削除(O(1))し、ハッシュマップからも消す。
全動作がO(1)。 配列の「順序は分かるが遅い」弱点と、ハッシュマップの「速いが順序を知らない」弱点が、互いをぴたりと補い合います。空間はアプリN個分、つまりO(N)です。
このパターンはOSのページ置換、データベース・CDNキャッシュ、ブラウザの戻る履歴など、「限られた空間に最近のものだけ残す」が必要なところに登場します。コーディングテストの定番テーマでもあります。
自分の目で確かめる
ハッシュマップでアプリを探し、そのノードがリストの最前面へ引き上げられ、メモリが満杯になった瞬間に最後尾のアプリが終了して抜けていく全工程をステップ別の可視化で用意しました。ハッシュマップと連結リストが一緒に変わる様子、switchToが命中/失敗する瞬間まで一目で分かります。