配列検索の二重ループを解消！MapとBig-Oで大量データ処理を高速化する

データが100件のときは一瞬で終わっていた処理が、1万件になった途端に数秒かかる。開発環境では軽快に動いていたのに、本番データを入れたら画面が固まる。そんな経験はありませんか。原因の多くは、配列の中でさらに配列を探す「ループの中にループ」にあります。この記事では、計算量（Big-O記法）の読み方を最小限の知識で押さえ、ハッシュマップ（JavaScriptの Map やオブジェクト）で検索を一気に軽くする方法を、手元ですぐ試せるコード付きで解説します。

なぜデータが増えると遅くなるのか？計算量（Big-O）の超基本

計算量とは、データ量 N が増えたときに、処理の手数がどう増えるかを表す指標です。それを大づかみに書く方法が Big-O記法 です。「秒数」ではなく「手数の増え方」に注目するため、PCの性能が違っても比較できます。アルゴリズム入門で最初に覚えたい考え方です。

よく見る3つだけ押さえれば十分です。

• O(1)：データ量に関係なく手数が一定（例：配列の添字アクセス）
• O(N)：データ量に比例して手数が増える（例：配列を1回ループする）
• O(N^2)：データ量の2乗で手数が増える（例：ループの中でループする）

N が増えたときの差を表にします。

N（件数）	O(N)	O(N^2)
100	100	10,000
1,000	1,000	1,000,000
10,000	10,000	100,000,000

データが100倍になると、O(N) の手数は100倍ですが、O(N^2) は1万倍になります。開発中の少量データでは気づかず、本番の大量データで突然重くなるのは、この増え方の差が原因です。なお、Big-O は「増え方」の目安であり、実際の秒数は環境や実装で変わります。

やってしまいがちなNGパターン：配列の二重ループとfind/includesの罠

典型例は「注文データに、ユーザー名を紐づける」処理です。次のコードは読みやすく、動作も正しいため、つい書いてしまいます。

function attachUsers(orders, users) {
  return orders.map(order => {
    const user = users.find(u => u.id === order.userId);
    return { ...order, userName: user?.name ?? "不明" };
  });
}

ループが1つに見えても油断できません。Array.prototype.find は、条件に合う要素が見つかるまで先頭から順に調べる関数です。つまり内部でもループが動いており、orders が N 件、users が M 件なら、最悪で N × M 回の比較が発生します。両方1万件なら最大1億回です。

同じ罠は includes、indexOf、filter、some にもあります。これらは配列を端から調べるため、1回あたり O(N) です。それをループ内で呼べば、見た目は1行でも O(N^2) になります。

// 重複を除く処理の例（これも O(N^2)）
const unique = items.filter((item, i) => items.indexOf(item) === i);

少量データでは問題が表に出ません。だからこそ、レビューで「ループの中で配列メソッドを呼んでいないか」を意識して見ることが、チーム開発では効果的です。

ハッシュマップ（オブジェクト/Map）で検索をO(1)に落とす実践テクニック

解決策は、検索される側の配列を ハッシュマップ に変換しておくことです。ハッシュマップは、キーから保存場所を直接計算して、値を取り出すデータ構造です。端から探す必要がないため、検索が平均で O(1) になります。JavaScript では Map か通常のオブジェクトが使えます。

ECMAScript の仕様でも、Map は要素数に対して平均でサブリニア（要素数に比例するより速い）なアクセス時間を提供するよう実装することが求められています。実際の主要なJavaScriptエンジンでは、ハッシュテーブルが使われているのが一般的です。ただし、キーが極端に偏った場合などの最悪ケースは遅くなり得ます。「常に必ず O(1)」ではなく「平均的に O(1)」と理解してください。

使い方は3ステップです。

1. 検索される側の配列から、1回のループで Map を作る（O(M)）
2. 検索する側のループで、map.get(key) を呼ぶ（1回あたり O(1)）
3. 全体の手数が N + M 程度に収まる（O(N + M)）

