Semua struktur yang kita bangun sejauh ini menuntut kerja sebanding jumlah data saat mencari: linear search O(n), binary search O(log n), BST O(h). Hash table melanggar harga itu dengan prinsip berbeda — ia menghitung sendiri lokasi data dari kuncinya. Sebuah hash function mengubah kunci (misalnya string "mangga") menjadi indeks array, sehingga pencarian tidak menelusuri apa pun: hitung indeks, lompat, ambil. Pada kondisi ideal operasinya O(1), dan karena itu hash table adalah struktur data paling banyak dipakai dalam rekayasa perangkat lunak nyata. Chapter ini membangun hash table mini dengan teknik chaining, lengkap dengan collision, load factor, dan rehash.

Ide Hashing: Dari Kunci ke Indeks #

Jantung hash table adalah hash function: fungsi yang menerima kunci apa pun dan mengembalikan angka. Untuk string, formula klasik yang juga dipakai banyak library adalah polynomial rolling hash: mulai dari 0, lalu untuk setiap karakter hitung h = h * 31 + kode_karakter. Angka 31 dipilih karena ganjil, prima, dan perkaliannya murah (31*x == x*32 - x, sekali geser bit dan satu pengurangan). Hasilnya lalu diperkecil dengan modulo jumlah bucket agar jatuh di rentang indeks yang sah.

Syarat hash function yang baik: deterministik (kunci sama selalu hasil sama), menyebar merata (agar data tidak menumpuk di satu bucket), dan cepat dihitung. Tidak ada hash function yang menjamin dua kunci berbeda menghasilkan indeks berbeda — dan justru di situ muncul tantangan berikutnya.

Hash Table Mini dengan Chaining #

Collision terjadi ketika dua kunci berbeda mendarat di bucket yang sama. Teknik chaining menanganinya dengan sederhana: setiap bucket bukan satu data, melainkan rantai berisi semua pasangan yang indeksnya sama. Implementasi kita memakai vector<pair<string,int>> per bucket. Program berikut menyimpan stok buah lalu memeriksa sebarannya per bucket:

cpp 
// Hash table mini dengan chaining: vector<vector<pair<string,int>>>.
#include <iostream>
#include <string>
#include <utility>
#include <vector>

class HashTable {
public:
    explicit HashTable(int jumlahBucket) : bucket_(jumlahBucket) {}

    // Polynomial rolling hash sederhana: h = h * 31 + kode karakter
    static int hashString(const std::string& kunci, int jumlahBucket) {
        unsigned long h = 0;
        for (unsigned char c : kunci) {
            h = h * 31 + c;
        }
        return static_cast<int>(h % static_cast<unsigned long>(jumlahBucket));
    }

    int loadFactorPersen() const {
        return static_cast<int>(100 * ukuran_ / bucket_.size());
    }

    void put(const std::string& kunci, int nilai) {
        if (100 * ukuran_ > 75 * static_cast<int>(bucket_.size())) {
            rehash();  // load factor melewati 75 persen: gandakan bucket
        }
        int indeks = hashString(kunci, static_cast<int>(bucket_.size()));
        for (auto& pasangan : bucket_[indeks]) {
            if (pasangan.first == kunci) {
                pasangan.second = nilai;  // kunci sudah ada: perbarui nilai
                return;
            }
        }
        bucket_[indeks].push_back({kunci, nilai});
        ++ukuran_;
    }

    bool get(const std::string& kunci, int& hasil) const {
        int indeks = hashString(kunci, static_cast<int>(bucket_.size()));
        for (const auto& pasangan : bucket_[indeks]) {
            if (pasangan.first == kunci) {
                hasil = pasangan.second;
                return true;
            }
        }
        return false;
    }

    void tampilkanSebaran() const {
        for (int i = 0; i < static_cast<int>(bucket_.size()); ++i) {
            std::cout << "Bucket " << i << ": " << bucket_[i].size() << " item";
            for (const auto& p : bucket_[i]) {
                std::cout << " [" << p.first << "]";
            }
            std::cout << '\n';
        }
    }

private:
    void rehash() {
        auto lama = bucket_;
        bucket_.assign(lama.size() * 2, {});
        std::cout << "-- Rehash: " << lama.size() << " bucket menjadi "
                  << bucket_.size() << " bucket --\n";
        for (const auto& rantai : lama) {
            for (const auto& p : rantai) {
                int indeks =
                    hashString(p.first, static_cast<int>(bucket_.size()));
                bucket_[indeks].push_back(p);
            }
        }
    }

    std::vector<std::vector<std::pair<std::string, int>>> bucket_;
    int ukuran_ = 0;
};

