Setelah memahami implementasi manual hash table, sekarang kita memakai versi siap pakai dari STL: std::unordered_map<K, V> dan std::unordered_set<T>. Kedua container ini menggunakan separate chaining di bawah hood, memberi kompleksitas rata-rata O(1) untuk insert, find, dan erase. Pada Chapter ini kita akan mempelajari API dasar, bagaimana menyediakan hash function dan equality predicate untuk tipe custom, lalu membandingkannya dengan std::map (BST) untuk membantu kita memilih container yang tepat.

API Dasar #

Mekanisme: Container Asosiatif Berbasis Hash #

std::unordered_map<K, V> menyimpan pasangan key-value unik. std::unordered_set<T> menyimpan himpunan key tanpa value. Keduanya:

  • Tidak menyimpan urutan (berbeda dari std::map / std::set).
  • Mengizinkan iterasi dengan urutan tidak ditentukan.
  • Kompleksitas rata-rata O(1) untuk operasi dasar, O(n) worst case (semua collision).

Kode: unordered_map Dasar #

cpp 
#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> um;

    // Insert dengan operator[]
    um["andi"] = 90;
    um["budi"] = 85;
    um["citra"] = 78;

    // Insert dengan emplace (lebih efisien untuk value baru)
    um.emplace("dewi", 92);

    // Update value existing
    um["budi"] = 88;

    // Akses dengan at() — throws jika key tidak ada
    try {
        std::cout << "nilai andi = " << um.at("andi") << '\n';
        std::cout << "nilai zaki = " << um.at("zaki") << '\n';
    } catch (const std::out_of_range& e) {
        std::cout << "exception: " << e.what() << '\n';
    }

    // Akses dengan operator[] — INSERT default bila tidak ada
    int nilai_eka = um["eka"];   // "eka" tidak ada, um["eka"]=0
    std::cout << "nilai eka (default) = " << nilai_eka << '\n';
    std::cout << "size setelah akses eka = " << um.size() << '\n';

    // find dengan iterator
    auto it = um.find("citra");
    if (it != um.end()) {
        std::cout << "find citra -> " << it->second << '\n';
    }

    // erase
    um.erase("dewi");
    std::cout << "size setelah erase dewi = " << um.size() << '\n';

    // Iterasi (urutan tidak ditentukan)
    std::cout << "\nIsi unordered_map:\n";
    for (const auto& [key, val] : um) {
        std::cout << "  " << key << " -> " << val << '\n';
    }

    // Statistik internal
    std::cout << "\nStatistik:\n";
    std::cout << "  bucket_count = " << um.bucket_count() << '\n';
    std::cout << "  load_factor = " << um.load_factor() << '\n';
    std::cout << "  max_load_factor = " << um.max_load_factor() << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
nilai andi = 90
nilai zaki = exception: unordered_map::at
nilai eka (default) = 0
size setelah akses eka = 5
find citra -> 78
size setelah erase dewi = 4

Isi unordered_map:
  eka -> 0
  citra -> 78
  budi -> 88
  andi -> 90

Statistik:
  bucket_count = 13
  load_factor = 0.307692
  max_load_factor = 1
  1. Baris um["andi"] = 90;: operator[] melakukan insert bila key belum ada, atau update bila sudah ada. Kompleksitas rata-rata O(1).
  2. Baris um.emplace("dewi", 92);: emplace membangun pair langsung di tempat tanpa copy sementara — sedikit lebih efisien daripada um["dewi"] = 92.
  3. Baris um.at("andi"): akses read-only dengan pengecekan key. Bila key tidak ada, lempar std::out_of_range — berbeda dari operator[] yang insert default.
  4. Baris um["eka"]: akses key yang tidak ada — operator[] memasukkan pair {"eka", 0} (default-constructed int = 0). Efek samping: ukuran map bertambah.
  5. Baris um.find("citra"): kembalikan iterator ke entry, atau um.end() bila tidak ketemu. Tidak ada efek samping, tidak insert.
  6. Baris for (const auto& [key, val] : um): structured binding C++17 — unpack pair menjadi variabel terpisah. Urutan iterasi bergantung posisi internal bucket, tidak dijamin alfabetis.
  7. Hasil bucket_count = 13, load_factor = 0.307692: setelah insert 5 entry (andi, budi, citra, dewi, eka), implementasi libstdc++ memilih ukuran bucket prima berikutnya setelah 5 — yaitu 13. Setelah erase("dewi") size menjadi 4, sehingga α = 4/13 ≈ 0.308. max_load_factor = 1 adalah default STL; rehash terjadi ketika α melampaui 1.

