Hash table là gì và nó đạt được tra cứu O(1) như thế nào?

Question

Accepted Answer

**Hash table** (hash map) lưu trữ các cặp **key → value** và cung cấp thao tác chèn, tra cứu và xóa **trung bình O(1)**. Nó hoạt động bằng cách đưa mỗi key qua một **hash function** ánh xạ nó tới một index trong array bên dưới (một "bucket").

## Cách hoạt động

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

## Ví dụ

```python
phone = {}
phone['alice'] = 555_1234   # chèn -> hash 'alice' tới một bucket
num = phone['alice']        # tra cứu -> hash lại, nhảy tới bucket
del phone['alice']          # xóa
'bob' in phone              # kiểm tra thành viên -> O(1) trung bình
```

## Độ phức tạp

| Thao tác | Trung bình | Tệ nhất |
|---|---|---|
| chèn | O(1) | O(n) |
| tra cứu | O(1) | O(n) |
| xóa | O(1) | O(n) |

**Trường hợp tệ nhất** O(n) xảy ra khi nhiều key collision vào cùng một bucket.

## Đánh đổi

- **Điểm mạnh:** truy cập theo key cực nhanh; key linh hoạt.
- **Điểm yếu:** không có thứ tự cho key; tốn thêm bộ nhớ; trường hợp tệ nhất O(n); cần một hash function tốt.

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

Hash table được cho là cấu trúc được dùng nhiều nhất trong thực tế — đứng sau dictionary, set, cache, database index, và khử trùng lặp.

Thay thế quét tuyến tính bằng tra cứu hash là một trong những cách phổ biến nhất để biến một thuật toán O(n²) thành O(n).