Konsep Hashing

Sebuah array memberi kita akses langsung ke elemen lewat indeks: a[7] selesai dalam satu langkah. Namun indeks array harus berupa bilangan bulat kecil yang berurutan, sedangkan di dunia nyata kita sering mencari data berdasarkan key yang berbentuk string (“Andi”), NIM (“13519001”), atau bahkan pasangan nilai. Struktur data sebelumnya menyelesaikan ini dengan trade-off: array statis butuh indeks numerik, BST memberi O(log n) tapi dengan perbandingan beruntun. Hashing menawarkan jalan tengah yang menarik — memetakan key sembarang ke indeks array lewat sebuah fungsi, sehingga lookup rata-rata mencapai O(1). Pada Chapter ini kita akan memahami konsep dasar hash table, perbandingannya dengan struktur lain, dan mengapa collision adalah konsekuensi matematis yang tak terhindarkan.

Motivasi: Lookup Berdasarkan Key #

Mekanisme: Pemetaan Key ke Indeks #

Diberikan sebuah himpunan key (mis. nama mahasiswa) dan value terkait (mis. nilai), kita ingin operasi:

• insert(key, value) — simpan pasangan key-value.
• find(key) — kembalikan value untuk key tertentu.
• erase(key) — hapus pasangan key-value.

Tiga pendekatan klasik beserta kompleksitas waktunya:

Hash table mencapai O(1) rata-rata dengan jalan pintas: alih-alih membandingkan key satu per satu, kita menghitung sebuah hash value h(k) yang langsung menentukan indeks bucket tempat data disimpan.

Bila tidak ada collision (dua key berbeda menghasilkan indeks yang sama), find cukup menghitung h(k) lalu mengakses bucket[h(k)] — dua langkah konstan, terlepas dari jumlah elemen.

Komponen Hash Table #

Sebuah hash table terdiri dari tiga komponen inti:

1. Array of buckets — wadah penyimpanan dengan ukuran m. Biasanya m dipilih agar relatif prima terhadap pola data.
2. Hash function h(k) — fungsi yang memetakan key k ke bilangan bulat dalam rentang [0, m-1].
3. Collision resolution — strategi menangani kasus ketika dua key berbeda menghasilkan indeks bucket yang sama.

+----------+      +------------------+      +------------------+
| key k    | ---> | h(k) = k mod m   | ---> | bucket[h(k)]     |
+----------+      +------------------+      +------------------+

Aturan Dasar Hash Function #

Sebuah hash function h wajib memenuhi:

• Deterministik: h(k) selalu menghasilkan nilai yang sama untuk k yang sama, selama ukuran tabel m tidak berubah.
• Berada dalam rentang: 0 <= h(k) < m.
• Cepat: kompleksitas O(1) atau paling tidak O(panjang key).
• Distribusi seragam: untuk key acak, setiap bucket memiliki peluang kira-kira sama untuk dipilih.

Demonstrasi: Hash Table Sederhana #

Sebelum membahas collision di chapter berikutnya, mari kita lihat hash table sederhana yang menampung integer key dengan hash function h(k) = k mod m.

Kode: Hash Table dengan Division Method #

#include <iostream>
#include <vector>
#include <optional>
#include <string>

class HashTableInt {
    std::vector<std::optional<int>> table_;
    std::size_t m_;
public:
    explicit HashTableInt(std::size_t m) : table_(m), m_(m) {}

    std::size_t hash(int key) const {
        return static_cast<std::size_t>(key) % m_;
    }

    bool insert(int key) {
        std::size_t idx = hash(key);
        if (table_[idx].has_value()) return false; // bucket terisi
        table_[idx] = key;
        return true;
    }

    bool contains(int key) const {
        return table_[hash(key)].has_value()
            && *table_[hash(key)] == key;
    }
};

int main() {
    HashTableInt ht(7);              // m = 7 (bilangan prima)
    int keys[] = {10, 22, 31, 4, 15, 28};

    std::cout << "Insert & posisi bucket:\n";
    for (int k : keys) {
        bool ok = ht.insert(k);
        std::cout << "  insert " << k
                  << " -> bucket " << (k % 7)
                  << (ok ? " (sukses)\n" : " (COLLISION)\n");
    }

    std::cout << "\nLookup:\n";
    for (int k : {22, 31, 99}) {
        std::cout << "  contains " << k << " -> "
                  << (ht.contains(k) ? "YA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Insert & posisi bucket:
  insert 10 -> bucket 3 (sukses)
  insert 22 -> bucket 1 (sukses)
  insert 31 -> bucket 3 (COLLISION)
  insert 4 -> bucket 4 (sukses)
  insert 15 -> bucket 1 (COLLISION)
  insert 28 -> bucket 0 (sukses)

Lookup:
  contains 22 -> YA
  contains 31 -> TIDAK
  contains 99 -> TIDAK

1. Baris std::vector<std::optional<int>> table_: setiap bucket memakai std::optional<int> untuk membedakan bucket kosong dari bucket yang berisi nilai 0. Ini representasi paling sederhana — belum ada collision resolution.
2. Baris hash(int key) { return key % m_; }: division method — paling sederhana. Kita pilih m = 7 karena prima, mengurangi pola simetri pada data bertipe umum.
3. Baris if (table_[idx].has_value()) return false;: implementasi naif yang menolak insert jika bucket terisi. Inilah mengapa insert 31 dan insert 15 gagal — key 31 berakhir di bucket 3 yang sudah ditempati 10, key 15 berakhir di bucket 1 yang sudah ditempati 22.
4. Baris return table_[hash(key)].has_value() && *table_[hash(key)] == key;: cek apakah bucket terisi dan nilainya cocok. Karena 31 tidak pernah berhasil di-insert, contains 31 mengembalikan TIDAK meskipun bucket-3 berisi nilai (yaitu 10).

Pigeonhole Principle dan Collision #

Mengapa collision selalu terjadi? Jawabannya adalah pigeonhole principle: jika ruang key lebih besar dari jumlah bucket, dua key berbeda pasti terpetakan ke bucket yang sama.

Ruang key    : semua integer (tak terhingga)
Jumlah bucket: m (terbatas, mis. 7)
=> Pasti ada key berbeda k1 != k2 dengan h(k1) == h(k2)

Contoh konkret pada kode di atas: 10 % 7 = 3 dan 31 % 7 = 3. Kedua key berbeda menghasilkan indeks yang sama.

Bahkan dengan birthday paradox, collision muncul lebih cepat dari yang kita kira. Pada hash table dengan m = 365 bucket, peluang collision melampaui 50% setelah hanya ~23 insert acak. Inilah mengapa setiap hash table praktis wajib memiliki strategi collision resolution, yang akan kita bahas tuntas di Chapter Collision Resolution, Separate Chaining, dan Open Addressing.

Perbandingan dengan BST dan Sorted Array #

Hash table bukanlah jawaban untuk semua masalah. Tabel berikut merangkum trade-off masing-masing struktur:

(*) BST tidak self-balancing dapat terdegradasi. (**) Self-balancing BST (AVL, Red-Black) menjamin O(log n).

Ringkasan #

• Hash table memetakan key ke indeks bucket via hash function, memberi lookup rata-rata O(1).
• Tiga komponen inti: array of buckets, hash function, dan strategi collision resolution.
• Collision adalah konsekuensi matematis dari pigeonhole principle — tak terhindarkan.
• Pemilihan m prima dan hash function dengan distribusi seragam meminimalkan collision tetapi tidak menghapusnya.
• Hash table unggul untuk lookup murni, sementara BST unggul untuk operasi yang butuh urutan.