Hashing bukan sekadar struktur data — ia adalah paradigma pemecahan masalah. Banyak algoritma yang berjalan O(n²) secara naif dapat diturunkan ke O(n) dengan hash table sebagai pondasi. Pada Chapter ini kita akan mempelajari lima penerapan klasik hashing: frequency counting, deduplikasi, two-sum problem, building block cache (LRU), dan substring hashing sebagai pengantar Rabin-Karp. Setiap penerapan disertai implementasi C++ yang siap pakai, sehingga kita memiliki pola siap pakai ketika menghadapi masalah serupa di kompetisi atau pekerjaan nyata.

Frequency Counting #

Masalah #

Diberikan array a, hitung berapa kali setiap elemen muncul. Tanpa hash table, kita bisa sorting lalu group (O(n log n)). Dengan hash table, satu pass O(n) cukup.

Mekanisme: Hash Map sebagai Akumulator #

Loop setiap elemen, increment counter di hash map. Key adalah elemen, value adalah jumlah kemunculan.

Kode: Frequency Map #

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

std::unordered_map<std::string, int>
hitung_frekuensi(const std::vector<std::string>& kata) {
    std::unordered_map<std::string, int> freq;
    for (const auto& w : kata) {
        ++freq[w];      // insert 0 bila belum ada, lalu increment
    }
    return freq;
}

int main() {
    std::vector<std::string> teks = {
        "kucing", "anjing", "kucing", "burung",
        "kucing", "anjing", "ikan"
    };

    auto freq = hitung_frekuensi(teks);

    std::cout << "Frekuensi kata:\n";
    for (const auto& [k, v] : freq) {
        std::cout << "  " << k << " -> " << v << '\n';
    }

    // Cari kata paling sering
    std::string mode;
    int max_count = 0;
    for (const auto& [k, v] : freq) {
        if (v > max_count) { max_count = v; mode = k; }
    }
    std::cout << "\nKata paling sering: " << mode
              << " (" << max_count << "x)\n";
    return 0;
}

Output yang Dihasilkan:

text 
Frekuensi kata:
  ikan -> 1
  burung -> 1
  anjing -> 2
  kucing -> 3

Kata paling sering: kucing (3x)
  1. Baris for (const auto& w : kata) { ++freq[w]; }: operator[] insert entry baru dengan default value 0 bila key belum ada, lalu mengembalikan reference ke value. ++ meng-increment langsung — idiom singkat untuk frequency counting.
  2. Baris for (const auto& [k, v] : freq): structured binding untuk iterasi pasangan key-value. Urutan tidak terurut.
  3. Kompleksitas: O(n) rata-rata untuk n elemen, jauh lebih cepat daripada sorting-based O(n log n) untuk dataset besar.

Deduplikasi #

Masalah #

Hapus elemen duplikat dari koleksi, pertahankan urutan pertama kemunculan.

Kode: Deduplikasi Memakai unordered_set #

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

std::vector<int> dedup_keep_order(const std::vector<int>& a) {
    std::vector<int> result;
    std::unordered_set<int> seen;
    for (int x : a) {
        if (seen.insert(x).second) {   // insert berhasil = key baru
            result.push_back(x);
        }
    }
    return result;
}

