0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Karentia

TypeScriptでLRU CacheをO(1)実装する：面接で説明できるHashMap＋双方向リスト

0
Posted at

原文の背景メモ: https://www.aceround.app/ja/blog/backend-developer-interview-ai
この記事は、バックエンド面接で出やすい「キャッシュをどう設計・実装するか」という論点を、Qiita向けにLRU Cacheの実装問題として再構成したものです。

結論

LRU Cacheを面接で説明するなら、Mapだけの小技よりも、HashMap + 双方向リストの構成で話すのが安全です。

  • get(key) は値を返し、そのキーを「最近使った」位置へ移動します。
  • put(key, value) は値を追加・更新し、容量を超えたら「最も使われていない」キーを捨てます。
  • HashMapでキーからノードへ直接到達し、双方向リストで順序の入れ替えと末尾削除をします。
  • これで get / put ともに平均 O(1) になります。

JavaScript / TypeScriptでは Map が挿入順を保持するため、実務では delete して set し直す簡易LRUも書けます。ただしライブコーディング面接では、データ構造の理解を見られることが多いので、ここでは明示的に双方向リストを実装します。

問題設定

容量 capacity を持つキャッシュを作ります。

const cache = new LRUCache<string, number>(2);
cache.put('A', 1);           // A
cache.put('B', 2);           // B, A
cache.get('A');              // A, B になる
cache.put('C', 3);           // C, A になり、B が削除される

ここで、左側を「最も最近使った要素」、右側を「最も古い要素」とします。

必要な操作は次の2つです。

get(key): value | undefined
put(key, value): void

get したキーも「使われた」とみなす点が重要です。読み取りだけでも順序が変わります。

なぜ HashMap だけでは足りないのか

HashMapは key -> value の検索を O(1) にできます。しかし、「どのキーが最も古いか」を直接は教えてくれません。

一方、配列や単方向リストで順序を管理すると、途中の要素を削除して先頭へ移動する操作が O(n) になります。

そこで、役割を分けます。

役割 データ構造 理由
キーから該当要素を探す Map<K, Node> 平均 O(1) でノードへ到達するため
最近使った順序を保つ 双方向リスト 任意ノードの削除・先頭追加を O(1) にするため

この2つを組み合わせると、検索と順序更新の両方を定数時間で処理できます。

不変条件を先に決める

実装前に、不変条件を3つに絞るとバグが減ります。

  1. map は key -> list node を持ちます。
  2. head.next が最も最近使ったノード、tail.prev が最も古いノードです。
  3. キャッシュ内の実データは、必ず map とリストの両方に存在します。

head と tail は番兵ノードです。番兵を置くと、空リスト・先頭・末尾の分岐を減らせます。

head <-> most recent <-> ... <-> least recent <-> tail

TypeScript実装

type NodeRef<K, V> = {
  key?: K;
  value?: V;
  prev: NodeRef<K, V> | null;
  next: NodeRef<K, V> | null;
};

class LRUCache<K, V> {
  private readonly map = new Map<K, NodeRef<K, V>>();
  private readonly head: NodeRef<K, V> = { prev: null, next: null };
  private readonly tail: NodeRef<K, V> = { prev: null, next: null };

  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new Error('capacity must be a positive integer');
    }
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;

    this.moveToFront(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.moveToFront(existing);
      return;
    }

    const node: NodeRef<K, V> = { key, value, prev: null, next: null };
    this.map.set(key, node);
    this.addToFront(node);

    if (this.map.size > this.capacity) {
      this.evictLeastRecentlyUsed();
    }
  }

  entriesMostRecentFirst(): Array<[K, V]> {
    const result: Array<[K, V]> = [];
    let current = this.head.next;

    while (current && current !== this.tail) {
      result.push([current.key as K, current.value as V]);
      current = current.next;
    }

    return result;
  }

  private moveToFront(node: NodeRef<K, V>): void {
    this.remove(node);
    this.addToFront(node);
  }

  private addToFront(node: NodeRef<K, V>): void {
    const first = this.head.next;
    if (!first) throw new Error('broken list: head.next is missing');

    node.prev = this.head;
    node.next = first;
    first.prev = node;
    this.head.next = node;
  }

  private remove(node: NodeRef<K, V>): void {
    if (!node.prev || !node.next) {
      throw new Error('broken list: node is detached');
    }

    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
  }

  private evictLeastRecentlyUsed(): void {
    const lru = this.tail.prev;
    if (!lru || lru === this.head || lru.key === undefined) {
      throw new Error('broken list: LRU node is missing');
    }

    this.remove(lru);
    this.map.delete(lru.key);
  }
}

entriesMostRecentFirst は動作確認用です。本番のキャッシュAPIには必須ではありません。

動かして確認する

const cache = new LRUCache<string, number>(2);

cache.put('A', 1);           // A
cache.put('B', 2);           // B, A
console.log(cache.get('A')); // 1 => A, B