unordered_set #

std::unordered_set<T> adalah versi tanpa value — hanya menyimpan himpunan key. API mirip dengan unordered_map tetapi tanpa pasangan value.

Kode: Himpunan dengan unordered_set #

cpp 
#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::unordered_set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(10);  // duplikat, diabaikan
    s.insert(30);

    std::cout << "size = " << s.size() << '\n';   // 3
    std::cout << "count(10) = " << s.count(10) << '\n';   // 1
    std::cout << "count(99) = " << s.count(99) << '\n';    // 0

    // Hapus duplikat dari vector
    std::vector<int> v = {1, 2, 3, 2, 1, 4, 5, 3};
    std::unordered_set<int> seen(v.begin(), v.end());
    std::cout << "\nElemen unik dari {1,2,3,2,1,4,5,3}:\n";
    for (int x : seen) std::cout << x << ' ';
    std::cout << '\n';

    // Cek irisan dua himpunan
    std::unordered_set<int> a = {1, 2, 3, 4, 5};
    std::unordered_set<int> b = {3, 4, 5, 6, 7};
    std::cout << "\nIrisan a dan b:\n";
    for (int x : a) {
        if (b.count(x)) std::cout << x << ' ';
    }
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
size = 3
count(10) = 1
count(99) = 0

Elemen unik dari {1,2,3,2,1,4,5,3}:
5 4 3 2 1

Irisan a dan b:
5 4 3
  1. Baris s.insert(10); s.insert(10);: insert kedua tidak berdampak karena unordered_set hanya menyimpan key unik. size() tetap 1.
  2. Baris s.count(10): kembalikan 0 atau 1 — count bukan total kemunculan (karena unik), tetapi idiomatik untuk “apakah ada?”.
  3. Baris std::unordered_set<int> seen(v.begin(), v.end());: konstruktor range — deduplikasi otomatis dari iterator. Efektif untuk membersihkan duplikat dari koleksi.
  4. Baris for (int x : seen): urutan iterasi tidak ditentukan — pada output di atas 5 4 3 2 1, bukan urutan input 1 2 3 4 5. Iterasi mengikuti urutan internal bucket.
  5. Hasil irisan 5 4 3: iterasi a dan cek keberadaan di b — O(n) rata-rata, jauh lebih cepat daripada nested loop O(n²). Urutan output juga tidak terurut.

Hash Function dan Equality untuk Tipe Custom #

STL menyediakan std::hash<T> untuk tipe bawaan (int, double, string, pointer). Untuk tipe custom, kita perlu menyediakan:

  1. Hash function — objek callable size_t operator()(const T&) const.
  2. Equality predicate — objek callable bool operator()(const T&, const T&) const (default std::equal_to<T> yang memakai operator==).

Kode: unordered_map dengan Key Custom #

cpp 
#include <iostream>
#include <unordered_map>
#include <string>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        // hash_combine idiom: XOR dengan konstanta emas
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;

    m[{0, 0}] = "origin";
    m[{1, 2}] = "kanan-atas";
    m[{3, 4}] = "kanan-jauh";
    m[{-1, -1}] = "kiri-bawah";

    Point target{1, 2};
    auto it = m.find(target);
    if (it != m.end()) {
        std::cout << "Point(1,2) -> " << it->second << '\n';
    }

    std::cout << "\nSemua entry:\n";
    for (const auto& [pt, label] : m) {
        std::cout << "  (" << pt.x << "," << pt.y << ") -> " << label << '\n';
    }

    std::cout << "\nStatistik:\n";
    std::cout << "  bucket_count = " << m.bucket_count() << '\n';
    std::cout << "  load_factor = " << m.load_factor() << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Point(1,2) -> kanan-atas