int main() {
    HashTable stok(4);
    stok.put("apel", 7000);
    stok.put("jeruk", 5000);
    stok.put("mangga", 9000);
    stok.put("pisang", 4000);
    stok.put("durian", 25000);
    stok.put("rambutan", 12000);
    stok.put("salak", 8000);
    stok.put("nanas", 6500);

    stok.tampilkanSebaran();

    int harga = 0;
    if (stok.get("mangga", harga)) {
        std::cout << "Harga mangga : " << harga << '\n';
    }
    if (stok.get("pepaya", harga)) {
        std::cout << "Harga pepaya : " << harga << '\n';
    } else {
        std::cout << "pepaya tidak ada di tabel\n";
    }
    std::cout << "Load factor akhir: " << stok.loadFactorPersen()
              << " persen\n";
    return 0;
}

Output yang Dihasilkan:

text 
-- Rehash: 4 bucket menjadi 8 bucket --
-- Rehash: 8 bucket menjadi 16 bucket --
Bucket 0: 2 item [pisang] [rambutan]
Bucket 1: 0 item
Bucket 2: 0 item
Bucket 3: 0 item
Bucket 4: 0 item
Bucket 5: 1 item [durian]
Bucket 6: 1 item [apel]
Bucket 7: 1 item [mangga]
Bucket 8: 1 item [salak]
Bucket 9: 0 item
Bucket 10: 0 item
Bucket 11: 0 item
Bucket 12: 0 item
Bucket 13: 2 item [jeruk] [nanas]
Bucket 14: 0 item
Bucket 15: 0 item
Harga mangga : 9000
pepaya tidak ada di tabel
Load factor akhir: 50 persen

Bedah baris penting:

  1. Baris 12-18 (hashString): polynomial rolling hash — h dikali 31 lalu ditambah kode karakter untuk setiap huruf, ditutup modulo jumlah bucket. Kunci yang sama selalu menghasilkan indeks yang sama.
  2. Baris 24-38 (put): tiga langkah — periksa load factor (baris 25), telusuri rantai untuk memperbarui kunci yang sudah ada (baris 31), atau tambahkan pasangan baru di ekor rantai.
  3. Baris 39-48 (get): hitung indeks, telusuri rantai bucket itu saja; jika rantai pendek, pencarian terasa instan.
  4. Baris 61-71 (rehash): jumlah bucket digandakan, lalu semua item dimasukkan ulang — indeks lama tidak berlaku lagi karena modulo berubah.
  5. Baris 80-88: delapan put memicu dua rehash yang tercetak di awal output: 4 bucket menjadi 8, lalu 8 menjadi 16, persis ketika load factor melewati 75 persen.
  6. Baris 90-99: sebaran akhir menunjukkan collision nyata — bucket 0 memuat pisang dan rambutan, bucket 13 memuat jeruk dan nanas — sementara get("mangga") tetap menemukan 9000 dengan hanya memeriksa satu rantai.

Load Factor dan Kapan Resize #

Load factor adalah rasio ukuran / jumlah_bucket: rata-rata jumlah item per bucket. Inilah penentu kualitas pencarian — pada load factor 1 dengan penyebaran sempurna, tiap get hanya memeriksa sekitar satu item; pada load factor 10, satu get bisa menelusuri sepuluh pasangan. Karena itu hash table memantau angka ini dan melakukan rehash ketika melewati ambang (implementasi kita memakai 0,75, sama seperti std::unordered_map secara default).

Rehash berbiaya O(n) karena semua item dipindahkan, tetapi terjadi makin jarang seiring tabel membesar — pola biaya amortized yang sama seperti doubling pada dynamic array. Pemilihan ambang adalah kompromi: ambang rendah menghabiskan memori, ambang tinggi membuat rantai memanjang.

Padanan STL: std::unordered_map #

Semua yang kita bangun tersedia siap pakai sebagai std::unordered_map<std::string, int> dengan operator[], insert, find, dan erase dalam O(1) rata-rata. Satu perbedaan penting dibanding hash table kita: urutan iterasi unordered_map ditentukan detail internal bucket dan tidak dijamin stabil antar implementasi — jangan pernah mengandalkan urutannya saat mencetak.

Hash table unggul untuk kecepatan, tetapi kehilangan satu hal: urutan. Ketika aplikasi butuh data yang selalu terurut — daftar nilai siswa dari kecil ke besar, indeks kamus — kita membutuhkan keluarga struktur berbeda: tree, topik chapter berikutnya.

Rujukan resmi: std::unordered_map dan std::hash .