ハッシュテーブルとは何か、またどのようにして O(1) ルックアップを実現しているか?

Question

Accepted Answer

**ハッシュテーブル**(ハッシュマップ)は **key → value** ペアを格納し、平均的に **O(1)** の insert、lookup、delete を提供します。各キーを**ハッシュ関数**に通して、基礎となる配列("bucket" と呼ばれる)のインデックスにマップすることで機能します。

## 動作原理

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## 例

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## 時間計算量

| 操作 | 平均 | 最悪 |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**最悪ケース** O(n) は、多くのキーが同じ bucket に衝突する場合に発生します。

## トレードオフ

- **長所:** キー ベースのアクセスが極めて高速; 柔軟なキー。
- **短所:** キーの順序付けがない; 追加メモリ; 最悪ケース O(n); 良好なハッシュ関数が必要。

## なぜ重要なのか

ハッシュテーブルは実際に最もよく使用されるデータ構造です — 辞書、セット、キャッシュ、データベースインデックス、重複排除の背後にあります。

線形スキャンをハッシュルックアップで置き換えることは、O(n²) アルゴリズムを O(n) に変える最も一般的な方法の 1 つです。