Kompleksitas Hashing

Hash table sering diiklankan sebagai struktur data dengan operasi O(1). Klaim ini benar secara rata-rata (average case) tetapi menyembunyikan dua jebakan: worst case dapat mencapai O(n), dan operasi sesekali (rehash) dapat menyentuh O(n) sekaligus. Pada Chapter ini kita akan menganalisis kompleksitas hashing secara formal, memahami bagaimana load factor α memengaruhi panjang rantai dan jumlah probe, serta bagaimana analisis amortisasi membenarkan klaim O(1) per operasi meski ada rehashing. Pemahaman ini krusial untuk memilih struktur data yang tepat dalam praktik.

Average Case: O(1 + α) untuk Chaining #

Mekanisme: Simple Uniform Hashing #

Asumsi simple uniform hashing: setiap key memiliki peluang sama untuk dipetakan ke setiap bucket, secara independen. Dengan asumsi ini, panjang rantai rata-rata pada separate chaining adalah α = n/m.

Kompleksitas operasi:

Insert (push_back ke rantai): O(1) tanpa perlu traversal (bila kita tidak cek duplikasi).
Insert with duplicate check: O(1 + α) — linear search di rantai.
Find: O(1 + α) — rata-rata setengah rantai diperiksa.
Erase: O(1 + α) — sama seperti find.

Selama α konstan (mis. α ≤ 1), semua operasi adalah O(1).

Verifikasi Numerik #

Mari kita ukur jumlah langkah rata-rata untuk find pada hash table dengan α bervariasi:

cpp
#include <iostream>
#include <vector>
#include <list>
#include <random>

class ChainingHT {
public:
    std::vector<std::list<int>> buckets;
    std::size_t probes_total = 0;
    std::size_t find_count = 0;

    explicit ChainingHT(std::size_t m) : buckets(m) {}

    void insert(int k) {
        std::size_t idx = std::hash<int>{}(k) % buckets.size();
        for (int x : buckets[idx]) if (x == k) return;
        buckets[idx].push_back(k);
    }

    bool find(int k) {
        std::size_t idx = std::hash<int>{}(k) % buckets.size();
        std::size_t probes = 0;
        for (int x : buckets[idx]) {
            ++probes;
            if (x == k) {
                probes_total += probes;
                ++find_count;
                return true;
            }
        }
        probes_total += probes;
        ++find_count;
        return false;
    }

    float avg_probes() const {
        return find_count ? static_cast<float>(probes_total) / find_count : 0.0f;
    }
};

