Giới Thiệu Chung

Vào hệ thống thư viện tiêu chuẩn C++, hai thành phần unordered_map và unordered_set đóng vai trò quan trọng nhờ cấu trúc dữ liệu bảng băm (Hash Table). Khác với các container có trật tự, chúng ưu tiên tốc độ truy xuất trung bình đạt O(1) cho các thao tác chèn, tìm kiếm và xóa. Bài viết này sẽ phân tích chi tiết nguyên lý, cách sử dụng và các lưu ý kỹ thuật khi làm việc với hai công cụ này.

Nguyên Lý Hoạt Động Cơ Bản

Bảng Băm (Hash Table)

• Cơ chế: Chuyển đổi khóa (Key) thành chỉ số mảng thông qua hàm băm, giúp định vị dữ liệu trực tiếp mà không cần duyệt tuần tự.
• Xử lý xung đột: Khi nhiều khóa ánh xạ đến cùng một vị trí, phương pháp phổ biến là dùng danh sách liên kết để lưu trữ các giá trị xung đột tại cùng một bucket.

Phân Biệt Hai Container

• unordered_map: Lưu trữ cặp khóa-giá trị (key-value). Khóa phải duy nhất, giá trị có thể trùng lặp.
• unordered_set: Chỉ lưu trữ khóa duy nhất, tự động loại bỏ các giá trị trùng nhau.

Thao Tác Thường Gặp Và Ví Dụ Minh Họa

Dưới đây là ví dụ khởi tạo và thực hiện các thao tác cơ bản bằng cú pháp C++ hiện đại.

#include <unordered_map>
#include <unordered_set>
#include <iostream>

int main() {
    // Khởi tạo unordered_map lưu điểm số sinh viên
    std::unordered_map<std::string, double> studentScores{
        {"Alice", 9.5}, {"Bob", 8.0}
    };

    // Khởi tạo unordered_set lưu ID đã đăng ký
    std::unordered_set<int> activeIds = {101, 102, 103};

    return 0;
}

Thêm Và Cập Nhật Dữ Liệu

// Thêm hoặc cập nhật vào map
studentScores["Charlie"] = 7.5;           // Thao tác qua toán tử []
studentScores.emplace("Diana", 9.0);      // Hàm construct trực tiếp hiệu quả hơn

// Thêm vào set
activeIds.insert(104);

Tìm Kiếm Và Kiểm Tra Sự Hiện Diện

// Kiểm tra trong map
auto result = studentScores.find("Eve");
if (result != studentScores.cend()) {
    std::cout << "Found score: " << result->second << "\n";
} else {
    std::cout << "Student not found.\n";
}

// Kiểm tra sự tồn tại trong set (trả về bool)
if (activeIds.count(102)) {
    std::cout << "ID 102 is active.\n";
}

Xóa Phần Tử Và Duyệt Vòng

// Xóa theo khóa
studentScores.erase("Bob");

// Duyệt qua map
for (const auto& [name, score] : studentScores) {
    std::cout << name << ": " << score << "\n";
}

// Duyệt qua set
for (const int id : activeIds) {
    std::cout << "Active ID: " << id << "\n";
}

Phân Tích Hiệu Suất

Độ Phức Tạp Thời Gian

So Sánh Với Container Có Trật Tự (map, set)

Các Kịch Bản Ứng Dụng Thực Tế

Khi Nên Dùng unordered_map

• Gán nhãn tần suất: Đếm số lần xuất hiện của từ khóa trong văn bản.
• Hệ thống đệm (Cache): Lưu trữ kết quả tạm thời để truy xuất nhanh theo ID.
• Quan hệ ánh xạ: Liên kết mã hóa sản phẩm với thông tin kho hàng.

Khi Nên Dùng unordered_set

• Lọc trùng lặp: Loại bỏ các mục giống nhau trong danh sách log hệ thống.
• Kiểm soát truy cập: Xác minh nhanh chóng xem người dùng có nằm trong danh sách cấm hay không.
• Toán học tập hợp: Thực hiện giao hoặc hợp của các nhóm dữ liệu lớn.

Kỹ Thuật Nâng Cao Và Lưu Ý Quan Trọng

Định Nghĩa Hàm Băm Tùy Chỉnh

Khi sử dụng kiểu dữ liệu do người dùng định nghĩa (struct/class) làm khóa, bạn cần cung cấp hàm băm riêng.

struct MetricData {
    int id;
    float value;
};

struct MetricHash {
    size_t operator()(const MetricData& m) const noexcept {
        size_t h1 = std::hash<int>{}(m.id);
        size_t h2 = std::hash<float>{}(m.value);
        return h1 ^ (h2 << 1);
    }
};

struct MetricEqual {
    bool operator()(const MetricData& a, const MetricData& b) const {
        return a.id == b.id && std::abs(a.value - b.value) < 0.001f;
    }
};

using MetricMap = std::unordered_map<MetricData, int, MetricHash, MetricEqual>;

Tối Ưu Hiệu Năng Bộ Nhớ

Hệ số tải (Load Factor) quyết định mật độ phần tử trên mỗi bucket. Tăng tỷ lệ này làm giảm dung lượng nhưng tăng nguy cơ va chạm.

MetricMap dataStore;
dataStore.max_load_factor(0.8f);     // Cho phép mật độ cao hơn trước khi resize
dataStore.reserve(500);              // Dự trữ dung lượng cho 500 phần tử tránh tái phân bổ

Thời Điểm Lựa Chọn Phù Hợp

Để tối ưu hóa ứng dụng, hãy chọn unordered_map/set khi bạn cần tốc độ xử lý cực nhanh cho các truy vấn ngẫu nhiên và không yêu cầu dữ liệu được sắp xếp. Ngược lại, nếu bài toán đòi hỏi duyệt tuần tự có trật tự hoặc tìm kiếm theo khoảng (range search), các container dựa trên cây như std::map vẫn là lựa chọn chính xác hơn.