【ハッシュテーブル】

これまで配列を使ってきましたが、配列は探すのが遅いです。この弱点を解決する道具が、ハッシュテーブルです。この講座で一番の山場です。

配列の弱点

会員リストから「佐藤さんの年齢」を調べたいとします。配列だと以下の通り。

const users = [
  { name: "田中", age: 28 },
  { name: "鈴木", age: 17 },
  { name: "佐藤", age: 35 },
];
const sato = users.find((u) => u.name === "佐藤");

findは先頭から順に確認します。3人なら一瞬ですが、100万人なら最悪100万回、つまりO(n)です。1回ならまだしも、「1000人分の名前について順に調べる」となると、100万×1000回の確認になり、現実的な時間で終わりません。

これは、探すたびに全員を見るのが問題なのです。欲しいのは、名前を言えば一発でデータが出てくる仕組み、つまり辞書です。

キーで引く、オブジェクトは辞書である

実は、その道具はすでに手元にあります。オブジェクトです。

ages["佐藤"] は、全員を順に確認しません。キー(名前)から保存場所を直接割り出して、そこを読むだけ。データが100万人分あってもO(1)です。なぜそんなことが可能なのか、その内部の仕組み(ハッシュ関数)はこの教材の後半「作る編」で種明かしします。

この「キー→値を1回で引ける構造」の一般名がハッシュテーブルです。言語によって連想配列、辞書、マップとも呼ばれます。JavaScriptではオブジェクトがその役割を果たし、型は Record<キーの型, 値の型> と書きます(スタック演習の括弧の対応表 Record<string, string> が、実はハッシュテーブルの初登場でした)。

定番パターン① 数える(頻度カウント)

ハッシュテーブルの一番使われるのは「数える」仕事です。文章に各単語が何回出てくるか、数えてみます。

核心は (counts[word] ?? 0) + 1 の1行です。?? は「左がundefinedなら、右を使う」という演算子(Null合体演算子)です。初めて見る単語なら「0回」から数え始め、既にあればその値に1を足す。この頻度カウントの型は、コーディングテストで最頻出のパターンです。「一番多く登場する文字は?」「重複はあるか?」「アナグラムか?」という数え上げ系の問題は、ほぼすべてこの3行から始まります。

定番パターン② 「あるかどうか」だけならSet

値は要らず、「存在するかどうか」だけ知りたい場面には、専用の道具があります。Set(セット)です。重複なしの値の集まりです。