Unordered Containers

Container std::unordered_set dan std::unordered_map (sejak C++11) menyimpan elemen berdasarkan hash function — bukan pohon terurut. Operasi find, insert, dan erase berjalan dalam O(1) rata-rata (O(n) worst-case saat semua key berbenturan ke satu bucket). Untuk DSA, container ini adalah pilihan default ketika kita tidak butuh iterasi terurut dan hanya memerlukan keanggotaan atau pasangan key-value. Pada Chapter ini kita akan membedah struktur internal hash table STL, mendemonstrasikan custom hash untuk tipe buatan sendiri, dan mengulas jebakan adversarial collision di kompetisi.

Dua Container Utama #

Versi unordered_multiset dan unordered_multimap juga ada — memperbolehkan duplikat key — tetapi lebih jarang dipakai untuk DSA.

Mekanisme: Hash Table Berbasis Bucket #

Setiap unordered_* secara internal adalah array of bucket. Operasi:

1. Hitung hash h = hash_fn(key).
2. Indeks bucket = h % bucket_count.
3. Dalam bucket (linked list), lakukan pencarian linier membandingkan key dengan elemen-elemen di bucket tersebut.

Bila load_factor (size / bucket_count) melewati max_load_factor() (default 1.0), container melakukan rehash — mengalokasikan array bucket baru yang lebih besar dan menyebarkan ulang seluruh elemen. Rehash bersifat O(n) tetapi amortisasi O(1) per insert.

Kode: Operasi Dasar dan Custom Hash #

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

// Custom hash untuk pair<int,int>
struct PairHash {
    std::size_t operator()(const std::pair<int,int>& p) const noexcept {
        // 31x + y — banyak digunakan di Java
        return static_cast<std::size_t>(p.first) * 31u
             + static_cast<std::size_t>(p.second);
    }
};

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

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        return std::hash<long long>()(static_cast<long long>(p.x) * 1000003LL + p.y);
    }
};

int main() {
    // 1) unordered_set<int>
    std::unordered_set<int> us = {5, 1, 3, 1, 4, 1, 2};
    std::cout << "unordered_set size=" << us.size() << '\n';
    std::cout << "bucket_count=" << us.bucket_count()
              << " load_factor=" << us.load_factor() << '\n';
    std::cout << "elements: ";
    for (int x : us) std::cout << x << ' ';  // urutan tidak terjamin
    std::cout << '\n';

    // Lookup O(1) rata-rata
    if (us.count(3)) std::cout << "3 ada di set\n";
    if (!us.count(99)) std::cout << "99 tidak ada\n";

    // 2) unordered_map<string,int>
    std::unordered_map<std::string, int> um;
    um["alice"] = 90;
    um["bob"] = 75;
    um["carol"] = 88;
    um["alice"] = 95;  // overwrite
    std::cout << "um[alice] = " << um["alice"] << '\n';
    std::cout << "size=" << um.size() << '\n';

    // 3) unordered_set<pair<int,int>> dengan custom hash
    std::unordered_set<std::pair<int,int>, PairHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});   // duplikat — diabaikan
    std::cout << "points size=" << points.size() << '\n';

    // 4) unordered_set<Point> dengan custom hash + operator==
    std::unordered_set<Point, PointHash> ps;
    ps.insert({5, 5});
    ps.insert({5, 5});  // duplikat
    ps.insert({1, 9});
    std::cout << "ps size=" << ps.size() << '\n';

    return 0;
}

Output yang Dihasilkan:

unordered_set size=5
bucket_count=13 load_factor=0.384615
elements: 2 4 3 1 5 
3 ada di set
99 tidak ada
um[alice] = 95
size=3
points size=2
ps size=2

Bedah Kode Baris-per-Baris #

1. std::unordered_set<int> us = {5, 1, 3, 1, 4, 1, 2}: tujuh elemen dalam initializer list, tiga 1 duplikat diabaikan. Hasil: us memuat {1,2,3,4,5} (lima elemen). Iterasi mencetak 2 4 3 1 5 — urutan tidak terjamin karena ditentukan oleh hash dan bucket.
2. us.bucket_count() dan us.load_factor(): STL memilih bucket_count = 13 (bilangan prima umum untuk default) untuk menampung lima elemen. load_factor = 5/13 ≈ 0.385 — masih jauh di bawah ambang 1.0 jadi belum rehash.
3. us.count(3): idiomatik untuk “apakah 3 ada?”. count pada unordered container rata-rata O(1) — tunggal lookup di bucket.
4. um["alice"] = 90; lalu um["alice"] = 95;: berbeda dengan std::map::insert, operator[] pada unordered_map melakukan overwrite bila key sudah ada. Akhirnya um["alice"] == 95.
5. struct PairHash: STL tidak menyediakan std::hash<std::pair<int,int>>. Untuk memakai pair sebagai key, kita harus menyediakan functor hash. Rumus 31 * x + y adalah kombinasi sederhana yang dipakai Java untuk String.hashCode().
6. points.insert({1, 2}) lalu points.insert({1, 2}) lagi: insert kedua menemukan elemen yang sama di bucket — diabaikan. size() tetap 2.
7. struct Point dengan operator==: unordered_set butuh dua hal — hash function dan equality comparison. Bila struct tidak menyediakan operator==, gunakan template parameter KeyEqual tambahan.
8. std::hash<long long>()(p.x * 1000003LL + p.y): idiomatik “flatten” 2D point menjadi satu integer 64-bit lalu pakai std::hash<long long> bawaan. Lebih aman daripada menulis hash manual.
9. Output ps size=2: walaupun kita insert({5,5}) dua kali, hanya satu yang disimpan — operator== mengenali duplikat.

Custom Hash: Pola Umum #

Untuk tipe buatan sendiri, dua bahan wajib: hash function dan equality. Tiga pola umum:

1. Flatten ke integer 64-bit, lalu std::hash<long long> — paling sederhana untuk tipe dengan beberapa field integer.
2. Combine hash field per field dengan hash_combine ala Boost:
   cpp Salin

   std::size_t h = std::hash<int>()(p.x);
   h ^= std::hash<int>()(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2);

3. Spesialisasi std::hash<T> sehingga tidak perlu menulis template parameter kedua:
   cpp Salin

   namespace std { template<> struct hash<Point> {
       std::size_t operator()(const Point& p) const noexcept { ... } }; }

Kapan unordered_* vs Container Associative #

Ringkasan #

• unordered_set/unordered_map: hash table berbasis bucket, rata-rata O(1) per operasi.
• Urutan iterasi tidak terjamin dan bisa berubah setelah rehash — jangan andalkan urutan untuk logika.
• Tipe buatan sendiri butuh dua bahan: hash function (functor operator()) dan equality (operator== atau parameter KeyEqual).
• Pola hash umum: flatten ke integer 64-bit lalu std::hash<long long>, atau combine field per field ala Boost.
• Untuk kompetisi, pertimbangkan custom randomized hash atau gp_hash_table dari __gnu_pbds untuk menghindari adversarial collision.