Hash table xử lý collision, load factor, và resizing như thế nào?

Question

Accepted Answer

Hai key khác nhau có thể hash vào **cùng một bucket** — một **collision** (va chạm). Hash table giữ trung bình O(1) bằng cách giải quyết collision và **resizing** (thay đổi kích thước) trước khi bucket trở nên chật chội, được kiểm soát bởi **load factor**.

## Giải quyết collision

```text
Separate chaining (chuỗi tách biệt): mỗi bucket giữ một list
  [3] -> ("cat",9) -> ("rat",2)   # cả hai hash vào 3

Open addressing (định địa chỉ mở): probe (dò) tới slot trống kế tiếp
  hash=3 đã chiếm -> thử 4 -> thử 5 ... (linear probing)
```

## Load factor và resizing

```text
load factor α = số_lượng_entry / số_lượng_bucket
α tăng -> nhiều collision hơn -> tra cứu chậm hơn
Khi α vượt một ngưỡng (ví dụ 0.75):
  -> cấp phát một array lớn hơn (thường gấp 2 lần)
  -> REHASH mọi key hiện có vào các bucket mới
```

```python
# Resize khái niệm
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 vào array mới
```

## Độ phức tạp

| Thao tác | Trung bình | Tệ nhất |
|---|---|---|
| tra cứu / chèn / xóa | O(1) | O(n) |
| một lần resize | — | O(n) |
| chèn (amortized, có resizing) | O(1) | — |

Một lần resize là O(n) nhưng hiếm khi xảy ra, nên nó **amortize về O(1)** mỗi lần chèn.

## Đánh đổi

- **Chaining:** đơn giản, suy giảm nhẹ nhàng, nhưng dùng thêm pointer và có tính cục bộ cache kém.
- **Open addressing:** thân thiện với cache và gọn gàng, nhưng nhạy cảm với load factor cao và cần xóa cẩn thận (tombstone).

## Tại sao điều này quan trọng

Những chi tiết nội bộ này giải thích *tại sao* hash map nhanh ở trung bình nhưng có thể tăng vọt lên O(n) — rất quan trọng cho code nhạy cảm về hiệu năng và phòng thủ trước đầu vào đối nghịch (hash-flooding).

Hiểu load factor cũng giải thích các núm chỉnh bộ nhớ/tốc độ được phơi bày bởi các thư viện thực tế.

Thao tác	Trung bình	Tệ nhất
tra cứu / chèn / xóa	O(1)	O(n)
một lần resize	—	O(n)
chèn (amortized, có resizing)	O(1)	—