unordered_map trong C++: tra cứu hash map tốc độ cao

Khi thứ tự không quan trọng

Bạn vừa thấy std::map, giữ các khóa luôn được sắp xếp bằng một cây cân bằng và cho các thao tác O(log n). Nhưng sắp xếp thì tốn chi phí, và rất nhiều khi bạn không quan tâm các khóa xuất hiện theo thứ tự nào: bạn chỉ muốn hỏi "khóa này có ở đây không, và giá trị của nó là gì?" càng nhanh càng tốt.

Đó là việc của std::unordered_map. Nó là một bảng băm (hash table): mỗi khóa được đưa qua một hàm băm để quyết định vị trí lưu, nhờ vậy thêm, tra cứu và xóa có độ phức tạp trung bình O(1) thay vì O(log n). Cái giá phải trả là thứ tự duyệt không xác định: các khóa xuất hiện theo bất kỳ thứ tự nào mà các bucket đang giữ chúng.

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

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

Giao diện của nó cố ý được thiết kế gần như giống hệt map, nên bạn thường có thể đổi qua lại chỉ bằng cách đổi kiểu. Hãy include <unordered_map> (không phải <map>), và các khóa sẽ xuất hiện không theo thứ tự.

Thêm và cập nhật

Có vài cách để thêm phần tử, và chúng không hoạt động giống nhau. Hai cách bạn sẽ dùng nhiều nhất là operator[] và insert:

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

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // create or overwrite
    votes["alice"] = 5;              // overwrites -> 5
    votes.insert({"bob", 2});        // inserts only if "bob" is absent
    votes.insert({"bob", 99});       // ignored, "bob" already exists

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, not 99
}

Khác biệt chính: operator[] ghi đè giá trị đã có, còn insert giữ nguyên khóa đã tồn tại. Nếu bạn dùng C++17, insert_or_assign(key, value) cho bạn ngữ nghĩa "gán bất kể thế nào", còn try_emplace(key, args...) chỉ tạo giá trị tại chỗ khi khóa còn mới, rất tiện cho những giá trị tốn công tạo.

Cái bẫy của operator[]: đọc cũng thêm khóa

Đây là bug phổ biến nhất với unordered_map, nên nó có hẳn một phần riêng. m[key] không chỉ đơn thuần là đọc. Nếu khóa chưa có, nó sẽ tạo giá trị mặc định và thêm khóa đó vào (một int thành 0, một string thành ""), rồi trả về tham chiếu. Vì vậy, code trông như tra cứu lại âm thầm làm map lớn lên:

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

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // We only meant to CHECK for "y", but [] inserted it:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, not 1!
}

seen["y"] đã tạo ra mục "y" -> 0 chỉ vì được nhắc đến. Để kiểm tra một khóa có tồn tại mà không thay đổi map, hãy dùng count (trả về 0 hoặc 1) hoặc find:

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

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() reads cleaner than count()
    if (seen.contains("x")) cout << "x is here\n";
}

Quy tắc chung: chỉ dùng [] khi bạn muốn tạo mới hoặc cập nhật. Với thao tác chỉ đọc, hãy dùng count, contains (C++20) hoặc find.

find và at: tra cứu an toàn

find trả về một iterator trỏ đến phần tử, hoặc end() nếu khóa không tồn tại. Nó không bao giờ thêm khóa, và cho phép bạn lấy cả khóa lẫn giá trị qua it->first và it->second chỉ với một lần tra cứu:

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

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Khi bạn biết chắc khóa phải tồn tại và muốn chương trình báo lỗi rõ ràng nếu không có, hãy dùng at. Khác với [], at không thêm khóa: nó ném std::out_of_range khi khóa không có:

int p = prices.at("pen");   // fine
int q = prices.at("hat");   // throws std::out_of_range - key absent

Vậy là bạn có ba cách tra cứu: [] (thêm khóa), at (ném ngoại lệ) và find/count (báo khóa có tồn tại hay không mà không đụng vào map). Hãy chọn cách có kiểu xử lý thất bại khớp với ý định của bạn.

Duyệt và xóa

Vòng lặp for dạng range-based kết hợp structured binding là cách gọn gàng để đi qua mọi phần tử. Nhớ rằng thứ tự là tùy ý, đừng bao giờ dựa vào nó:

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

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // order is unspecified
    }
}

Để xóa một phần tử, erase nhận trực tiếp một khóa và trả về số phần tử đã xóa (0 hoặc 1). Một cái bẫy quan trọng: trong unordered_map, xóa trong lúc duyệt chỉ làm vô hiệu iterator của phần tử bị xóa, vì vậy hãy dùng giá trị trả về của erase(it) để tiến lên một cách an toàn:

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

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Drop every team with a score below 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase returns the next valid iterator
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Viết kiểu wins.erase(it++) hoặc ++it sau một lệnh erase(it) thông thường là cái bẫy iterator treo kinh điển: iterator đã bị xóa không còn dùng được, nên hãy luôn lấy iterator mà erase trả về.

map hay unordered_map?

Cả hai đều lưu các cặp khóa và giá trị với API tương tự, nên lựa chọn phụ thuộc vào nhu cầu của bạn:

// std::map            -> sorted keys, O(log n), range queries (lower_bound)
// std::unordered_map  -> no order,    O(1) avg, fastest plain lookup

Hãy dùng unordered_map khi bạn chỉ cần tra cứu nhanh theo khóa và thứ tự không quan trọng (đếm tần suất từ, cache, loại bỏ trùng lặp). Chọn map khi bạn cần các khóa được sắp xếp, muốn duyệt theo thứ tự hoặc truy vấn theo khoảng. Hai lưu ý với unordered_map: O(1) của nó là trung bình, một hàm băm tệ có thể làm nó chậm đi; và một kiểu khóa tự định nghĩa cần một bản chuyên biệt hóa hash hoặc một hash functor, trong khi map chỉ cần operator<.

Tiếp theo: set

Giờ bạn đã thấy cả hai loại container khóa và giá trị. Tuy nhiên, đôi khi bạn hoàn toàn không cần giá trị: bạn chỉ quan tâm liệu một thứ có tồn tại hay không, ví dụ một tập các tag không trùng nhau hoặc các ID đã ghé thăm. Tiếp theo, chúng ta sẽ xem std::set (và người anh em dùng bảng băm của nó là unordered_set), chỉ lưu khóa và tự động giữ cho chúng không trùng lặp.