ハッシュマップはアルゴリズムをどのように最適化しますか？

Question

Accepted Answer

**ハッシュマップ**（辞書）は平均で**O(1)**の検索、挿入、削除を実現します。O(n)のメモリを速度と引き換えにすることで、反復的なスキャンを即座なルックアップに置き換え、多くのO(n²)アルゴリズムをO(n)に変換します。

## 基本的な考え方

リストを毎回検索する代わりに、見つけた値をハッシュマップに保存し、定数時間でメンバーシップを確認します。

## 例：O(n)での2つの数の合計

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

マップなしではこれはO(n²)ですが、マップを使用すると1回のパスで済みます。

## 一般的な用途

- **重複排除/メンバーシップ**（setを使用）。
- **頻度のカウント**（`Counter`）。
- **キーによるグループ化/インデックス作成**。
- **結果のキャッシング/メモ化**。

## 計算量

- **平均：** 操作あたりO(1)。**最悪：** 衝突が多い場合はO(n)。**空間：** O(n)。

## 落とし穴

キーは**ハッシュ可能**で不変である必要があります。最悪の衝突でパフォーマンスが低下します。ハッシュマップは順序付けされていません（順序が重要な場合は順序付けされたバリアントを使用します）。

## なぜ重要なのか

ハッシングはコーディングインタビューと実際のシステムで最も一般的な最適化です — 「何度も検索する」を「一度検索する」に変換します。

空間と時間のトレードオフは繰り返し現れるエンジニアリングのテコです。

頻度のカウント、キャッシング、インデックス作成はすべてこの1つの概念に依存しています。