int main() {
    std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    auto unik = dedup_keep_order(a);

    std::cout << "Input:  ";
    for (int x : a) std::cout << x << ' ';
    std::cout << "\nUnik:   ";
    for (int x : unik) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Input:  3 1 4 1 5 9 2 6 5 3 5
Unik:   3 1 4 5 9 2 6
  1. Baris if (seen.insert(x).second): insert mengembalikan pair<iterator, bool>. Bool true berarti elemen baru saja dimasukkan (key belum ada), false berarti duplikat. Pola idiomatik untuk “jika belum ada”.
  2. Baris result.push_back(x);: hanya tambahkan ke result bila key baru. Urutan tetap mengikuti kemunculan pertama di input.
  3. Kompleksitas: O(n) rata-rata untuk n elemen, dengan tradeoff memori O(unique) untuk set.

Two-Sum Problem #

Masalah #

Diberikan array a dan target T, cari pasangan (a[i], a[j]) dengan i != j sehingga a[i] + a[j] = T. Implementasi naif O(n²); hash table menurunkan ke O(n).

Mekanisme: Hash Set sebagai Lookup Cepat #

Loop setiap elemen x. Kita ingin tahu apakah T - x sudah muncul sebelumnya. Bila ya, pasangan ditemukan. Simpan semua elemen yang sudah dilihat ke hash set.

Kode: Two-Sum O(n) #

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

std::optional<std::pair<int, int>>
two_sum(const std::vector<int>& a, int T) {
    std::unordered_set<int> seen;
    for (int x : a) {
        int complement = T - x;
        auto it = seen.find(complement);
        if (it != seen.end()) {
            return std::make_pair(complement, x);
        }
        seen.insert(x);
    }
    return std::nullopt;
}

int main() {
    std::vector<int> a = {2, 7, 11, 15, 1, 8};

    for (int T : {9, 10, 25, 100}) {
        auto result = two_sum(a, T);
        if (result) {
            std::cout << "T=" << T << ": "
                      << result->first << " + " << result->second
                      << " = " << T << '\n';
        } else {
            std::cout << "T=" << T << ": tidak ada pasangan\n";
        }
    }
    return 0;
}

Output yang Dihasilkan:

text 
T=9: 2 + 7 = 9
T=10: 2 + 8 = 10
T=25: tidak ada pasangan
T=100: tidak ada pasangan
  1. Baris int complement = T - x;: hitung komplemen — nilai yang dibutuhkan agar x + complement = T.
  2. Baris auto it = seen.find(complement);: cek apakah komplemen sudah pernah muncul. Bila ya, kita menemukan pasangan (complement, x) dengan komplemen muncul lebih awal.
  3. Baris seen.insert(x);: setelah pengecekan, masukkan x ke set agar bisa dipakai sebagai komplemen untuk elemen-elemen setelahnya.
  4. Mengapa find sebelum insert: bila kita insert dulu, find(T-x) mungkin menemukan x itu sendiri (bila x == T-x, mis. T=2x). Pola find-then-insert menghindari bug ini.
  5. Verifikasi T=25: tidak ada pasangan dalam {2,7,11,15,1,8} yang berjumlah 25 (cek: 15+10? 10 tidak ada; 11+14? 14 tidak ada; dst). Algoritma dengan benar mengembalikan std::nullopt.
  6. Kompleksitas: O(n) rata-rata untuk n elemen, dengan O(n) memori untuk set.

Cache: Building Block LRU #

Masalah #

Implementasi cache LRU (Least Recently Used): ketika cache penuh dan elemen baru ditambahkan, evict elemen yang paling lama tidak diakses. Hash table + doubly-linked list adalah pondasi klasik.

Mekanisme: Hash Table + Doubly-Linked List #

  • Hash table memetakan key → node list. Memberi O(1) lookup.
  • Doubly-linked list menjaga urutan akses (MRU di head, LRU di tail). Memindahkan node ke head = O(1) dengan pointer hash table.
  • get(k): hash table lookup, pindah node ke head, return value.
  • put(k, v): bila ada, update value + pindah ke head. Bila tidak ada, insert baru di head; bila over capacity, evict tail.

Kode: LRU Cache Sederhana #

cpp 
#include <iostream>
#include <list>
#include <unordered_map>

class LRUCache {
    int capacity_;
    std::list<std::pair<int, int>> list_;   // (key, value), MRU di front
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> map_;
public:
    explicit LRUCache(int cap) : capacity_(cap) {}

    int get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) return -1;
        // Pindah ke front (most recently used)
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        if (static_cast<int>(list_.size()) >= capacity_) {
            // Evict LRU (back)
            auto lru = list_.back();
            map_.erase(lru.first);
            list_.pop_back();
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }

    void dump() const {
        std::cout << "cache (MRU->LRU): ";
        for (const auto& [k, v] : list_) {
            std::cout << "[" << k << ":" << v << "] ";
        }
        std::cout << '\n';
    }
};

