🧩 Hash Table & Priority Queue

🎯 Mục tiêu bài học

1. Đặt vấn đề

1.1. Dùng cấu trúc nào?

2. Hash Table và unordered_map

unordered_map frequency;

frequency["apple"]++;
frequency["banana"] += 2;

if (frequency.find("apple")
    != frequency.end()) {
    cout << frequency["apple"];
}

3. Mô phỏng Hash Table

4. Va chạm Hash

Hai khóa khác nhau có thể được ánh xạ vào cùng một bucket. Đây gọi là collision.

5. Priority Queue

priority_queue pq;

pq.push(5);
pq.push(10);
pq.push(3);

cout << pq.top(); // 10

priority_queue<
    int,
    vector,
    greater
> pq;

6. Mô phỏng Priority Queue

7. Mô phỏng lịch xử lý công việc

8. Phân tích và lựa chọn cấu trúc

9. Code mẫu

#include 
using namespace std;

int main() {
    int n;
    cin >> n;

    unordered_map frequency;

    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        frequency[word]++;
    }

    int q;
    cin >> q;

    while (q--) {
        string word;
        cin >> word;

        auto iterator = frequency.find(word);

        if (iterator == frequency.end()) {
            cout << 0 << '
';
        } else {
            cout << iterator->second << '
';
        }
    }
}

unordered_map nameById;

nameById[10] = "An";
nameById.insert({20, "Binh"});
nameById.emplace(30, "Chi");

if (nameById.count(20)) {
    cout << nameById.at(20);
}

auto iterator = nameById.find(30);

if (iterator != nameById.end()) {
    nameById.erase(iterator);
}

for (const auto& [id, name] : nameById) {
    cout << id << ' ' << name << '
';
}

#include 
using namespace std;

int main() {
    priority_queue pq;

    pq.push(5);
    pq.push(10);
    pq.push(3);
    pq.push(8);

    while (!pq.empty()) {
        cout << pq.top() << ' ';
        pq.pop();
    }
}

// Output: 10 8 5 3

#include 
using namespace std;

int main() {
    priority_queue<
        long long,
        vector,
        greater
    > minHeap;

    minHeap.push(5);
    minHeap.push(10);
    minHeap.push(3);
    minHeap.push(8);

    while (!minHeap.empty()) {
        cout << minHeap.top() << ' ';
        minHeap.pop();
    }
}

// Output: 3 5 8 10

#include 
using namespace std;

struct Job {
    int id;
    int priority;
};

struct CompareJob {
    bool operator()(
        const Job& a,
        const Job& b
    ) const {
        if (a.priority != b.priority) {
            return a.priority < b.priority;
        }

        return a.id > b.id;
    }
};

int main() {
    priority_queue<
        Job,
        vector,
        CompareJob
    > jobs;

    jobs.push({3, 5});
    jobs.push({1, 5});
    jobs.push({2, 7});

    while (!jobs.empty()) {
        Job current = jobs.top();
        jobs.pop();

        cout << current.id
             << ' '
             << current.priority
             << '
';
    }
}

from collections import Counter
import heapq

words = ["apple", "banana", "apple"]
frequency = Counter(words)

min_heap = []

heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 3)

while min_heap:
    print(heapq.heappop(min_heap))

10. Giải thích code

10.1. Vì sao frequency[word]++ hoạt động?

Nếu khóa chưa tồn tại, operator[] tạo một phần tử mới với giá trị mặc định 0, sau đó tăng lên 1.

10.2. Khi nào nên dùng find thay vì operator[]?

Khi chỉ muốn kiểm tra hoặc đọc mà không muốn tạo khóa mới. mp[key] có thể làm thay đổi map.

10.3. Vì sao unordered_map không có thứ tự tăng dần?

Phần tử được tổ chức theo bucket của hash, không theo thứ tự khóa.

10.4. Vì sao priority_queue mặc định là max-heap?

Comparator mặc định làm phần tử lớn nhất có độ ưu tiên cao nhất và nằm ở top().

10.5. Comparator Priority Queue có vẻ “ngược” vì sao?

Comparator trả về true khi a có độ ưu tiên thấp hơn b. Với max-heap số nguyên, less làm số lớn nhất ở top.

10.6. Vì sao top() không xóa phần tử?

top() chỉ xem phần tử ưu tiên nhất. Muốn xóa, phải gọi pop() riêng.

10.7. Có thể sửa trực tiếp pq.top() không?

Không nên và giao diện chuẩn trả về tham chiếu hằng. Sửa trực tiếp có thể phá tính chất heap.

10.8. Khi nào dùng lazy deletion?

Khi cần “xóa” hoặc cập nhật phần tử không nằm ở top. Ta đánh dấu dữ liệu cũ là không còn hợp lệ và bỏ qua khi nó lên top.

11. Lỗi thường gặp

• Dùng mp[key] chỉ để kiểm tra và vô tình tạo khóa.
• Cho rằng unordered_map duyệt theo thứ tự chèn hoặc thứ tự khóa.
• Giả sử mọi thao tác hash luôn O(1), bỏ qua worst case.
• Quên rằng rehash có thể làm iterator bị vô hiệu hóa.
• Gọi top() hoặc pop() khi Priority Queue rỗng.
• Tưởng pop() trả về phần tử.
• Dùng comparator sai chiều trong Priority Queue.
• Tưởng Priority Queue hỗ trợ xóa phần tử bất kỳ hiệu quả.
• Dùng priority_queue> nhưng quên quy tắc so sánh từ điển.
• Dùng min-heap nhưng quên thêm greater.

12. Quiz và bài tập