Separate chaining menyelesaikan collision dengan cara paling intuitif: biarkan setiap bucket menampung lebih dari satu entry. Saat dua key berbeda terpetakan ke indeks yang sama, keduanya disimpan dalam wadah sekunder (linked list atau vector) yang tergantung pada bucket tersebut. Lookup cukup menghitung indeks, lalu mencari linear di wadah tersebut. Pada Chapter ini kita akan membangun implementasi hash table dengan separate chaining secara bertahap — mulai dari operasi dasar insert/find/erase, lalu menambahkan load factor monitoring, dan akhirnya rehashing otomatis ketika tabel terlalu penuh. Implementasi ini menjadi cetak biru yang sama dipakai STL std::unordered_map.

Struktur Dasar #

Mekanisme: Bucket sebagai Linked List #

Setiap bucket adalah pointer ke singly-linked list node. Setiap node menyimpan pasangan key-value dan pointer ke node berikutnya dengan hash yang sama.

Operasi dasar kompleksitas rata-rata O(1 + α) dengan α = n/m (load factor), karena panjang rantai rata-rata adalah α.

Komponen Class #

cpp 
template <typename K, typename V>
struct ChainNode {
    K key;
    V value;
    ChainNode* next;
};

template <typename K, typename V, typename Hash = std::hash<K>>
class HashMapChaining { /* ... */ };
  • K — tipe key (int, string, dll.)
  • V — tipe value
  • Hash — hash function policy, default std::hash<K>
  • ChainNode — node linked list sederhana

Implementasi Lengkap dengan Rehashing #

Kode: Hash Table Separate Chaining #

cpp 
#include <iostream>
#include <vector>
#include <list>
#include <utility>
#include <string>
#include <functional>

template <typename K, typename V, typename Hash = std::hash<K>>
class HashMapChaining {
public:
    using Entry = std::pair<K, V>;
private:
    std::vector<std::list<Entry>> buckets_;
    Hash hash_fn_;
    std::size_t size_ = 0;
    float max_load_ = 0.75f;

    std::size_t bucket_index(const K& key) const {
        return hash_fn_(key) % buckets_.size();
    }

    void rehash_if_needed() {
        if (load_factor() < max_load_) return;
        std::size_t new_m = buckets_.size() * 2 + 1;
        std::vector<std::list<Entry>> new_buckets(new_m);
        for (auto& chain : buckets_) {
            for (auto& entry : chain) {
                std::size_t idx = hash_fn_(entry.first) % new_m;
                new_buckets[idx].push_back(std::move(entry));
            }
        }
        buckets_.swap(new_buckets);
    }
public:
    explicit HashMapChaining(std::size_t initial_m = 17)
        : buckets_(initial_m) {}

    std::size_t size() const { return size_; }
    std::size_t bucket_count() const { return buckets_.size(); }
    float load_factor() const {
        return static_cast<float>(size_) / buckets_.size();
    }

    void insert(const K& key, const V& value) {
        std::size_t idx = bucket_index(key);
        for (auto& entry : buckets_[idx]) {
            if (entry.first == key) { entry.second = value; return; }
        }
        buckets_[idx].push_back({key, value});
        ++size_;
        rehash_if_needed();
    }

    bool find(const K& key, V& out) const {
        std::size_t idx = bucket_index(key);
        for (const auto& entry : buckets_[idx]) {
            if (entry.first == key) { out = entry.second; return true; }
        }
        return false;
    }

    bool erase(const K& key) {
        std::size_t idx = bucket_index(key);
        auto& chain = buckets_[idx];
        for (auto it = chain.begin(); it != chain.end(); ++it) {
            if (it->first == key) { chain.erase(it); --size_; return true; }
        }
        return false;
    }

    void print_distribution() const {
        for (std::size_t i = 0; i < buckets_.size(); ++i) {
            std::cout << "bucket " << i << ": " << buckets_[i].size() << '\n';
        }
    }
};

