Open Addressing

Open addressing menyelesaikan collision tanpa wadah sekunder: semua entry disimpan langsung di dalam array bucket. Ketika bucket target h(k) sudah ditempati key lain, kita mencari bucket alternatif dengan strategi probing hingga menemukan slot kosong. Pendekatan ini memberi keunggulan cache-friendly (data kontigu) tetapi membatasi load factor di bawah 1. Pada Chapter ini kita akan membangun implementasi open addressing dengan tiga varian probing — linear, quadratic, dan double hashing — lalu menangani tantangan deletion dengan tombstone, dan akhirnya rehashing ketika α melewati ambang.

Konsep Probing #

Mekanisme: Fungsi Probe Sequence #

Open addressing memakai fungsi hash dua-argumen h(k, i) dengan i adalah nomor probe (0, 1, 2, …). Insert memanggil h(k, 0), h(k, 1), ... hingga menemukan bucket kosong:

insert(k, v):
    for i = 0 to m-1:
        idx = h(k, i)
        if bucket[idx] kosong:
            bucket[idx] = (k, v)
            return
    error "table penuh"

Lookup melakukan probing serupa hingga menemukan key yang cocok atau bucket kosong (berarti key tidak ada).

Tiga varian klasik dari h(k, i):

Linear Probing #

Linear probing paling sederhana: jika bucket h'(k) penuh, coba h'(k)+1, h'(k)+2, ... (modulo m).

Kode: Hash Table Linear Probing #

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

template <typename K, typename V, typename Hash = std::hash<K>>
class HashMapLinear {
    struct Slot {
        K key;
        V value;
        bool occupied = false;
        bool tombstone = false;     // menandai slot yang di-erase
    };
    std::vector<Slot> slots_;
    Hash hash_fn_;
    std::size_t size_ = 0;
    float max_load_ = 0.7f;

    std::size_t h_prime(const K& key) const {
        return hash_fn_(key) % slots_.size();
    }
    bool slot_usable(std::size_t idx, const K& key) const {
        // usable untuk insert/find: occupied DAN key-nya sama
        return slots_[idx].occupied && slots_[idx].key == key;
    }
    bool slot_empty_for_insert(std::size_t idx) const {
        return !slots_[idx].occupied || slots_[idx].tombstone;
    }
    void rehash() {
        std::vector<Slot> old = std::move(slots_);
        slots_.assign(old.size() * 2 + 1, Slot{});
        size_ = 0;
        for (auto& s : old) {
            if (s.occupied && !s.tombstone) {
                insert(s.key, s.value);
            }
        }
    }
public:
    explicit HashMapLinear(std::size_t m = 17) : slots_(m) {}

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

    void insert(const K& key, const V& value) {
        if (load_factor() >= max_load_) rehash();
        std::size_t start = h_prime(key);
        for (std::size_t i = 0; i < slots_.size(); ++i) {
            std::size_t idx = (start + i) % slots_.size();
            if (slot_empty_for_insert(idx)) {
                slots_[idx] = {key, value, true, false};
                ++size_;
                return;
            }
            if (slot_usable(idx, key)) {
                slots_[idx].value = value;     // update existing
                return;
            }
        }
        throw std::runtime_error("hash table penuh");
    }

    bool find(const K& key, V& out) const {
        std::size_t start = h_prime(key);
        for (std::size_t i = 0; i < slots_.size(); ++i) {
            std::size_t idx = (start + i) % slots_.size();
            if (!slots_[idx].occupied) return false;
            if (!slots_[idx].tombstone && slots_[idx].key == key) {
                out = slots_[idx].value;
                return true;
            }
        }
        return false;
    }

