ハッシュテーブル

ハッシュテーブルとは

ハッシュテーブルは、キーをハッシュ関数で配列のインデックスに変換し、平均 O(1) でデータを検索・挿入・削除するデータ構造である。JavaScript の Map/Object、Python の dict が内部でハッシュテーブルを使用する。

仕組み

ハッシュ関数でキーを配列のインデックスに変換し、そのインデックスに値を格納する。検索時も同じハッシュ関数でインデックスを計算するだけなので、平均 O(1) でアクセスできる。異なるキーが同じインデックスに衝突した場合は、チェイン法 (連結リスト) やオープンアドレス法で解決する。

この平均 O(1) は無条件ではない。ハッシュ値がスロット全体に散らばること、そして格納数 ÷ スロット数 (負荷率) が一定以下に保たれていることが前提になる。負荷率が上限を超えると実装は配列を拡張して全要素を入れ直す (リハッシュ)。そのため個々の挿入は最悪 O(n) を踏み、多数の挿入でならして平均すると O(1) に収まる (償却計算量)。要素数の見込みが立つなら、生成時に容量を指定してリハッシュの回数を減らすのが定石だ。

キー "alice" → hash("alice") = 3 → 配列[3] に値を格納
キー "bob"   → hash("bob")   = 7 → 配列[7] に値を格納

検索: hash("alice") = 3 → 配列[3] → O(1)

計算量

計算量を以下にまとめる。

操作	平均	最悪
検索	O(1)	O(n)
挿入	O(1)	O(n)
削除	O(1)	O(n)

最悪ケースは、キーが同じスロットに集中して、そのスロットの連結リストを線形に走査するのと変わらなくなる場合である。Java の HashMap の仕様書きが「ハッシュ関数がバケット間に要素を適切に分散させることを前提として」定数時間と断っているように、平均 O(1) はハッシュ関数の質に依存する条件付きの性質だ。

偏りは偶然だけで起きるものではない。外部から受け取った値をそのままキーにする経路では、同じスロットに落ちるキーを大量に送り込んで処理を重くする攻撃 (ハッシュ衝突 DoS) が成立し得る。Python が文字列・バイト列のハッシュ乱択化を既定で有効にしているのはこの対策で、副作用として同じ文字列でもプロセスごとにハッシュ値が変わる。hash() の戻り値を実行をまたいで保存したり、そのままシャーディングのキーに使ったりしてはいけない。

TypeScript での使用

TypeScript での使用のコード例を示す。

// Map (ハッシュテーブル)
const users = new Map<string, User>();
users.set('alice', { name: 'Alice', age: 30 });
users.get('alice'); // O(1)
users.has('alice'); // O(1)
users.delete('alice'); // O(1)

// Set (キーのみのハッシュテーブル)
const seen = new Set<string>();
seen.add('item-1');
seen.has('item-1'); // O(1)

衝突の解決

衝突の解決を以下にまとめる。

方式	説明
チェイニング	同じインデックスにリンクリストで格納
オープンアドレス	次の空きスロットを探す

配列 vs ハッシュテーブル

配列と ハッシュテーブル のコード例を比較する。

// ❌ 配列で検索: O(n)
const users = [{ id: '1', name: 'Alice' }, { id: '2', name: 'Bob' }];
users.find(u => u.id === '1'); // 全要素を走査

// ✅ ハッシュテーブルで検索: O(1)
const userMap = new Map([['1', { name: 'Alice' }], ['2', { name: 'Bob' }]]);
userMap.get('1'); // 即座に取得

実用例: 重複チェック

重複チェックの実用的なコード例を示す。

// O(n) で重複を検出 (ハッシュテーブルを使用)
function hasDuplicate(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const n of arr) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}
// 配列のネストループ O(n²) より高速

基礎から学ぶなら関連書籍が手がかりになる。