int main() {
    HashMapChaining<std::string, int> ht(7);

    ht.insert("andi", 90);
    ht.insert("budi", 85);
    ht.insert("citra", 78);
    ht.insert("dewi", 92);
    ht.insert("eka", 88);
    ht.insert("fajar", 75);

    int v;
    if (ht.find("budi", v))
        std::cout << "nilai budi = " << v << '\n';
    if (ht.find("andi", v))
        std::cout << "nilai andi = " << v << '\n';
    if (!ht.find("zaki", v))
        std::cout << "zaki tidak ditemukan\n";

    std::cout << "\nSebelum erase, size = " << ht.size()
              << ", bucket_count = " << ht.bucket_count()
              << ", load_factor = " << ht.load_factor() << '\n';

    ht.erase("budi");
    std::cout << "Setelah erase budi, size = " << ht.size() << '\n';

    // Trigger rehash dengan banyak insert
    for (int i = 0; i < 30; ++i) {
        ht.insert("key" + std::to_string(i), i);
    }
    std::cout << "\nSetelah 30 insert tambahan:\n";
    std::cout << "  size = " << ht.size()
              << ", bucket_count = " << ht.bucket_count()
              << ", load_factor = " << ht.load_factor() << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
nilai budi = 85
nilai andi = 90
zaki tidak ditemukan

Sebelum erase, size = 6, bucket_count = 15, load_factor = 0.4
Setelah erase budi, size = 5

Setelah 30 insert tambahan:
  size = 35, bucket_count = 63, load_factor = 0.555556
  1. Baris std::vector<std::list<Entry>> buckets_;: setiap bucket adalah std::list<Entry> — doubly-linked list STL yang mendukung erase iterator dengan O(1). Inilah representasi separate chaining paling idiomatis.
  2. Baris float max_load_ = 0.75f;: ambang batas load factor. Bila load_factor() melampaui 0.75, rehash_if_needed() akan memicu rehash.
  3. Baris for (auto& entry : buckets_[idx]) (insert): linear search di rantai bucket untuk mendeteksi key yang sudah ada. Bila ketemu, update value; bila tidak, push_back entry baru.
  4. Baris buckets_[idx].push_back({key, value});: tambahkan entry ke akhir rantai. Kompleksitas O(1) amortized.
  5. Baris rehash_if_needed();: dipanggil setelah insert. Logika di rehash_if_needed: bila α ≥ 0.75, alokasi array baru dengan ukuran 2m + 1 (ganjil agar peluang prima lebih tinggi), lalu pindahkan setiap entry ke bucket baru berdasarkan hash baru.
  6. Baris buckets_.swap(new_buckets);: swap pointer internal — O(1). Array lama akan di-destruktor setelah fungsi selesai.
  7. Hasil bucket_count = 15 setelah 6 insert: awalnya m = 7, setelah insert ke-6 α = 6/7 ≈ 0.857 melampaui 0.75, memicu rehash ke m = 15 (2·7+1). α baru = 6/15 = 0.4. Inilah mengapa tampilan menunjukkan load_factor = 0.4, bukan 0.857.
  8. Hasil akhir bucket_count = 63, α = 0.555: setelah 30 insert tambahan (size total = 35), terjadi dua rehash berturut-turut — dari 15 ke 31 (saat size mencapai 12, α = 12/15 = 0.8), lalu dari 31 ke 63 (saat size mencapai 24, α = 24/31 ≈ 0.774). α akhir = 35/63 ≈ 0.555, di bawah ambang 0.75.

Load Factor dan Performa #

Load factor α = n/m adalah ukuran seberapa penuh hash table. Performa separate chaining bergantung pada panjang rantai rata-rata, yang persis sama dengan α.

α rata-rataPanjang rantaiLookup expectedLookup worst
0.50.51.5 langkahO(n) (semua di 1 bucket)
0.750.751.75 langkahO(n)
1.01.02 langkahO(n)
2.02.03 langkahO(n)

Worst case O(n) terjadi ketika semua key terkonsentrasi di satu bucket (hash function sangat buruk atau data disusun musuh). Inilah mengapa pemilihan hash function penting.

Mekanisme: Rehashing Amortisasi #

Biaya rehashing adalah O(n) — seluruh entry dipindahkan. Namun karena rehash jarang terjadi (setiap ~n/2 insert), biaya amortisasi per insert adalah O(1). Ini analog dengan strategi doubling pada std::vector (lihat Chapter Kompleksitas Amortisasi).

Operasi Erase dan Iterator Stability #

Mekanisme: Erase di Doubly-Linked List #

std::list mendukung erase iterator dalam O(1) tanpa membatalkan iterator lain. Ini berbeda dari std::vector yang erase O(n) dan membatalkan semua iterator setelah titik hapus. Karena itu, std::list cocok sebagai wadah bucket pada hash table yang banyak melakukan erase.

cpp 
auto& chain = buckets_[idx];
for (auto it = chain.begin(); it != chain.end(); ++it) {
    if (it->first == key) {
        chain.erase(it);   // O(1), iterator lain tetap valid
        --size_;
        return true;
    }
}

Bila memakai std::vector sebagai bucket, erase akan O(panjang rantai) karena elemen setelahnya harus digeser — tetapi tetap O(1+α) rata-rata karena rantai pendek.

Verifikasi Distribusi #

Mari kita cek distribusi bucket pada hash table dengan 35 entry di 57 bucket:

cpp 
// (Tambahkan pada main sebelum return 0)
std::cout << "\nDistribusi bucket:\n";
ht.print_distribution();

Output yang Dihasilkan (cuplikan):

text 
Distribusi bucket:
bucket 0: 1
bucket 1: 0
bucket 2: 1
bucket 3: 2
...
bucket 55: 0
bucket 56: 1

Distribusi yang sehat memiliki mayoritas bucket berisi 0-2 entry. Bila satu bucket berisi >5 entry, hash function perlu diinvestigasi.

Ringkasan #

  • Separate chaining menampung collision di wadah sekunder (linked list) per bucket.
  • Tiga operasi dasar — insert/find/erase — rata-rata O(1+α), worst O(n).
  • Load factor α = n/m mengontrol panjang rantai rata-rata; ambang umum 0.75 memicu rehash.
  • Rehashing memperbesar m (umumnya 2m+1) dan mendistribusikan ulang semua entry; biaya O(n) tetapi amortisasi O(1) per insert.
  • std::list cocok sebagai wadah bucket karena erase O(1) dan iterator stability.
  • STL std::unordered_map menggunakan strategi ini secara default; inspeksi via bucket_count(), bucket_size(), load_factor().