Dictionary, set và ý tưởng băm
Ôn lại trước khi học
Giới thiệu
Bài này học từ điển khóa-giá trị và tập hợp. Bạn hiểu hàm băm giúp tra cứu rất nhanh.
Kiến thức cần nhớ
Dictionary — cặp khóa giá trị
- Mỗi mục gồm khóa và giá trị.
- Khóa duy nhất, ghi đè thì thay giá trị.
- Khóa phải ổn định, không đổi giữa chừng.
- Ví dụ đời thường: từ điển tiếng Việt tra nghĩa.
- Tra cứu trung bình .
Set — tập không trùng
- Set chỉ giữ khóa, không giữ giá trị.
- Mọi phần tử đều duy nhất.
- Có phép hợp, giao, hiệu.
- Ví dụ đời thường: danh sách email không trùng.
- Cần ánh xạ thì dùng dict, chỉ cần tồn tại thì dùng set.
Hàm băm và khi nào dùng gì
- Hàm băm biến khóa thành chỉ số ô nhớ.
- Nhờ đó nhảy thẳng tới ô, khỏi quét.
- Hai khóa khác nhau có thể chung ô, gọi là xung đột.
- Ví dụ đời thường: tủ đồ có số ngăn tính từ tên.
| Nhu cầu | Dùng gì |
|---|---|
| Tên -> điểm | Dictionary |
| Lọc trùng | Set |
| Tra cứu theo giá trị | Dictionary |
| Bạn chung 2 nhóm | Giao 2 set |
Ví dụ
- Input: dict {Vàng: thủ công}, hỏi màu đã duyệt. Output: Xanh lá.
- Giải thích: đưa khóa vào là nhận giá trị ngay.
diem = {"An": 9} # từ điển tên -> điểm
diem["An"] = 10 # ghi đè giá trị cũ
print("An" in diem) # kiểm tra khóa tồn tại
💻 Bài tập
Ngôn ngữ: C++17. Bài 1 được dùng std::unordered_map, std::unordered_set. Bài 3 tự cài. Nộp vào day-005/.
Bài 1: Đếm từ và lọc trùng
Viết chương trình đọc một file văn bản tiếng Việt hoặc tiếng Anh.
| Hàm | Yêu cầu |
|---|---|
std::vector<std::string> tokenize(const std::string &text) | Tách từ theo khoảng trắng và dấu câu, đưa về chữ thường |
std::unordered_map<std::string, int> countWords(...) | Đếm tần suất từng từ |
std::vector<std::pair<std::string,int>> topK(map, k) | Trả k từ xuất hiện nhiều nhất, hòa thì theo alphabet |
size_t distinctWords(...) | Số từ khác nhau, dùng unordered_set |
"An an AN, bình. Bình!" -> {an: 3, bình: 2}; distinct = 2; top1 = (an, 3)
"" -> {} ; distinct = 0
Bài 2: Phép toán tập hợp
Viết 3 hàm nhận hai std::unordered_set<int> và trả tập mới: unionOf, intersectOf, differenceOf.
Ứng dụng: cho danh sách bạn bè của 2 người, in bạn chung và gợi ý kết bạn (bạn của B mà A chưa kết bạn, trừ chính A).
A = {1,2,3,4}, B = {3,4,5}
union -> {1,2,3,4,5}
intersect -> {3,4}
A - B -> {1,2}
Ràng buộc: intersectOf duyệt tập nhỏ hơn, tra trong tập lớn hơn. Ghi độ phức tạp vào comment.
Bài 3: Tự cài hash set số nguyên (nâng cao)
Cài IntHashSet bằng separate chaining. Không dùng container băm của thư viện.
| Hàm | Yêu cầu |
|---|---|
bool insert(int x) | Trả false nếu đã có |
bool contains(int x) const | |
bool erase(int x) | |
size_t size() const, double loadFactor() const | |
| Rehash | Khi loadFactor > 0.75 thì gấp đôi số bucket và chèn lại |
Hàm băm: h(x) = (uint32_t)x * 2654435761u % buckets.
insert 1..1000 -> size=1000, loadFactor <= 0.75
contains(500) / (1001) -> true / false
erase(500); contains(500) -> false
insert -7; contains(-7) -> true
Đo thời gian insert số ngẫu nhiên, so với std::unordered_set. Ghi kết quả vào README.md.
✅ Tiêu chí hoàn thành
- Test mẫu của cả 3 bài pass.
- Bài 3 rehash đúng: sau rehash mọi phần tử cũ vẫn
contains. - Sanitizer sạch.
- Giải thích được khi nào dùng dict, khi nào dùng set, và vì sao tra cứu là trung bình chứ không phải tệ nhất.
❓ Câu hỏi ôn tập
- Dictionary gồm gì, khóa có quy tắc gì?
- Set khác dictionary ở điểm nào?
- Hàm băm giúp tra cứu nhanh thế nào?
- Khi nào dùng set thay dictionary?
🌕 Bạn đã hoàn thành ngày 5. Làm hết bài tập phía trên rồi sang ngày tiếp theo.