Giới thiệu

unordered_map và unordered_set là hai container mạnh mẽ trong thư viện chuẩn C++ STL, dựa trên cơ chế bảng băm để đạt được hiệu năng trung bình O(1) cho các thao tác tìm kiếm, chèn và xóa. Bài viết này sẽ phân tích nguyên lý hoạt động bên trong của chúng và cung cấp bản giả lập bằng C++.

Kiến thức nền

Bảng băm

Cấu trúc dữ liệu bảng băm sử dụng hàm băm để ánh xạ khóa thành chỉ số mảng. Phương pháp này cho phép truy cập trực tiếp tới phần tử thông qua chỉ số đã tính toán.

Hàm băm

Hàm băm chuyển đổi đầu vào có độ dài bất kỳ thành giá trị đầu ra cố định. Hàm băm tốt cần phân bố đều các khóa và giảm thiểu va chạm.

Hệ số tải

Tỷ lệ giữa số phần tử và số bucket trong bảng. Khi hệ số tải vượt ngưỡng, hiệu năng giảm do gia tăng va chạm.

Giả lập unordered_set

Thiết kế cấu trúc dữ liệu

Sử dụng vector chứa các danh sách liên kết (bucket), mỗi bucket chứa các phần tử va chạm.

template<typename T>
class UnorderedSet {
private:
    std::vector<std::list<T>> bang;
    size_t sucChua;
    size_t kichThuoc;
    float nguongTai;
    size_t (*hamBam)(const T&);
public:
    UnorderedSet(size_t kichCoBanDau = 16, float heSoTai = 0.75f) 
        : sucChua(kichCoBanDau), kichThuoc(0), nguongTai(heSoTai) {
        bang.resize(sucChua);
        hamBam = &UnorderedSet::tinhBam;
    }
    // Các phương thức
};

Giải quyết va chạm

Áp dụng phương pháp chaining - lưu các phần tử va chạm trong cùng một danh sách liên kết.

Thao tác chèn

Kiểm tra ngưỡng tải trước khi chèn, cập nhật kích thước sau khi thêm phần tử.

template<typename T>
bool UnorderedSet<T>::chen(const T& giaTri) {
    if (kichThuoc >= sucChua * nguongTai) {
        phanBoLai();
    }
    size_t chiSo = hamBam(giaTri);
    auto& thung = bang[chiSo];
    if (timKiem(thung, giaTri)) return false;
    thung.push_back(giaTri);
    kichThuoc++;
    return true;
}

Thao tác tìm kiếm

Thao tác xóa

Giả lập unordered_map

Lưu trữ cặp khóa-giá trị

Giống unordered_set nhưng lưu trữ các cặp std::pair<K,V>

template<typename K, typename V>
class UnorderedMap {
private:
    std::vector<std::list<std::pair<K,V>>> bang;
    size_t sucChua;
    size_t kichThuoc;
    float nguongTai;
    size_t (*hamBam)(const K&);
public:
    UnorderedMap(size_t kichCo = 16, float heSo = 0.75f) 
        : sucChua(kichCo), kichThuoc(0), nguongTai(heSo) {
        bang.resize(sucChua);
        hamBam = &UnorderedMap::tinhBam;
    }
    // Các phương thức
};

Thao tác chèn

Trả về iterator và trạng thái thành công khi chèn cặp khóa-giá trị.

Thao tác tìm kiếm

Thao tác xóa

Ví dụ sử dụng

int main() {
    UnorderedSet<int> tapHop;
    tapHop.chen(10);
    tapHop.chen(20);
    std::cout << "Tồn tại 20: " << tapHop.timKiem(20) << std::endl;

    UnorderedMap<std::string, int> banDo;
    banDo.chen({"mot", 1});
    auto vitri = banDo.timKiem("mot");
    if (vitri != banDo.layCuoi()) {
        std::cout << "Giá trị: " << vitri->second << std::endl;
    }
    return 0;
}