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

Bảng băm (Hash table): ý tưởng & hàm băm

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

Bảng băm (hash table) là cấu trúc thần kỳ cho phép tra cứu, thêm, xóa O(1) trung bình — gần như tức thì. Nó là nền của dict và set trong Python. Bạn sẽ hiểu hàm băm biến khóa thành chỉ số ra sao.

1. Trực quan: tủ gửi đồ có công thức​

Mảng tra theo chỉ số số nguyên (O(1)). Nhưng đời thực ta hay tra theo khóa bất kỳ: tên, email, từ. Bảng băm giải bài này bằng một mẹo: biến khóa thành chỉ số qua một hàm băm (hash function).

khóa "an"  ──[ hàm băm ]──▶  số 2   ──▶  bang[2]
khóa "ba"  ──[ hàm băm ]──▶  số 4   ──▶  bang[4]

Giống tủ gửi đồ mà từ tên bạn tính ra luôn số tủ — không phải dò từng tủ. Biết khóa → tính được chỉ số → nhảy thẳng tới ô. Đó là gốc rễ của O(1).

2. Hàm băm là gì?​

Hàm băm nhận một khóa và trả về một số nguyên trong khoảng [0, N) (N = số ô của bảng). Một hàm băm đơn giản (cho mục đích học): cộng mã các ký tự rồi chia lấy dư.

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

Một hàm băm tốt cần: xác định (cùng khóa luôn ra cùng số), nhanh, và rải đều (ít khóa trùng ô — sẽ bàn ở bài đụng độ).

3. Chạy debug: băm khóa "an" thành chỉ số​

Bước qua cách tính chỉ số cho khóa "an" với bảng 5 ô:

🐞 Băm "an" với N = 5Bước 1/4
1tong = 0
2for c in "an":
3  tong += ord(c)
4o = tong % 5
Biến tại bước này
tong0
👉 Bắt đầu tổng = 0.

4. Tra cứu vì sao O(1)?​

Cả khi thêm và khi tìm, ta đều băm khóa ra cùng chỉ số → nhảy thẳng tới đúng ô. Không duyệt, không dò. Đó là vì sao dict["key"] hay "x" in set gần như tức thì, bất kể bảng to cỡ nào.

Thêm:  bang[ bam(key) ] = value
Tìm:   value = bang[ bam(key) ]      ← cùng chỉ số → O(1)

5. dict & set của Python là bảng băm​

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

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

  • Cần tra cứu theo khóa bất kỳ (không phải chỉ số) nhanh → bảng băm (dict).
  • Cần kiểm tra "đã thấy chưa / có tồn tại không" nhanh → set.
  • Thấy mình duyệt đi duyệt lại để tìm → thường thay được bằng dict/set để xuống O(1).

7. 🎮 Trò chơi: Hiểu hash table​

🎮 Hiểu hash tableCâu 1/4· Điểm 0· 🔥 0

Hàm băm biến khóa → chỉ số → nhảy thẳng tới ô → O(1) trung bình.

Tính chất BẮT BUỘC của hàm băm là?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Vì sao bảng băm tra cứu O(1)?
2. dict trong Python là?
3. Hàm băm trả về giá trị trong khoảng nào?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.4.2 — Xử lý đụng độ (khi hai khóa rơi vào cùng một ô).