Bảng băm (hash table) là cấu trúc dữ liệu phổ biến trong lập trình. Bài viết này tập trung vào cách sử dụng các phương thức của unordered_map và unordered_set trong C++ thông qua các ví dụ cụ thể.

Khai báo hash table

#include <unordered_map>
// Cú pháp tổng quát
unordered_map<KieuKhoa, KieuGiaTri> tenBien;

// Ví dụ với kiểu int
unordered_map<int, int> myMap;

// Ví dụ với key là char và value là int
unordered_map<char, int> charMap;

Khởi tạo hash table

// Khởi tạo với danh sách các cặp key-value
unordered_map<int, int> scores{ {1, 100}, {2, 90}, {3, 85} };

// Key là kiểu char
unordered_map<char, int> frequencies{ {'a', 3}, {'b', 5}, {'c', 2} };

Thêm và sửa phần tử (giống mảng)

// Gán giá trị mới cho key (nếu chưa tồn tại thì thêm mới)
scores[1] = 95;  // Sửa giá trị từ 100 thành 95
scores[4] = 88;  // Thêm cặp {4, 88}

Sử dụng hàm insert

scores.insert({5, 76});  // Thêm cặp {5, 76}

Sao chép hash table

unordered_map<int, int> original{ {1, 50}, {2, 60} };
unordered_map<int, int> copy(original);  // Sao chép toàn bộ

Các hàm iterator trong STL

// Khai báo iterator trỏ đến đầu hash table
unordered_map<int, int>::iterator it = scores.begin();
cout << it->first << ": " << it->second;

// Iterator cho char key
unordered_map<char, int>::iterator start = frequencies.begin();
unordered_map<char, int>::iterator stop = frequencies.end();

Giải thích begin() và end():

• begin(): Trả về iterator trỏ đến phần tử đầu tiên của hash table.
• end(): Trả về iterator trỏ đến vị trí "sau" phần tử cuối cùng. Không thể giải tham chiếu (dereference) iterator này vì sẽ gây lỗi không xác định. Thường dùng để kiểm tra điều kiện kết thúc vòng lặp.

int main() {
    unordered_map<char, int> data;
    data['x'] = 10;
    data['y'] = 20;
    data['z'] = 30;

    // Khai báo iterator trỏ đến vị trí kết thúc
    unordered_map<char, int>::iterator endPos = data.end();

    // Duyệt toàn bộ hash table
    for (auto pos = data.begin(); pos != data.end(); ++pos) {
        cout << pos->first << ": " << pos->second << endl;
    }
    return 0;
}

cbegin() và cend() - iterator hằng

const unordered_map<int, int> fixedMap{ {1, 100}, {2, 200} };
unordered_map<int, int>::const_iterator cit = fixedMap.cbegin();
// Không thể thay đổi giá trị qua cit

Xóa phần tử: erase() và clear()

myMap.erase(1);   // Xóa phần tử có key = 1
myMap.clear();    // Xóa toàn bộ hash table

// Ví dụ chi tiết
unordered_map<int, string> studentMap;
studentMap[1] = "Alice";
studentMap[2] = "Bob";
studentMap[3] = "Charlie";

studentMap.erase(2);
// Kết quả: còn {1: "Alice", 3: "Charlie"}

Xóa các phần tử có giá trị cụ thể:

unordered_map<int, int> values;
values[1] = 15;
values[2] = 25;
values[3] = 15;
values[4] = 35;

// Duyệt và xóa tất cả phần tử có value = 15
for (auto it = values.begin(); it != values.end(); ) {
    if (it->second == 15) {
        it = values.erase(it);  // erase trả về iterator cho phần tử tiếp theo
    } else {
        ++it;
    }
}
// Kết quả: {2: 25, 4: 35}

So sánh unordered_set và unordered_map

Cả hai đều dựa trên hash table nhưng có điểm khác biệt:

1. Kiểu dữ liệu lưu trữ

• unordered_set: Lưu các phần tử duy nhất (không trùng lặp). Là tập hợp, mỗi phần tử chỉ xuất hiện một lần.
• unordered_map: Lưu cặp key-value, key là duy nhất nhưng value có thể trùng. Giống như từ điển.

2. Cách truy cập

• unordered_set: Chỉ truy cập thông qua giá trị phần tử, không hỗ trợ chỉ mục.
• unordered_map: Truy cập giá trị thông qua key, tương tự ánh xạ.

3. Thao tác chèn

• unordered_set: Chèn giá trị đơn, trả về pair gồm iterator (trỏ đến vị trí chèn) và bool (thành công hay không).
• unordered_map: Chèn cặp key-value, cũng trả về pair tương tự.

unordered_set<int> primes = {2, 3, 5, 7};
primes.insert(11);  // Thêm giá trị 11

unordered_map<string, int> ages;
ages.insert({"John", 25});  // Thêm cặp key-value