    bool erase(const K& key) {
        std::size_t start = h_prime(key);
        for (std::size_t i = 0; i < slots_.size(); ++i) {
            std::size_t idx = (start + i) % slots_.size();
            if (!slots_[idx].occupied) return false;
            if (!slots_[idx].tombstone && slots_[idx].key == key) {
                slots_[idx].tombstone = true;
                --size_;
                return true;
            }
        }
        return false;
    }
};

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

    ht.insert(10, "sepuluh");
    ht.insert(17, "tujuh belas");
    ht.insert(24, "dua empat");
    ht.insert(31, "tiga satu");
    ht.insert(38, "tiga delapan");

    std::cout << "size=" << ht.size() << " cap=" << ht.capacity()
              << " alpha=" << ht.load_factor() << '\n';

    std::string v;
    for (int k : {10, 17, 24, 31, 38, 99}) {
        if (ht.find(k, v)) std::cout << "find " << k << " -> " << v << '\n';
        else               std::cout << "find " << k << " -> TIDAK\n";
    }

    ht.erase(24);
    std::cout << "\nSetelah erase(24), size=" << ht.size() << '\n';
    std::cout << "find 24 -> " << (ht.find(24, v) ? v : "TIDAK") << '\n';
    std::cout << "find 31 -> " << (ht.find(31, v) ? v : "TIDAK") << '\n';

    ht.insert(24, "dua empat baru");
    std::cout << "\nSetelah re-insert(24):\n";
    std::cout << "find 24 -> " << (ht.find(24, v) ? v : "TIDAK") << '\n';
    std::cout << "size=" << ht.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

size=5 cap=7 alpha=0.714286
find 10 -> sepuluh
find 17 -> tujuh belas
find 24 -> dua empat
find 31 -> tiga satu
find 38 -> tiga delapan
find 99 -> TIDAK

Setelah erase(24), size=4
find 24 -> TIDAK
find 31 -> tiga satu

Setelah re-insert(24):
find 24 -> dua empat baru
size=5

1. Baris struct Slot { K key; V value; bool occupied; bool tombstone; };: setiap slot menyimpan entry beserta dua flag. occupied menandai slot pernah diisi; tombstone menandai pernah dihapus. Slot “benar-benar kosong” memiliki occupied = false.
2. Baris bool slot_empty_for_insert(...) const { return !occupied || tombstone; }: insert boleh menempati slot kosong maupun slot dengan tombstone. Tombstone tidak menghentikan probe sequence saat find.
3. Baris for (i = 0; i < slots_.size(); ++i) { idx = (start + i) % slots_.size(); }: linear probing — probe berurutan dari start, wrap-around modulo kapasitas.
4. Baris if (slot_usable(idx, key)): bila kita menemukan slot yang sudah berisi key yang sama, update value — hindari duplikasi.
5. Baris if (load_factor() >= max_load_) rehash();: cek di awal insert. max_load_ = 0.7f karena open addressing sensitif terhadap α tinggi.
6. Baris slots_[idx].tombstone = true; (erase): tandai sebagai tombstone, jangan kosongkan occupied. Lookup yang melewati slot ini harus lanjut probing.
7. Hasil find 31 -> tiga satu setelah erase(24): 31 collides dengan 10 (keduanya 31 % 7 = 3, 10 % 7 = 3), lalu probing menempatkan 31 di slot setelahnya. Setelah 24 dihapus menjadi tombstone, find(31) melewati tombstone dan tetap menemukan 31 di slot selanjutnya.
8. Hasil akhir find 24 -> dua empat baru, size=5: re-insert 24 menempati slot tombstone yang sama (atau slot kosong berikutnya). size naik kembali ke 5.

Clustering pada Linear Probing #

Mekanisme: Primary Clustering #

Linear probing rentan terhadap primary clustering: setiap collision memperpanjang blok kontigu bucket terisi. Insert baru ke wilayah blok lebih cenderung memperpanjang blok daripada memulai blok baru, sehingga blok tumbuh superlinear.

Insert: 3, 10, 17, 24 (semua mod 7 = 3)
m = 7, state setelah 4 insert:

[0]    [1]    [2]    [3]    [4]    [5]    [6]
                            3      10     17    24 masih probing...
                                                  -> wrap, dapat slot 0

Pada contoh output di atas, 38 % 7 = 3 collision dengan 10, 17, 24, 31, sehingga probing berjalan cukup jauh.

Quadratic Probing #

Quadratic probing melompat dengan langkah kuadratik: probe ke-i mengunjungi h'(k) + c1·i + c2·i² (mod m). Pilihan umum c1 = 0, c2 = 1:

