エピローグ ── データ構造の選択は設計判断である
シリーズの全体像
問題の性質 → 最適なデータ構造 → 実際のシステム
「キーで O(1) 検索」 → Hash Table → Redis, Python dict
「順序付き検索」 → BST / AVL / RB-Tree → TreeMap, std::map
「最大/最小の取り出し」 → Heap → 優先度付きキュー, Dijkstra
「先入先出」 → Queue (deque) → BFS, タスクキュー, Kafka Consumer
「経路・関係の探索」 → Graph + BFS/DFS → SNS, 路線検索
「部分問題の再利用」 → DP テーブル → 最適化問題全般
「ディスク I/O 最適化」 → B-Tree / B+ Tree → PostgreSQL, MySQL
「書き込み最適化」 → LSM-Tree → Cassandra, RocksDB
「近似判定で十分」 → Bloom Filter / HLL → Chrome, Redis PFCOUNTデータ構造選択のチートシート
| やりたいこと | 第一候補 | 計算量 | 代替候補 |
|---|---|---|---|
| キーで値を引く | Hash Table | O(1) avg | BST O(log n) ※順序が必要なら |
| 最小/最大を取り出す | Heap | O(log n) push/pop | ソート済み配列 ※静的データなら |
| 範囲検索 | B+ Tree / BST | O(log n + k) | ソート済み配列 + 二分探索 |
| 存在チェック（大量） | Bloom Filter | O(k) | HashSet ※メモリが許すなら |
| ユニーク数の推定 | HyperLogLog | O(1) add | HashSet → count |
| 頻度の推定 | Count-Min Sketch | O(d) | HashMap ※正確さが必要なら |
| ソート済みデータの検索 | 二分探索 | O(log n) | Hash ※順序不要なら |
| 依存関係の解決 | トポロジカルソート | O(V+E) | — |
| 連結判定 | Union-Find | O(α(n)) ≈ O(1) | BFS/DFS |
| 最短経路（重みなし） | BFS | O(V+E) | — |
| 最短経路（重みあり） | Dijkstra + Heap | O((V+E) log V) | Bellman-Ford ※負の辺 |
面接で問われるのは「なぜその選択か」
面接官は「HashMap を使いました」という回答ではなく、「検索が O(1) 必要で順序は不要、メモリは許容範囲なので HashMap を選びました」という判断のプロセスを聞いている。
判断の軸：
1. 操作の頻度（読み多い？書き多い？）
2. 必要な計算量（O(1) が必須？O(log n) で十分？）
3. 順序の要否（ソート済みで返す必要がある？）
4. メモリの制約（データが全てメモリに載る？）
5. 近似の許容度（100% 正確でなくていい？）次のステップ
このシリーズと「システム設計 CS」シリーズの接続
本シリーズで学んだデータ構造とアルゴリズムが、実際のシステム設計でどう使われているかを「システム設計 CS」シリーズで体感できる。
本シリーズ → システム設計 CS
Ch.2 Hash Table → Ch.2 短縮URL（Base62 + KV ストア）
Ch.4 BST / 平衡木 → Ch.10 B-Tree（DB インデックス）
Ch.5 Heap → Ch.16 Dijkstra（経路探索）
Ch.6 Graph + BFS → Ch.15 ソーシャルグラフ
Ch.8 Binary Search → Ch.14 オートコンプリート（Trie + 二分探索）
Ch.10 B-Tree / LSM-Tree → Ch.4 AlloyDB / Spanner
Ch.11 Bloom Filter → Ch.3 S3（存在チェック）
Ch.11 HyperLogLog → Ch.14 ユニーク検索語の推定推薦書籍
- Introduction to Algorithms (CLRS) — アルゴリズムの教科書の決定版
- Algorithm Design Manual (Skiena) — 実践的な問題解決に寄せた教科書
- Designing Data-Intensive Applications (Kleppmann) — B-Tree / LSM-Tree / レプリケーションの実務的解説
最後に
データ構造とアルゴリズムは「覚えるもの」ではなく「理解するもの」だ。
「ハッシュテーブルは O(1) です」と暗記するのではなく、「なぜ O(1) なのか → ハッシュ関数でインデックスを直接計算するから → ではなぜ最悪 O(n) になるか → 衝突が連鎖するから → ではどう防ぐか → 負荷率を管理してリハッシュするから」と、理由の連鎖を追えることが真の理解だ。
この理由の連鎖を持っていれば、初見の問題に対しても「この性質が使えるのでは」と気づける。それが設計力の本質だ。