ハッシュテーブル

ハッシュテーブルとは

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

仕組み

ハッシュ関数でキーを配列のインデックスに変換し、そのインデックスに値を格納する。検索時も同じハッシュ関数でインデックスを計算するだけなので、平均 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)

最悪ケースは全キーが同じハッシュ値になる場合 (衝突)。

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²) より高速

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