ハッシュテーブルはどのようにコリジョン、ロードファクタ、およびリサイジングを処理しますか？

Question

Accepted Answer

異なる2つのキーが**同じバケット**にハッシュされる可能性があります。これを**コリジョン**と呼びます。ハッシュテーブルは、コリジョンを解決し、バケットが満杯になる前に**リサイジング**することで、**ロードファクタ**によって制御されながら、平均的にO(1)を保ちます。

## コリジョン解決

```text
Separate chaining: each bucket holds a list
  [3] -> ("cat",9) -> ("rat",2)   # both hashed to 3

Open addressing: probe to the next free slot
  hash=3 taken -> try 4 -> try 5 ... (linear probing)
```

## ロードファクタとリサイジング

```text
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
  -> allocate a bigger array (usually 2x)
  -> REHASH every existing key into new buckets
```

```python
# Conceptual resize
def _resize(self):
    old = self.buckets
    self.buckets = [None] * (len(old) * 2)
    for entry in all_entries(old):
        self._insert(entry.key, entry.value)   # rehash into new array
```

## 計算量

| 操作 | 平均 | 最悪 |
|---|---|---|
| lookup / insert / delete | O(1) | O(n) |
| 単一リサイズ | — | O(n) |
| insert (償却、リサイジング付き) | O(1) | — |

リサイズはO(n)ですが、めったに発生しないため、1回の挿入あたり**償却してO(1)**になります。

## トレードオフ

- **チェーニング：**シンプルで段階的に性能が低下しますが、余分なポインタを使用し、キャッシュの局所性が悪いです。
- **オープンアドレッシング：**キャッシュフレンドリーでコンパクトですが、高いロードファクタに敏感で、削除時に注意が必要です（トゥームストーン）。

## なぜ重要なのか

これらの内部動作により、ハッシュマップが平均的に高速である一方で、O(n)にスパイクする可能性がある理由が説明されます。これは、パフォーマンスに敏感なコードと敵対的入力（ハッシュフラッディング）防御にとって重要です。

ロードファクタを理解することで、実際のライブラリが公開しているメモリ/速度のチューニングノブについても説明がつきます。

操作	平均	最悪
lookup / insert / delete	O(1)	O(n)
単一リサイズ	—	O(n)
insert (償却、リサイジング付き)	O(1)	—