unordered_map và unordered_set trong C++

Trong C++, unordered_map và unordered_set là hai cấu trúc dữ liệu thuộc thư viện chuẩn (Standard Template Library – STL). Chúng được thiết kế để lưu trữ và truy xuất dữ liệu một cách hiệu quả, đặc biệt khi bạn cần thực hiện các thao tác như tìm kiếm, thêm, hoặc xóa phần tử với độ phức tạp thời gian trung bình là O(1) .

Dưới đây là tổng quan chi tiết về unordered_map và unordered_set.

1. unordered_map

Khái niệm:

• unordered_map là một cấu trúc dữ liệu lưu trữ các cặp key-value (khóa-giá trị).
• Các khóa (key) trong unordered_map là duy nhất, nghĩa là không có hai khóa nào trùng nhau.
• Dữ liệu được tổ chức dựa trên bảng băm (hash table ), giúp việc tìm kiếm, thêm, và xóa phần tử nhanh chóng.

Ưu điểm:

• Độ phức tạp trung bình của các thao tác cơ bản (tìm kiếm, thêm, xóa) là O(1) .
• Phù hợp khi bạn cần lưu trữ và truy xuất dữ liệu dựa trên khóa mà không quan tâm đến thứ tự.

Cú pháp khai báo:

#include <unordered_map>
std::unordered_map<KeyType, ValueType> mapName;

Ví dụ:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    // Khai báo unordered_map
    unordered_map<string, int> ageMap;

    // Thêm phần tử vào unordered_map
    ageMap["Alice"] = 25;
    ageMap["Bob"] = 30;
    ageMap["Charlie"] = 35;

    // Truy xuất giá trị bằng khóa
    cout << "Tuổi của Alice: " << ageMap["Alice"] << endl;

    // Kiểm tra sự tồn tại của một khóa
    if (ageMap.find("Bob") != ageMap.end()) {
        cout << "Bob có trong map.\n";
    }

    // Duyệt qua tất cả các phần tử
    for (auto it = ageMap.begin(); it != ageMap.end(); it++) {
        cout << it->first << ": " << it->second << endl;
    }

    return 0;
}

Output:

Tuổi của Alice: 25
Bob có trong map.
Alice: 25
Bob: 30
Charlie: 35

2. unordered_set

Khái niệm:

• unordered_set là một cấu trúc dữ liệu lưu trữ các phần tử duy nhất (không trùng lặp).
• Các phần tử trong unordered_set không có thứ tự cụ thể.
• Dữ liệu cũng được tổ chức dựa trên bảng băm (hash table ).

Ưu điểm:

• Độ phức tạp trung bình của các thao tác cơ bản (tìm kiếm, thêm, xóa) là O(1) .
• Phù hợp khi bạn cần lưu trữ tập hợp các phần tử duy nhất mà không quan tâm đến thứ tự.

Cú pháp khai báo:

#include <unordered_set>
std::unordered_set<ElementType> setName;

Ví dụ:

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // Khai báo unordered_set
    unordered_set<int> numberSet;

    // Thêm phần tử vào unordered_set
    numberSet.insert(10);
    numberSet.insert(20);
    numberSet.insert(30);

    // Kiểm tra sự tồn tại của một phần tử
    if (numberSet.find(20) != numberSet.end()) {
        cout << "20 có trong set.\n";
    }

    // Xóa một phần tử
    numberSet.erase(10);

    // Duyệt qua tất cả các phần tử
    for (auto it = numberSet.begin(); it != numberSet.end(); it++) {
        cout << *it << " ";
    }

    return 0;
}

Output:

20 có trong set.
20 30

3. So sánh unordered_map và unordered_set

4. Cách hoạt động của bảng băm (Hash Table)

• Bảng băm là cơ chế chính đằng sau unordered_map và unordered_set.
• Mỗi phần tử được ánh xạ vào một vị trí trong bảng băm thông qua hàm băm (hash function ).
• Nếu xảy ra xung đột (collision), tức là hai phần tử có cùng giá trị băm, chúng sẽ được xử lý bằng các kỹ thuật như chaining (liên kết) hoặc open addressing (địa chỉ mở).

5. Khi nào nên sử dụng unordered_map/unordered_set?

• Sử dụng unordered_map:
  • Khi bạn cần lưu trữ dữ liệu dưới dạng cặp key-value.
  • Khi bạn cần truy xuất nhanh chóng dựa trên khóa (ví dụ: đếm tần suất xuất hiện của phần tử).
• Sử dụng unordered_set:
  • Khi bạn cần lưu trữ tập hợp các phần tử duy nhất.
  • Khi bạn cần kiểm tra nhanh xem một phần tử có tồn tại trong tập hợp hay không.

6. Nhược điểm của unordered_map và unordered_set

Không đảm bảo thứ tự: Các phần tử không được sắp xếp theo bất kỳ thứ tự nào.

• Hiệu suất trong trường hợp xấu nhất: Trong trường hợp xảy ra nhiều xung đột, độ phức tạp có thể tăng lên O(n) .
• Không phù hợp với dữ liệu lớn: Khi số lượng phần tử quá lớn, việc quản lý bảng băm có thể trở nên kém hiệu quả.

7. So sánh với map và set

8. Tổng kết

• unordered_map và unordered_set là công cụ mạnh mẽ trong lập trình C++, đặc biệt khi bạn cần thực hiện các thao tác nhanh chóng trên dữ liệu.
• Chúng rất hữu ích trong các bài toán như đếm tần suất, kiểm tra sự tồn tại của phần tử, hoặc lưu trữ tập hợp duy nhất.
• Tuy nhiên, hãy cân nhắc giữa unordered_map/unordered_set và map/set tùy thuộc vào yêu cầu về thứ tự và hiệu suất của bài toán.

Chúc bạn thành công trong việc áp dụng unordered_map và unordered_set vào các bài toán lập trình! 🚀