Chuyển tới nội dung chính

Xử lý đụng độ (collision)

Bạn sẽ học được gì

Hàm băm có thể đưa hai khóa khác nhau vào cùng một ô — gọi là đụng độ (collision). Điều này không tránh được hoàn toàn. Bạn sẽ học hai cách xử lý kinh điển: nối chuỗi và dò địa chỉ mở.

1. Vì sao đụng độ là không tránh khỏi?​

Có vô số khóa có thể (mọi chuỗi), nhưng bảng chỉ có hữu hạn ô. Theo nguyên lý chuồng bồ câu, kiểu gì cũng có hai khóa băm ra cùng chỉ số. Ví dụ với hàm băm cộng mã ký tự, "an" và "na" cho cùng tổng → cùng ô!

"an" ──▶ ô 2
"na" ──▶ ô 2   ← ĐỤNG ĐỘ!

Bảng băm tốt không loại bỏ đụng độ — nó xử lý đụng độ cho gọn.

2. Cách 1: Nối chuỗi (chaining)​

Mỗi ô không giữ một mục, mà giữ một danh sách các mục cùng băm vào đó. Đụng độ → cứ thêm vào danh sách của ô đó.

ô 0: → None
ô 1: → None
ô 2: → [("an", 90)] → [("na", 70)]      ← hai mục cùng ô, nối thành chuỗi
ô 3: → None
ô 4: → [("ba", 80)]

Tìm khóa: băm ra ô, rồi duyệt danh sách nhỏ trong ô đó để khớp đúng khóa.

🐞 Nối chuỗi: thêm "an" rồi "na" (cùng ô 2)Bước 1/5
1bang = [[] for _ in range(5)]   # moi o la mot list
2def them(key, val):
3  o = bam(key)                # gia su "an" va "na" deu -> o 2
4  bang[o].append((key, val))
Biến tại bước này
bang[[],[],[],[],[]]
👉 Bảng 5 ô, mỗi ô một list rỗng.

3. Cách 2: Dò địa chỉ mở (open addressing)​

Mỗi ô chỉ giữ một mục. Đụng độ → dò sang ô kế tiếp (vd ô+1, ô+2...) cho tới khi gặp ô trống.

Thêm "an" -> ô 2 (trong) -> dat o o 2
Thêm "na" -> ô 2 (ban!) -> thu o 3 (trong) -> dat o o 3

Tìm khóa: băm ra ô, nếu không khớp thì dò tiếp cùng quy luật cho tới khi gặp khóa hoặc ô trống.

4. So sánh hai cách​

Nối chuỗi (chaining)Dò địa chỉ mở (open addressing)
Mỗi ô giữmột danh sáchmột mục
Khi đụng độthêm vào list của ôdò sang ô khác
Ưuđơn giản, chịu tải cao tốttiết kiệm bộ nhớ, cache tốt
Nhượctốn con trỏ/list phụxuống cấp nhanh khi bảng gần đầy

Python dict/set dùng open addressing (biến thể tinh vi). Nhiều ngôn ngữ khác dùng chaining. Cả hai đều cho O(1) trung bình nếu bảng không quá đầy (bài tiếp theo).

5. Code minh họa: bảng băm nối chuỗi tự xây​

Đang tải trình chạy code…

6. Mẫu nhận diện​

  • Đụng độ là bình thường — bảng băm sinh ra để xử lý nó, không phải tránh.
  • Nhiều đụng độ vào một ô → ô đó tra cứu chậm dần (duyệt list dài / dò xa). Cần hàm băm rải đều + giữ bảng không quá đầy.

7. 🎮 Trò chơi: Hiểu đụng độ​

🎮 Hiểu đụng độCâu 1/4· Điểm 0· 🔥 0

Đụng độ = hai khóa cùng ô. Chaining: list mỗi ô. Open addressing: dò sang ô khác.

Đụng độ có tránh được hoàn toàn không?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Vì sao đụng độ không tránh khỏi?
2. Trong nối chuỗi, mỗi ô của bảng chứa?
3. Python dict/set dùng cách xử lý đụng độ nào?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.4.3 — Hệ số tải, rehash & độ phức tạp.