結論：ループが必要ないならArrayでなくMapを使え

はじめに：なぜコードが「動く」だけでは不十分なのか

「機能要件は満たしています。テストも通りました」 Web開発の現場では、これで十分かもしれません。しかし、Googleをはじめとするトップティアのテック企業の面接では、これだけでは不合格になります。

彼らが見ているのは 「データが100万件になっても、そのコードは一瞬で動くか？」 というスケーラビリティ（拡張性）です。

今回は、アルゴリズムの基礎である Big O Notation（計算量） と、それを劇的に改善する Hash Map の仕組みについて、TypeScriptを用いて、V8エンジンまで深掘りして解説します。

0. 「Big O (ビッグオー)」とは何か？

「計算量」と聞くと難しく聞こえますが、要するに 「データが増えたとき、処理時間はどれくらい増えるの？」 という成長率を表す物差しです。

Googleのエンジニアは、コードを見た瞬間に頭の中でグラフを描きます。

$O(1)$ (定数時間): データが1個でも1億個でも、時間は変わらない（最高）。
- 例：配列のインデックスアクセス arr[0]
$O(n)$ (線形時間): データが2倍になれば、時間も2倍になる（普通）。
- 例：forループで配列を全部見る。
$O(n^2)$ (二乗時間): データが2倍になると、時間は4倍になる（危険）。
- 例：二重ループ。データが増えると爆発的に遅くなる。

面接では、いかにしてコードを $O(n^2)$ (危険ゾーン) から $O(n)$ や $O(1)$ (安全ゾーン) に落とし込むかが勝負になります。

1. 悪夢の O(n^2)：総当たり戦法

では、LeetCodeの定番問題「Two Sum（合計してターゲット値になるペアを探す）」を例に、悪いパターンを見てみましょう。
最も直感的なアプローチは「二重ループ」です。

// ❌ 推奨されないアプローチ O(n^2) 
function twoSumBruteForce(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]; // やっと見つけた...
      }
    }
  }
  return [];
}

このコードの計算量は $O(n^2)$ です。
データが1,000件なら100万回の計算で済みますが、もしユーザーが100万人いたら？計算回数は1兆回を超えます。サーバーは応答不能になり、あなたはクビになるかもしれません。

CPUに「参加者全員と総当たりで握手させる」ような非効率な作業をさせてはいけません。

2.救世主 O(n) ：Hash Mapによる「空間と時間の等価交換」

ここで登場するのが Hash Map です。「過去に見た数字」をメモリ（Map）に記憶させることで、計算回数を劇的に減らします。

// ✅ 推奨されるアプローチ O(n)
function twoSumHashMap(nums: number[], target: number): number[] {
  // Key: 数字の値, Value: インデックス
  const prevMap = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    const neededNum = target - currentNum;

    // 過去のリストを「一瞬」で確認
    // "!" はTypeScriptのNon-null assertion operator
    if (prevMap.has(neededNum)) {
      return [prevMap.get(neededNum)!, i];
    }

    // 記憶する
    prevMap.set(currentNum, i);
  }

  return [];
}

このアプローチの計算量は $O(n)$ です。
ループは1回だけ。中身の検索（map.has）は $O(1) で完了します。

3.Deep Dive：なぜ Map は O(1) で検索できるのか？

ここからが本題です。
なぜ配列の探索は $O(n)$ かかるのに、Mapはデータ量に関係なく $O(1)$ で検索できるのでしょうか？

それは、「ハッシュ関数」という魔法が、データの 住所（インデックス） を即座に特定しているからです。

内部で起きている3ステップ

map.set("UserA", 100) を実行した時、内部では以下のような処理が行われます。

Hashing: キー（"UserA"）をハッシュ関数に通し、巨大な整数（ハッシュコード）を生成します。
Compression: 現在の配列サイズで割り算（Modulo）し、余りを求めます。
- 例：982734... % 10 = 3
Access: 配列のインデックス 3番にデータを格納します。

探す時も全く同じ計算を行えば、ループで探すことなく、いきなり「3番の部屋」を見に行けるのです。

⚠️ 面接での「落とし穴」：インデックス ≠ メモリアドレス

ここでGoogleの面接官が好む意地悪な質問があります。
「Mapのインデックスは、物理的なメモリアドレスを指しているのか？」

答えは No です。

正解: 内部配列（Bucket）の インデックス（添字） です。
詳細: V8エンジンなどのランタイムが、このインデックスを物理メモリのアドレスに変換してアクセスしています。

TypeScriptのような高級言語では、セキュリティやメモリの動的なリサイズ（可変長対応）のために、生のアドレスは隠蔽されています。ここまで答えられれば、基礎知識は完璧です。

4.Object `{}` vs Map `new Map()`：V8エンジンの最適化

TypeScriptではオブジェクト {} もハッシュマップのように使えますが、アルゴリズムの実装では Map が好まれます。

その理由の一つに「V8エンジンの最適化（Hidden Classes）」があります。

Object {} の場合

V8エンジンは、オブジェクトの形状（プロパティのセット）が変わらない限り、Hidden Class を作成して高速化します。C言語の構造体のようにオフセットでアクセスするため、爆速です。

しかし、プロパティの追加・削除（delete）を頻繁に行うと、この最適化が崩れ、「辞書モード（低速）」に落ちてしまうことがあります。

Map `new Map()` の場合

Mapは最初から「頻繁な追加・削除」を前提に設計されています。どれだけデータを出し入れしてもパフォーマンスが安定しており、常に $O(1)$ に近い速度を維持します。

まとめ

Big O を意識することで、コードの「パフォーマンス」が見えるようになる。
Hash Map は「検索」を $O(n)$ にする最強の武器である。

Googleへの道は、単にコードを書くことではなく、こうした「裏側の仕組み」を理解し、最適なデータ構造を選択する力にかかっています。

Happy Coding! 🚀