int main() {
    LRUCache cache(3);
    cache.put(1, 10);
    cache.put(2, 20);
    cache.put(3, 30);
    cache.dump();

    std::cout << "get(1) = " << cache.get(1) << '\n';  // 10, pindah 1 ke MRU
    cache.dump();

    cache.put(4, 40);    // evict LRU (yaitu 2)
    cache.dump();

    std::cout << "get(2) = " << cache.get(2) << '\n';   // -1, sudah evicted
    std::cout << "get(3) = " << cache.get(3) << '\n';   // 30
    return 0;
}

Output yang Dihasilkan:

text 
cache (MRU->LRU): [3:30] [2:20] [1:10]
get(1) = 10
cache (MRU->LRU): [1:10] [3:30] [2:20]
cache (MRU->LRU): [4:40] [1:10] [3:30]
get(2) = -1
get(3) = 30
  1. Baris std::list<std::pair<int, int>> list_;: doubly-linked list STL yang menyimpan pasangan (key, value). Front = MRU, back = LRU.
  2. Baris std::unordered_map<int, std::list<...>::iterator> map_;: hash table memetakan key → iterator ke node di list. Iterator std::list tetap valid setelah splice.
  3. Baris list_.splice(list_.begin(), list_, it->second);: splice memindahkan node dari posisi iterator ke posisi baru (di sini: front). Operasi O(1) — tidak ada copy data, hanya manipulasi pointer.
  4. Baris auto lru = list_.back();: LRU adalah elemen di back list. Simpan dulu sebelum pop untuk hapus key dari map.
  5. Hasil get(1) = 10, [1:10] pindah ke front: akses 1 membuatnya MRU. Urutan berubah dari [3,2,1] menjadi [1,3,2].
  6. Hasil put(4, 40) evict [2:20]: kapasitas 3, setelah insert 4 menjadi 4 elemen — pop back [2:20] dan hapus dari map. Hasil: [4,1,3].
  7. Hasil get(2) = -1: key 2 sudah evicted, kembalikan -1 (sentinel “tidak ada”).
  8. Kompleksitas: get dan put keduanya O(1) rata-rata. Inilah kekuatan kombinasi hash table + linked list.

Substring Hashing: Preview Rabin-Karp #

Masalah #

Cari pattern P di text T ( substring matching). Naif: O(|T|·|P|). Hashing: O(|T|+|P|) rata-rata.

Mekanisme: Rolling Hash #

Hitung hash dari setiap substring T[i..i+|P|-1]. Bandingkan dengan hash pattern. Bila hash cocok, verifikasi karakter-per-karakter (untuk hindari collision). Trik rolling: hash dari T[i+1..i+|P|] dapat dihitung dari hash T[i..i+|P|-1] dalam O(1):

text 
h(T[i+1..i+|P|]) = (B * (h(T[i..i+|P|-1]) - T[i] * B^(|P|-1)) + T[i+|P|]) mod m

Kode: Rabin-Karp Sederhana #

cpp 
#include <iostream>
#include <string>
#include <vector>