const userMap = new Map(users.map(u => [u.id, u]));
const user = userMap.get(order.userId);

存在チェックだけなら Set が便利です。includes の代わりに set.has(value) を使います。

const allowedIds = new Set(allowedList);
const result = items.filter(item => allowedIds.has(item.id));

注意点もあります。Map を作る分のメモリと、構築の時間がかかります。検索が1〜2回しかなく、データも数十件なら、配列の find のほうが単純で十分です。「何回検索するか」で判断してください。

実例コードで比較！1万件の突合処理が数秒から数ミリ秒へ縮む劇的ビフォーアフター

実際に計測してみましょう。ユーザー1万件と注文1万件を用意し、2通りの実装を比べます。Node.js で動かせます。

const N = 10000;
const users = Array.from({ length: N }, (_, i) => ({ id: i, name: `user${i}` }));
const orders = Array.from({ length: N }, (_, i) => ({
  orderId: i,
  userId: N - 1 - i, // 配列の後ろ側から探させる
}));

// Before: 配列の find（O(N × M)）
function attachUsersSlow(orders, users) {
  return orders.map(order => {
    const user = users.find(u => u.id === order.userId);
    return { ...order, userName: user?.name ?? "不明" };
  });
}

// After: Map を使う（O(N + M)）
function attachUsersFast(orders, users) {
  const userMap = new Map(users.map(u => [u.id, u]));
  return orders.map(order => {
    const user = userMap.get(order.userId);
    return { ...order, userName: user?.name ?? "不明" };
  });
}

console.time("slow");
attachUsersSlow(orders, users);
console.timeEnd("slow");

console.time("fast");
attachUsersFast(orders, users);
console.timeEnd("fast");

筆者が想定する結果の傾向は、slow が数十ミリ秒〜数百ミリ秒以上、fast が数ミリ秒〜十数ミリ秒です。環境次第で数字は大きく変わり、find はエンジンの最適化で意外と速く動くこともあります。ただし、N を10万件に増やしたときの差は決定的です。N が10倍になると slow の手数は約100倍に膨らみ、秒単位の待ち時間になります。一方 fast は約10倍の増加で収まります。

大切なのは、絶対的な秒数よりも 件数を増やしたときの伸び方 を見ることです。N を 1,000、10,000、100,000 と変えて計測すると、O(N^2) の曲線が立ち上がる様子を体感できます。自分の環境で必ず試してみてください。

実務のデータベース連携でも同じ考え方が通用します。注文ごとにユーザーを1件ずつ検索するクエリを発行するより、必要なIDをまとめて取得し、メモリ上で Map に引き当てるほうが、往復回数を減らせるケースが多いです。

日常の開発で「遅いコード」を作らないための設計チェックリスト

最後に、コードを書くとき・レビューするときの確認項目をまとめます。全部を毎回やる必要はなく、データが増えそうな箇所だけで十分です。

1. ループの中で find、includes、indexOf、filter を呼んでいないか
2. 「紐づけ」「突合」「重複チェック」の処理で、検索される側を Map や Set にしているか
3. Map を作る処理が、ループの外にあるか（ループ内で毎回作ると意味がなくなります）
4. 想定するデータ量は何件か。今は100件でも、半年後に10万件にならないか
5. 検索回数が少なく、データも小さいなら、あえて単純な配列のままにしていないか
6. 改善前後を console.time などで計測し、推測ではなく数値で確認したか

3番目は見落としやすいポイントです。users.find(...) を new Map(...) に置き換えても、Map の生成が毎回のループ内にあると、結局 O(N^2) のままです。

もう1つ大事なのは、計測してから最適化する ことです。読みやすさを犠牲にしてまで全部を Map にする必要はありません。チーム開発では、「ここは件数が増えるので Map にしています」とコメントを1行残すと、保守する人に意図が伝わります。ボトルネックを見つけ、効果の大きい箇所だけを直す。その習慣が、パフォーマンス改善を再現性のある技術に変えてくれます。