Semua entry:
  (-1,-1) -> kiri-bawah
  (3,4) -> kanan-jauh
  (1,2) -> kanan-atas
  (0,0) -> origin

Statistik:
  bucket_count = 13
  load_factor = 0.307692
  1. Baris bool operator==(const Point& o) const: wajib didefinisikan untuk equality. Default std::equal_to<Point> akan memanggil operator ini.
  2. Baris struct PointHash { std::size_t operator()(const Point& p) const; }: objek function yang meng-hash Point. Harus deterministic dan uniform.
  3. Baris std::size_t h1 = std::hash<int>{}(p.x);: hash setiap field dengan std::hash<int>. Inisialisasi {} membuat instance sementara.
  4. Baris return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));: idiom hash_combine dari Boost — kombinasi XOR dengan konstanta emas 0x9e3779b9 (rasio fibonacci) plus rotasi bit. Menghasilkan distribusi seragam untuk pasangan field.
  5. Baris std::unordered_map<Point, std::string, PointHash> m;: tipe map dengan tiga template argumen: key, value, hash function type. Karena operator== sudah didefinisikan, equality predicate default bekerja.
  6. Baris m[{0, 0}] = "origin";: aggregate initialization membuat Point{0,0} untuk key. C++17 mendukung syntax ini bila Point adalah aggregate.
  7. Hasil bucket_count = 13, α = 0.308: 4 entry pada 13 bucket. Implementasi libstdc++ memilih ukuran prima terdekat di atas ambang load_factor, yaitu 13. Iterasi (-1,-1), (3,4), (1,2), (0,0) tidak mengikuti urutan insert maupun urutan numerik — itu mengikuti posisi internal bucket.
cpp 
namespace std {
    template<> struct hash<Point> {
        std::size_t operator()(const Point& p) const noexcept {
            std::size_t h1 = std::hash<int>{}(p.x);
            std::size_t h2 = std::hash<int>{}(p.y);
            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
        }
    };
}
// Sekarang std::unordered_map<Point, V> bekerja tanpa argumen hash eksplisit.

unordered_map vs std::map #

Tabel perbandingan membantu kita memilih:

Aspekstd::unordered_mapstd::map
ImplementasiHash table + chainingBST merah-hitam
Lookup rata-rataO(1)O(log n)
Lookup worst caseO(n)O(log n)
Insert rata-rataO(1)O(log n)
Iterasi terurutTidakYa (in-order)
Lower/upper boundTidak adaAda
Memory overheadTinggi (bucket)Sedang (pointer per node)
Sensitif terhadap hash lemahYaTidak

Performa: Praktik versus Teori #

Worst case O(n) terjadi ketika semua key terpetakan ke bucket yang sama. STL std::unordered_map tidak melindungi dari ini secara default. Bila kita memakai std::unordered_map<int, V> dan key di-set ke 0, 7, 14, 21, ... (kelipatan bucket_count default), semua entry tumpuk di satu bucket.

Mitigasi #

  • Pilih hash function yang seragam untuk distribusi key yang diketahui.
  • Atur max_load_factor(0.5) untuk memaksa rehash lebih awal — mengurangi panjang rantai.
  • Reserve upfront: um.reserve(n) memanggil rehash agar bucket_count cukup untuk n entry tanpa intermediate rehash.
  • Profile: bila lookup lambat, gunakan bucket_count() dan bucket_size(i) untuk inspeksi distribusi.

Ringkasan #

  • std::unordered_map<K, V> dan std::unordered_set<T> adalah hash container STL dengan kompleksitas rata-rata O(1).
  • API utama: operator[], at(), find(), insert/emplace, erase(), count(), contains() (C++20).
  • operator[] insert default bila key tidak ada; at() throws; find() tidak mengubah map.
  • Untuk tipe custom, sediakan hash function (callable size_t operator()(T)) dan equality predicate (default operator==).
  • Idiom hash_combine dengan konstanta emas 0x9e3779b9 menjadi standar untuk menggabung hash beberapa field.
  • Pilih unordered_map untuk lookup cepat tanpa urutan; map untuk iterasi terurut, range query, atau ketika hash function lemah.