Bagaimana hash table mengendalikan collision, load factor, dan resizing?

Question

Accepted Answer

Dua kunci yang berbeza boleh di-hash ke **bucket yang sama** — suatu **collision**. Hash table kekal O(1) secara purata dengan menyelesaikan collision dan **mengubah saiz (resize)** sebelum bucket menjadi sesak, dikawal oleh **load factor**.

## Penyelesaian collision

```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)
```

## Load factor dan resizing

```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
```

## Kerumitan

| Operasi | Purata | Terburuk |
|---|---|---|
| lookup / insert / delete | O(1) | O(n) |
| resize tunggal | — | O(n) |
| insert (ter-amortize, dengan resizing) | O(1) | — |

Suatu resize ialah O(n) tetapi jarang berlaku, jadi ia **ter-amortize kepada O(1)** setiap insert.

## Pertimbangan timbal balik

- **Chaining:** ringkas, merosot secara anggun, tetapi menggunakan penunjuk tambahan dan mempunyai lokaliti cache yang lemah.
- **Open addressing:** mesra cache dan padat, tetapi sensitif terhadap load factor yang tinggi dan memerlukan pemadaman yang teliti (tombstone).

## Mengapa ia penting

Dalaman ini menerangkan *mengapa* hash map pantas secara purata namun boleh melonjak kepada O(n) — penting untuk kod yang sensitif prestasi dan pertahanan input bermusuhan (hash-flooding).

Memahami load factor juga menerangkan tombol penalaan memori/kelajuan yang didedahkan oleh pustaka sebenar.

Operasi	Purata	Terburuk
lookup / insert / delete	O(1)	O(n)
resize tunggal	—	O(n)
insert (ter-amortize, dengan resizing)	O(1)	—