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

Hệ số tải, rehash & độ phức tạp

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

Vì sao bảng băm là O(1) trung bình nhưng O(n) xấu nhất, hệ số tải quyết định tốc độ ra sao, và rehash (mở rộng bảng) giữ cho nó luôn nhanh — liên hệ với amortized đã học.

1. Hệ số tải (load factor)​

Hệ số tải = số mục đã lưu / số ô của bảng.

load factor = (số mục) / (số ô)

10 mục trong bảng 20 ô → load = 0.5  (thoáng, nhanh)
18 mục trong bảng 20 ô → load = 0.9  (chật, nhiều đụng độ, chậm dần)

Bảng càng đầy (load cao) → càng nhiều đụng độ → tra cứu càng chậm (list dài / dò xa). Nếu để mặc kệ, bảng đầy dần sẽ tụt về O(n).

2. Rehash: mở rộng để giữ tốc độ​

Khi load vượt ngưỡng (thường ~0.7), bảng tự rehash:

  1. Tạo bảng mới lớn hơn (thường gấp đôi số ô).
  2. Băm lại mọi mục vào bảng mới (vì N đổi → chỉ số đổi).
  3. Thay bảng cũ bằng bảng mới.

Rehash tốn O(n) cho lần đó, nhưng vì nhân đôi nên xảy ra ngày càng thưa → amortized O(1) mỗi lần thêm (chính xác mô hình bài 1.2.6 amortized — mảng động cũng vậy).

3. Nhìn tận mắt: load factor và rehash​

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

Để ý: mỗi khi load sắp vượt 0.7, số ô nhân đôi → load tụt xuống → bảng luôn "thoáng" → tra cứu luôn nhanh. Đó là cơ chế giữ O(1) trung bình.

4. Vì sao trung bình O(1) nhưng xấu nhất O(n)?​

Trường hợpKhi nàoĐộ phức tạp
Trung bìnhhàm băm rải đều, load thấpO(1)
Xấu nhấtmọi khóa đụng độ vào một ôO(n)

Xấu nhất xảy ra khi hàm băm dở (tất cả khóa cùng ô) → bảng băm thoái hóa thành một danh sách → tra cứu O(n). Thực tế hiếm gặp với hàm băm tốt, nên ta nói bảng băm "O(1)" — nhưng nhớ rằng đó là trung bình, không phải đảm bảo tuyệt đối.

So với cây cân bằng

Bảng băm: O(1) trung bình nhưng O(n) xấu nhất, và không giữ thứ tự. Cây tìm kiếm cân bằng (học ở Chương 2.5): O(log n) đảm bảo và giữ thứ tự. Chọn theo nhu cầu: cần nhanh nhất + không cần thứ tự → hash; cần đảm bảo + thứ tự → cây.

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

  • Bảng băm chậm bất thường → kiểm tra load factor (quá đầy?) và hàm băm (rải đều?).
  • Cần độ phức tạp đảm bảo (không chỉ trung bình) hoặc cần thứ tự → cân nhắc cây thay hash.
  • Thêm nhiều vào dict/set → có những lần chậm (rehash) nhưng trung bình vẫn O(1).

6. 🎮 Trò chơi: Tải & rehash​

🎮 Tải & rehashCâu 1/4· Điểm 0· 🔥 0

Load factor = mục/ô. Quá cao → rehash (nhân đôi ô). Trung bình O(1), xấu nhất O(n).

Độ phức tạp XẤU NHẤT của tra cứu trong bảng băm?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Hệ số tải (load factor) là?
2. Bảng băm có độ phức tạp trung bình và xấu nhất là?
3. Ưu thế của cây cân bằng so với bảng băm?

8. Hoàn thành​

…

☑️ Tiếp theo: 2.4.4 — Set & Map: ứng dụng giải bài.