int main() {
    const std::size_t n = 1000;

    for (std::size_t m : {2000, 1000, 500, 200}) {
        ChainingHT ht(m);
        // Seed rng di DALAM loop agar rng2 dapat mereproduksi sequence
        std::mt19937 rng(42);
        for (std::size_t i = 0; i < n; ++i) {
            ht.insert(static_cast<int>(rng()));
        }
        // rng2 dengan seed sama -> menghasilkan key yang sama
        std::mt19937 rng2(42);
        for (std::size_t i = 0; i < n; ++i) {
            int k = static_cast<int>(rng2());
            if (i % 2 == 0) ht.find(k);   // cari key yang ada
        }
        float alpha = static_cast<float>(n) / m;
        std::cout << "m=" << m << " alpha=" << alpha
                  << " avg_probes=" << ht.avg_probes() << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
m=2000 alpha=0.5 avg_probes=1.224
m=1000 alpha=1 avg_probes=1.498
m=500 alpha=2 avg_probes=2
m=200 alpha=5 avg_probes=3.458

Baris std::vector<std::list<int>> buckets;: bucket sebagai linked list, sama seperti implementasi separate chaining sebelumnya.
Baris std::size_t probes_total = 0; std::size_t find_count = 0;: instrumentasi untuk menghitung jumlah langkah rata-rata.
Baris for (int x : buckets[idx]) { ++probes; ... }: setiap iterasi loop dihitung sebagai satu probe. Untuk find yang berhasil, jumlah probe = posisi key di rantai (1-indexed).
Baris std::mt19937 rng(42); di dalam for-m loop: penting agar rng2 (yang juga di-seed dengan 42) mereproduksi urutan key yang sama dengan yang di-insert. Tanpa ini, find akan mencari key yang tidak ada di tabel.
Baris for (std::size_t m : {2000, 1000, 500, 200}): uji empat konfigurasi α = 0.5, 1, 2, 5.
Hasil alpha=0.5, avg_probes=1.224: rata-rata 1.22 probe, sedikit di atas 1 (yang diharapkan: 1 + α/2 = 1.25). Cocok dengan teori.
Hasil alpha=5, avg_probes=3.458: dengan rantai panjang rata-rata 5, find berhasil membutuhkan ~3.46 probe. Teori: 1 + α/2 = 3.5, sangat dekat.
Insight: rata-rata probe ≈ 1 + α/2 untuk find berhasil (karena rata-rata posisi key di rantai adalah (panjang rantai + 1)/2). Untuk find gagal, probe = α (panjang rantai penuh).

Open Addressing: Rumus Knuth #

Untuk open addressing dengan linear probing, kompleksitas tidak se-simple O(1+α). Knuth (1973) menurunkan rumus berikut untuk jumlah probe rata-rata:

Operasi	Successful find	Unsuccessful find
Linear probing	`(1/2)(1 + 1/(1-α))`	`(1/2)(1 + 1/(1-α)²)`
Double hashing	`-(1/α) · ln(1-α)`	`1/(1-α)`

Mari kita verifikasi tabel numerik untuk berbagai α:

cpp
#include <iostream>
#include <iomanip>
#include <cmath>

double lin_succ(double a) { return 0.5 * (1 + 1.0/(1.0 - a)); }
double lin_fail(double a)  { return 0.5 * (1 + 1.0/((1.0 - a)*(1.0 - a))); }
double dh_succ(double a)   { return -std::log(1.0 - a) / a; }
double dh_fail(double a)   { return 1.0 / (1.0 - a); }

int main() {
    std::cout << std::fixed << std::setprecision(4);
    std::cout << "alpha  lin_succ  lin_fail  dh_succ  dh_fail\n";
    std::cout << "-----  --------  --------  -------  -------\n";
    for (double a : {0.1, 0.25, 0.5, 0.7, 0.75, 0.9, 0.99}) {
        std::cout << std::setw(5) << a << "  "
                  << std::setw(8) << lin_succ(a) << "  "
                  << std::setw(8) << lin_fail(a) << "  "
                  << std::setw(7) << dh_succ(a) << "  "
                  << std::setw(7) << dh_fail(a) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
alpha  lin_succ  lin_fail  dh_succ  dh_fail
-----  --------  --------  -------  -------
1000   1.0556   1.1173   1.0536   1.1111
2500   1.1667   1.3889   1.1507   1.3333
5000   1.5000   2.5000   1.3863   2.0000
7000   2.1667   6.0556   1.7200   3.3333
7500   2.5000  8.5000   1.8484   4.0000
9000   5.5000  50.5000   2.5584  10.0000
9900  50.5000 5000.5000   4.6517  100.0000

Baris lin_succ(double a) { return 0.5 * (1 + 1.0/(1.0 - a)); }: rumus Knuth untuk successful find pada linear probing. Saat α mendekati 1, nilai meledak.
Baris dh_succ(double a) { return -std::log(1.0 - a) / a; }: rumus double hashing — tumbuh lebih lambat (logaritmik) dibanding linear.
Hasil α=0.5, lin_fail=2.5: unsuccessful find membutuhkan 2.5 probe rata-rata — bandingkan dengan chaining yang hanya butuh α = 0.5 probe.
Hasil α=0.99, lin_fail=5000: kenaikan dramatis. Inilah mengapa open addressing wajib rehash sebelum α mendekati 1.
Insight: double hashing secara konsisten lebih baik daripada linear probing untuk α tinggi, tetapi keduanya tetap sensitif. Standar industri menjaga α ≤ 0.75 untuk open addressing.

Worst Case: O(n) #

Skenario yang Menghasilkan Worst Case #

Worst case O(n) terjadi ketika semua key terpetakan ke bucket yang sama. Penyebab umum:

Hash function lemah: mis. h(k) = k mod 8 untuk key yang selalu kelipatan 8.
Adversarial input: penyerang sengaja memilih key yang collide (DDoS algoritma hash web — CVE-2011-5034 di PHP/Java).
Birthday paradox: bahkan dengan hash function baik, collision signifikan muncul setelah sqrt(m) insert acak.

Pada chaining, semua n entry tumpuk di satu bucket → find = O(n). Pada open addressing, probe sequence harus menjelajah seluruh tabel → find = O(n).

Mekanisme: Pertahanan STL #

STL std::unordered_map tidak otomatis melindungi dari adversarial input. Sejak C++14, beberapa implementasi (libstdc++ dengan _GLIBCXX_DEBUG) menyediakan perlindungan via perubahan seed hash acak per proses, tetapi ini tidak dijamin standar.

Rehashing dan Analisis Amortisasi #

Mekanisme: Doubling Strategy #

Ketika load factor melampaui ambang (mis. 0.75 untuk open addressing, 1.0 untuk chaining), hash table melakukan rehash:

Alokasi array baru dengan ukuran 2m + 1 (umumnya ganjil agar mendekati prima).
Hitung ulang h(k) untuk setiap entry dengan modulus baru.
Pindahkan setiap entry ke bucket baru.

Biaya satu rehash adalah O(n). Tapi seberapa sering rehash terjadi?

Analisis Amortisasi #

Misalkan kita start dengan m = 1 dan insert n elemen, dengan rehash setiap kali α melewati 1. Rehash terjadi pada saat:

n = 1 → rehash ke m = 3 (biaya 1)
n = 3 → rehash ke m = 7 (biaya 3)
n = 7 → rehash ke m = 15 (biaya 7)
n = 15 → rehash ke m = 31 (biaya 15)
…
n = 2^k - 1 → rehash ke m = 2^(k+1) - 1 (biaya 2^k - 1)

Total biaya rehash untuk n insert = 1 + 3 + 7 + 15 + ... + (n-1)/2 = O(n). Karena ada n insert, biaya amortisasi per insert = O(n)/n = O(1). Inilah esensi aggregate method dalam analisis amortisasi (lihat Chapter Kompleksitas Amortisasi).

Verifikasi Numerik: Amortisasi #

cpp
#include <iostream>
#include <vector>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> um;
    std::size_t rehash_count = 0;
    std::size_t last_buckets = um.bucket_count();

    for (int i = 0; i < 10000; ++i) {
        um[i] = i;
        if (um.bucket_count() != last_buckets) {
            ++rehash_count;
            last_buckets = um.bucket_count();
        }
    }

    std::cout << "Setelah 10000 insert:\n";
    std::cout << "  size = " << um.size() << '\n';
    std::cout << "  bucket_count = " << um.bucket_count() << '\n';
    std::cout << "  rehash terjadi = " << rehash_count << " kali\n";
    std::cout << "  load_factor akhir = " << um.load_factor() << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Setelah 10000 insert:
  size = 10000
  bucket_count = 10273
  rehash terjadi = 10 kali
  load_factor akhir = 0.973426

Baris if (um.bucket_count() != last_buckets) { ++rehash_count; ... }: deteksi rehash dengan membandingkan jumlah bucket sebelum dan sesudah insert.
Hasil rehash terjadi = 10 kali: untuk 10000 insert, hanya 10 rehash. Biaya total ≈ jumlah doubling 1+3+7+…+5000 ≈ 10000 operasi — sama dengan n. Inilah biaya amortisasi O(1).
Hasil bucket_count = 10273: implementasi libstdc++ memilih prima terdekat di atas n / max_load_factor = 10000 / 1 = 10000, yaitu 10273 (prima).
Hasil load_factor = 0.973: tepat di bawah ambang default max_load_factor = 1. Rehash berikutnya akan dipicu bila satu insert lagi terjadi.
Insight: walau sekali rehash O(n), frekuensinya berkurang secara geometri sehingga total tetap linier terhadap n.

Perbandingan dengan Struktur Data Lain #

Struktur	Build	Find avg	Find worst	Insert avg	Memori	Iterasi terurut
Hash table (chaining)	O(n)	O(1)	O(n)	O(1)	O(n) + overhead	Tidak
Hash table (open addr.)	O(n)	O(1)	O(n)	O(1)	O(m)	Tidak
BST (self-balancing)	O(n log n)	O(log n)	O(log n)	O(log n)	O(n)	Ya
Sorted array	O(n log n)	O(log n)	O(log n)	O(n)	O(n)	Ya
Trie (string key)	O(total len)	O(len)	O(len)	O(len)	O(total len)	Leksikografis

Ringkasan #

Kompleksitas rata-rata hash table adalah O(1 + α) untuk chaining dan O(1/(1-α)) untuk open addressing.
Knuth menurunkan rumus eksplisit: linear probing 0.5(1 + 1/(1-α)²) untuk unsuccessful find, double hashing 1/(1-α).
Worst case O(n) terjadi pada hash function lemah atau adversarial input. STL tidak otomatis melindungi; gunakan hash ber-seed acak untuk input tidak terpercaya.
Rehashing biaya O(n) tetapi amortisasi O(1) per operasi karena frekuensi rehash berkurang secara geometri.
Pemilihan strategi bergantung karakteristik data: chaining toleran α tinggi, open addressing cache-friendly tetapi sensitif.
Bandingkan dengan BST/sorted array: hash table cepat tetapi tidak mendukung iterasi terurut atau range query.