Hash table nâng cao: hàm băm và xử lý xung đột

Giới thiệu

Bài này học hàm băm tốt và cách xử lý xung đột. Kiến thức này giúp bảng băm luôn nhanh $O(1)$.

Kiến thức cần nhớ

Hàm băm tốt

• Xác định: cùng đầu vào luôn cho cùng đầu ra.
• Đều: khóa rải khắp các ô, không dồn một chỗ.
• Nhanh: tính trong tích tắc vì gọi rất nhiều lần.
• Ví dụ đời thường: chia đều thư vào các hộc tủ.

Hai họ xử lý xung đột

• Móc nối: mỗi ô giữ danh sách các khóa cùng rơi vào.
• Địa chỉ mở: ô đầy thì dò ô trống lân cận theo quy tắc.
• Móc nối xóa dễ, chịu tải cao; địa chỉ mở gọn cache.
• Ví dụ đời thường: hai xe trùng chỗ, một xếp chồng, một đậu chỗ bên.

Hệ số tải và băm lại

• Hệ số tải = số phần tử chia số ô.
• Tải cao thì xung đột nhiều, mọi thứ chậm dần.
• Vượt ngưỡng 0.75 thì băm lại sang bảng gấp đôi.
• Ví dụ đời thường: tủ đầy thì mua tủ to gấp đôi.

Ví dụ

• Input: chèn 5 khóa vào bảng 8 ô có 1 cặp xung đột -> Output: cặp đó nằm chung xô móc nối.
• Câu này cho thấy xung đột là bình thường và xử lý được.
• Input: chèn vượt ngưỡng 0.75 -> Output: kích hoạt băm lại, mọi khóa vẫn tìm thấy.
• Câu này cho thấy giám sát tải rất quan trọng.

💻 Bài tập

Ngôn ngữ: C++. Không dùng std::unordered_map. Nộp vào day-038/. Khóa std::string, giá trị int.

Bài 1: Hash map móc nối (separate chaining)

Hàm băm: tự cài FNV-1a 64 bit. Số bucket là lũy thừa của 2, chỉ số là hash & (buckets - 1).

put("an",1), put("binh",2), put("an",5) -> size 2, get("an") = 5
erase("binh"); get("binh")              -> nullopt
put 10.000 khóa                         -> loadFactor <= 0.75, mọi khóa get đúng

Bài 2: Địa chỉ mở dò tuyến tính

Viết OpenAddressingMap cùng API. Xóa dùng bia mộ (tombstone). Ngưỡng rehash 0.5, tính cả bia mộ.

put A, B, C cùng rơi vào ô 3 (dùng hàm băm giả để test) -> nằm ở ô 3, 4, 5
erase B; get C                                         -> vẫn tìm thấy (nhờ bia mộ)
put D rơi vào ô 3                                      -> dùng lại ô 4 của B

Bài 3: Đo và tấn công hàm băm (nâng cao)

1. Đo put và get $10^6$ khóa ngẫu nhiên cho 2 cách cài và std::unordered_map. In bảng.
2. Vẽ độ dài chuỗi dài nhất theo hệ số tải 0.25, 0.5, 0.75, 1, 2 cho bản móc nối.
3. Thay hàm băm bằng hàm tệ h(s) = s.size(). Đo lại và giải thích vì sao chậm hẳn. Viết 2 câu về tấn công HashDoS.

✅ Tiêu chí hoàn thành

• Test mẫu pass cho cả 2 cách cài. Có test ngẫu nhiên so với std::map.
• Bia mộ hoạt động: xóa rồi vẫn tìm được khóa phía sau.
• Bảng đo Bài 3 có số thật.
• Giải thích được ưu nhược của móc nối và địa chỉ mở (cache, xóa, tải cao).

❓ Câu hỏi ôn tập

• 3 tính chất của hàm băm tốt là gì?
• Móc nối và địa chỉ mở khác nhau sao?
• Hệ số tải cao gây hại gì?
• Khi nào chọn cây thay vì bảng băm?

🌕 Bạn đã hoàn thành ngày 38. Làm hết bài tập phía trên rồi sang ngày tiếp theo.