std::vector<std::size_t> rabin_karp(const std::string& T,
                                     const std::string& P) {
    const std::uint64_t M = 1'000'000'007ULL;
    const std::uint64_t B = 256ULL;

    std::vector<std::size_t> result;
    if (P.empty() || P.size() > T.size()) return result;

    // Hitung hash pattern dan hash window pertama text
    std::uint64_t hp = 0, ht = 0, pow = 1;
    for (std::size_t i = 0; i < P.size(); ++i) {
        hp = (hp * B + static_cast<unsigned char>(P[i])) % M;
        ht = (ht * B + static_cast<unsigned char>(T[i])) % M;
        if (i + 1 < P.size()) pow = (pow * B) % M;
    }

    for (std::size_t i = 0; i + P.size() <= T.size(); ++i) {
        if (hp == ht) {
            // Verifikasi karakter-per-karakter untuk hindari collision
            if (T.compare(i, P.size(), P) == 0) {
                result.push_back(i);
            }
        }
        // Rolling hash untuk window berikutnya
        if (i + P.size() < T.size()) {
            std::uint64_t keluar = (static_cast<unsigned char>(T[i]) * pow) % M;
            ht = (ht + M - keluar) % M;     // hapus char lama
            ht = (ht * B + static_cast<unsigned char>(T[i + P.size()])) % M;
        }
    }
    return result;
}

int main() {
    std::string T = "ABABDABACDABABCABAB";
    std::string P = "ABAB";

    auto positions = rabin_karp(T, P);
    std::cout << "Text:    " << T << '\n';
    std::cout << "Pattern: " << P << '\n';
    std::cout << "Posisi (0-indexed): ";
    for (std::size_t pos : positions) {
        std::cout << pos << ' ';
    }
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Text:    ABABDABACDABABCABAB
Pattern: ABAB
Posisi (0-indexed): 0 10 15
  1. Baris hp = (hp * B + P[i]) % M;: polynomial rolling hash untuk pattern. Sama dengan implementasi di Chapter Hash Function.
  2. Baris pow = (pow * B) % M;: precompute B^(|P|-1) mod M — dipakai untuk menghapus karakter lama dari hash window.
  3. Baris if (hp == ht) { if (T.compare(...) == 0) {...} }: bila hash cocok, verifikasi langsung karakter-per-karakter. Langkah ini mencegah false positive akibat collision hash.
  4. Baris ht = (ht + M - keluar) % M;: hapus karakter lama. + M untuk menghindari negatif (operasi modulo tidak menghasilkan negatif di uint64_t, tetapi untuk pemahaman umum).
  5. Baris ht = (ht * B + T[i + |P|]) % M;: tambah karakter baru. Sekarang hash merefleksikan window [i+1 .. i+|P|].
  6. Hasil posisi 0, 10, 15: substring ABAB muncul di indeks 0, 10, dan 15 dalam text. Verifikasi visual: ABAB|DABACD|ABAB|CABAB — indeks 0, 10, 15 sesuai.
  7. Kompleksitas: O(|T| + |P|) rata-rata. Worst case O(|T|·|P|) bila banyak hash match palsu, tetapi sangat jarang dengan modulus prima besar.

Pola Umum Hashing #

Tabel ringkas pola penerapan hashing:

PolaStrukturKompleksitasContoh
Frequency countingunordered_map<K, int>O(n)Hitung kata
Deduplikasiunordered_set<T>O(n)Unik elemen
Two-sum lookupunordered_set<T>O(n)Pasangan = target
Cache LRUunordered_map + listO(1) per opBrowser cache
Substring matchingrolling hashO(n+m)Rabin-Karp
Disjoint set lookupunordered_map<K, int>O(1) averageUnion-find dengan hash
Memoization DPunordered_map<state, val>O(1) per stateTop-down DP

Ringkasan #

  • Frequency counting: increment counter di unordered_map, kompleksitas O(n).
  • Deduplikasi: unordered_set dengan pola insert(x).second untuk deteksi key baru.
  • Two-sum: hash set lookup komplemen T - x, kompleksitas O(n).
  • LRU cache: kombinasi unordered_map (key → list iterator) + std::list untuk urutan akses. splice memberi O(1) move.
  • Rabin-Karp: polynomial rolling hash dengan update O(1) per window; verifikasi karakter-per-karakter bila hash cocok.
  • Pola umum hashing: lookup O(1) memungkinkan algoritma O(n²) → O(n) untuk banyak masalah klasik.