cache.put('C', 3);           // C, A（Bが削除される）
console.log(cache.get('B')); // undefined

cache.put('A', 10);          // A, C
console.log(cache.entriesMostRecentFirst());

出力は次のようになります。

1
undefined
[ [ 'A', 10 ], [ 'C', 3 ] ]

Bunならこのまま実行できます。

bun lru-cache.ts

get の流れを分解する

get('A') でやっていることは2つだけです。

  1. map.get('A') でノードを探します。
  2. 見つかったノードをリストの先頭へ移動します。

先頭へ移動する処理は、さらに次の2段階です。

this.remove(node);
this.addToFront(node);

双方向リストなので、ノード自身が前後の参照を持っています。そのため、リスト全体を走査せずに取り外せます。

before:
head <-> B <-> A <-> tail

get('A') after remove + addToFront:
head <-> A <-> B <-> tail

この「途中ノードを O(1) で外せる」点が、単方向リストではなく双方向リストを使う理由です。

put の流れを分解する

put は、既存キーか新規キーかで分岐します。

既存キーの場合

値を上書きし、最近使った扱いにします。

const existing = this.map.get(key);
if (existing) {
  existing.value = value;
  this.moveToFront(existing);
  return;
}

ここで容量は増えません。削除も不要です。

新規キーの場合

新しいノードを作って先頭に追加します。

const node: NodeRef<K, V> = { key, value, prev: null, next: null };
this.map.set(key, node);
this.addToFront(node);

その後、容量を超えた場合だけ末尾側を削除します。

if (this.map.size > this.capacity) {
  this.evictLeastRecentlyUsed();
}

最も古いノードは常に tail.prev です。ここも走査しません。

計算量

操作 計算量 理由
get 平均 O(1) Map検索 + 双方向リストの付け替え
put 平均 O(1) Map更新 + 先頭追加 + 必要なら末尾削除
空間 O(capacity) 最大で容量分のノードとMap要素を持つ

厳密にはJavaScriptの Map はハッシュテーブル相当の平均 O(1) として扱います。面接では「平均」と一言添えると誠実です。

面接での説明テンプレート

ライブコーディングでは、コードを書く前に次の順番で説明すると通じやすいです。

  1. 「キー検索はHashMapで O(1) にします」
  2. 「LRU順序は双方向リストで持ちます」
  3. 「リストの先頭をmost recent、末尾をleast recentにします」
  4. 「get されたノードは先頭へ移動します」
  5. 「put で容量を超えたら末尾の直前を削除します」

この説明を先に置くと、実装中に多少詰まっても、面接官は設計意図を追いやすくなります。

よくあるバグ

1. get で順序を更新し忘れる

LRUの「used」は書き込みだけではありません。読み取りも使用です。get で先頭へ移動しないと、頻繁に読まれているキーが誤って削除されます。

2. map.delete を忘れる

リストからノードを外しただけでは、map に古い参照が残ります。削除時は必ず両方を更新します。

this.remove(lru);
this.map.delete(lru.key);

3. 先頭・末尾の分岐が増えすぎる

番兵ノードを使わない実装では、空リスト、要素1個、先頭削除、末尾削除の分岐が増えます。面接ではバグりやすいので、head / tail の番兵を使うのがおすすめです。

4. 容量1のケースを確認しない

capacity = 1 は良いテストケースです。

const c = new LRUCache<string, number>(1);
c.put('A', 1);
c.put('B', 2);
console.log(c.get('A')); // undefined
console.log(c.get('B')); // 2

ここで壊れる実装は、削除処理か番兵のつなぎ替えに問題があります。

Mapの挿入順だけで書く簡易版について

TypeScript実務では、次のような簡易実装も可能です。

class SimpleLRU<K, V> {
  private readonly map = new Map<K, V>();

  constructor(private readonly capacity: number) {}

  get(key: K): V | undefined {
    const value = this.map.get(key);
    if (value === undefined) return undefined;

    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    }

    this.map.set(key, value);

    if (this.map.size > this.capacity) {
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
  }
}

これは短く、用途によっては十分です。ただし、面接で「なぜ delete して set し直すと順序が変わるのか」「undefined を値として保存したい場合はどうするのか」と聞かれる可能性があります。

データ構造の理解を示したい場面では、HashMap + 双方向リスト版を説明できるようにしておく方が堅いです。

まとめ

LRU Cacheは、単に「キャッシュを作る問題」ではありません。HashMapの検索性能と、双方向リストの順序更新を組み合わせる問題です。

押さえるポイントは次の4つです。

  • Map<K, Node> でキーからノードへ直接到達します。
  • 双方向リストで最近使った順序を管理します。
  • get でも順序を更新します。
  • 容量超過時は tail.prev を削除します。

この形で説明できると、LRU Cacheだけでなく、キャッシュ設計、メモリ管理、バックエンドのホットデータ管理の話にも自然につなげられます。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?