h(k, i) = (h'(k) + i^2) mod m

Quadratic mengurangi primary clustering karena dua key dengan h'(k) berbeda menghasilkan rangkaian probe yang berbeda. Namun secondary clustering tetap ada: dua key dengan h'(k) sama menghasilkan rangkaian probe identik.

Implementasi Probe Function #

std::size_t probe_quadratic(std::size_t h_prime, std::size_t i, std::size_t m) const {
    return (h_prime + i * i) % m;
}

Syarat mungkin menjelajahi seluruh tabel: bila m = 2^p, quadratic hanya menjelajahi m/2 slot berbeda. Pilih m prima dan m ≡ 3 (mod 4) agar seluruh m slot terjangkau.

Double Hashing #

Double hashing memakai dua hash function berbeda:

h(k, i) = (h1(k) + i * h2(k)) mod m

• h1(k) menentukan bucket awal.
• h2(k) menentukan ukuran langkah, harus tidak nol dan relatif prima terhadap m.
• Syarat umum: m prima, h2(k) = 1 + (k mod (m-1)) agar h2 selalu di [1, m-1].

Double hashing menghilangkan secondary clustering karena setiap key memiliki urutan probe yang sangat spesifik.

Kode: Probe Function Double Hashing #

#include <iostream>
#include <functional>

std::size_t h1(int k, std::size_t m) { return k % m; }
std::size_t h2(int k, std::size_t m) { return 1 + (k % (m - 1)); }

std::size_t probe_double(int k, std::size_t i, std::size_t m) {
    return (h1(k, m) + i * h2(k, m)) % m;
}

int main() {
    std::size_t m = 7;
    int keys[] = {10, 17, 24, 31, 38};
    for (int k : keys) {
        std::cout << "Probe sequence untuk key " << k << " (mod " << m << "): ";
        for (std::size_t i = 0; i < m; ++i) {
            std::cout << probe_double(k, i, m) << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Probe sequence untuk key 10 (mod 7): 3 1 6 4 2 0 5
Probe sequence untuk key 17 (mod 7): 3 2 1 0 6 5 4
Probe sequence untuk key 24 (mod 7): 3 4 5 6 0 1 2
Probe sequence untuk key 31 (mod 7): 3 5 0 2 4 6 1
Probe sequence untuk key 38 (mod 7): 3 6 2 5 1 4 0

1. Baris std::size_t h1(int k, std::size_t m) { return k % m; }: hash function pertama — bucket awal. Untuk kelima key di atas, semuanya ≡ 3 (mod 7), sehingga probe selalu dimulai dari bucket 3.
2. Baris std::size_t h2(int k, std::size_t m) { return 1 + (k % (m - 1)); }: hash function kedua — langkah probing. 1 + ... memastikan h2 ≥ 1 (tidak nol, agar probing maju). m-1 dipakai sebagai modulus untuk h2 agar langkah selalu relatif prima terhadap m prima.
3. Baris return (h1(k, m) + i * h2(k, m)) % m;: rumus double hashing. Step bergantung pada key via h2(k).
4. Hasil key 24: 3 4 5 6 0 1 2 — h2(24) = 1 + (24 % 6) = 1. Probe: 3, 3+1=4, 3+2=5, 3+3=6, 3+4=0, 3+5=1, 3+6=2. Pola langkah +1 identik dengan linear probing — kasus khusus ketika h2 sangat kecil.
5. Hasil key 10: 3 1 6 4 2 0 5 — h2(10) = 1 + (10 % 6) = 5. Probe: 3, 3+5=8≡1, 3+10=13≡6, 3+15=18≡4, 3+20=23≡2, 3+25=28≡0, 3+30=33≡5. Langkah besar membuat rangkaian melompat-lompat menjangkau seluruh bucket.
6. Insight: meskipun semua key collide pada h1 (bucket 3), rangkaian probe berbeda untuk setiap key — inilah kekuatan double hashing yang menghilangkan secondary clustering.

Perbandingan Strategi Probing #

Ringkasan #

• Open addressing menyimpan semua entry di array datar; collision diselesaikan dengan probing.
• Tiga varian probing: linear (h'+i) mod m, quadratic (h'+i²) mod m, double hashing (h1+i·h2) mod m.
• Linear probing paling cache-friendly tetapi rentan primary clustering; quadratic meredamnya tetapi secondary clustering tetap ada; double hashing menghapus keduanya.
• Deletion pada open addressing memerlukan tombstone — penanda “pernah dihapus” agar probe sequence tidak terputus.
• Load factor wajib dijaga α < 0.7 karena kompleksitas probing meningkat tajam saat α mendekati 1.
• STL tidak menyediakan open addressing; gunakan pustaka pihak ketiga bila butuh performa cache-friendly maksimal.