1. Khái niệm

Trong C++, hash map được cài đặt bởi unordered_map trong thư viện STL (Standard Template Library).
Đây là một container lưu cặp key–value, cho phép:

• Tìm kiếm, chèn, xóa phần tử trung bình trong O(1) thời gian.

• Các phần tử không có thứ tự, được sắp xếp theo hàm băm (hash function).

Cú pháp khai báo:

#include <unordered_map> using namespace std; unordered_map<KeyType, ValueType> myMap;

Ví dụ:

unordered_map<string, int> mp; // key: string, value: int

---

2. Các thao tác cơ bản

2.1. Thêm phần tử

unordered_map<string, int> mp; mp["apple"] = 3; // cách 1: dùng [] mp.insert({"banana", 5}); // cách 2: dùng insert()

2.2. Truy cập phần tử

cout << mp["apple"]; // Truy cập value qua key cout << mp.at("banana"); // Dùng at() -> ném exception nếu không tồn tại

2.3. Kiểm tra tồn tại key

if (mp.find("orange") != mp.end()) { cout << "Có orange\n"; } else { cout << "Không có orange\n"; }

2.4. Duyệt các phần tử

for (auto &p : mp) { cout << p.first << " " << p.second << "\n"; }

2.5. Xóa phần tử

mp.erase("apple"); // Xóa theo key mp.clear(); // Xóa toàn bộ map

---

3. Một số hàm hữu ích

• mp.size() → số phần tử.

• mp.empty() → kiểm tra rỗng.

• mp.count(key) → trả về 1 nếu tồn tại key, 0 nếu không.

• mp.bucket_count() → số bucket trong hash table.

• mp.load_factor() → hệ số tải (load factor).

  4. Ví dụ minh họa

  Bài toán: Đếm số lần xuất hiện của các từ trong một câu.

  #include <bits/stdc++.h> using namespace std; int main() { unordered_map<string, int> freq; string word; // Nhập dữ liệu string s = "apple banana apple orange banana apple"; stringstream ss(s); while (ss >> word) { freq[word]++; } // In kết quả for (auto &p : freq) { cout << p.first << ": " << p.second << endl; } return 0; }

  Kết quả có thể là:

  orange: 1 banana: 2 apple: 3

  ---

  5. Lưu ý khi dùng

• Key nên có hàm băm tốt (C++ hỗ trợ sẵn cho kiểu cơ bản: int, string, char...).

• Nếu muốn dùng pair, struct làm key thì phải tự định nghĩa hash function.

• Trong thi đấu lập trình, unordered_map thường nhanh hơn map, nhưng cần lưu ý trường hợp tệ nhất (có thể bị hack test).