Hash Function

Hash function adalah jantung dari sebuah hash table. Sebuah hash function yang buruk dapat mengubah struktur O(1) rata-rata menjadi O(n) dalam praktik, sedangkan hash function yang baik membuat distribusi data merata ke seluruh bucket dengan sedikit collision. Pada Chapter ini kita akan mempelajari sifat-sifat yang wajib dimiliki hash function, tiga metode klasik (division, multiplication, polynomial rolling untuk string), serta cara STL menyediakan std::hash<T> untuk berbagai tipe bawaan. Pemahaman ini menjadi fondasi sebelum kita membahas collision resolution di chapter-chapter selanjutnya.

Sifat Hash Function yang Baik #

Sebuah hash function h: K -> {0, 1, ..., m-1} dianggap baik bila memenuhi empat kriteria berikut:

1. Deterministik — untuk input yang sama, output harus selalu sama selama m tidak berubah.
2. Cepat dihitung — kompleksitas O(1) untuk tipe primitif, atau O(panjang key) untuk string/data besar.
3. Distribusi seragam — untuk himpunan key yang masuk akal, setiap bucket memiliki peluang kira-kira sama untuk dipilih.
4. Avalanche effect — perubahan kecil pada input (mis. satu bit) mengubah output secara signifikan, agar pola pada input tidak terbawa ke output.

Mekanisme: Konflik antar Sifat #

Tidak ada hash function yang optimal untuk semua data. Sebagai contoh, h(k) = k mod m sangat cepat, tetapi bila k selalu kelipatan m, seluruh key terkonsentrasi di bucket 0. Karena itu, pemilihan hash function harus mempertimbangkan pola data yang akan di-hash.

Metode Division #

Metode paling sederhana dan paling banyak digunakan dalam buku ajar:

h(k) = k mod m

Aturan pemilihan m:

• m harus bilangan prima yang tidak dekat dengan pangkat 2.
• Hindari m = 2^p kecuali diketahui distribusi key seragam di semua bit.
• Praktik umum: m prima antara 1.5n hingga 2n untuk load factor α ≈ 0.5–0.67.

#include <iostream>

std::size_t hash_div(int key, std::size_t m) {
    return static_cast<std::size_t>(key) % m;
}

int main() {
    std::size_t m = 13;
    int keys[] = {7, 20, 33, 46, 100, 200};
    for (int k : keys) {
        std::cout << "h(" << k << ") = " << k << " mod " << m
                  << " = " << hash_div(k, m) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

h(7) = 7 mod 13 = 7
h(20) = 20 mod 13 = 7
h(33) = 33 mod 13 = 7
h(46) = 46 mod 13 = 7
h(100) = 100 mod 13 = 9
h(200) = 200 mod 13 = 5

1. Baris return key % m;: satu operasi modulus. Sangat cepat di CPU modern.
2. Hasil h(7) = h(20) = h(33) = h(46) = 7: keempat key berbeda menghasilkan bucket yang sama. Karena 20-7=13, 33-20=13, 46-33=13 — selisih kelipatan m. Ini wajar pada data terurut dengan langkah tetap; modifikasi hash function atau pemilihan m yang berbeda mungkin diperlukan.

Metode Multiplication #

Metode ini mengurangi ketergantungan pada pilihan m:

h(k) = floor(m * (k * A mod 1))     dengan 0 < A < 1

Konstanta A yang direkomendasikan Knuth adalah (sqrt(5) - 1) / 2 ≈ 0.6180339887. Keunggulan: m boleh pangkat dua (mis. 2^p), yang memungkinkan optimasi bit-shift.

#include <iostream>
#include <cstdint>
#include <cmath>

std::size_t hash_mul(std::uint64_t key, std::size_t m) {
    const double A = 0.6180339887498949;  // (sqrt(5)-1)/2
    double frac = std::fmod(static_cast<double>(key) * A, 1.0);
    return static_cast<std::size_t>(m * frac);
}

int main() {
    std::size_t m = 16;                  // pangkat dua, OK di sini
    int keys[] = {7, 20, 33, 46, 100, 200};
    for (int k : keys) {
        std::cout << "h(" << k << ") = " << hash_mul(k, m) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

h(7) = 5
h(20) = 5
h(33) = 6
h(46) = 6
h(100) = 12
h(200) = 9

1. Baris const double A = 0.6180339887498949;: konstanta Knuth. Sifatnya membuat pola pada k terdistribusi acak ke seluruh rentang [0, m).
2. Baris double frac = std::fmod(key * A, 1.0);: ambil bagian pecahan dari k * A. Operasi ekuivalen: k * A - floor(k * A).
3. Baris return static_cast<std::size_t>(m * frac);: kalikan pecahan dengan m untuk mendapatkan indeks di [0, m-1].
4. Hasil: pasangan h(7)=h(20)=5 dan h(33)=h(46)=6 tetap collision, tetapi sebaran lebih baik daripada division yang seragam menumpuk pada satu bucket untuk deret aritmetika langkah m.

Polynomial Rolling Hash untuk String #

String tidak memiliki representasi numerik natural. Kita bisa memperlakukan string sebagai bilangan berbasis B (mis. B = 31 atau B = 256), dengan modulus m prima besar:

h(s) = (s[0] * B^(n-1) + s[1] * B^(n-2) + ... + s[n-1] * B^0) mod m

Implementasi efisien memakai loop Horner:

h = 0
for c in s:
    h = (h * B + c) mod m

Kode: Polynomial Rolling Hash #

#include <iostream>
#include <string>
#include <cstdint>

class RollingHash {
    std::uint64_t m_;
    std::uint64_t B_;
public:
    RollingHash(std::uint64_t m = 1'000'000'007ULL,
                std::uint64_t B = 31ULL)
        : m_(m), B_(B) {}

    std::uint64_t hash(const std::string& s) const {
        std::uint64_t h = 0;
        for (unsigned char c : s) {
            h = (h * B_ + static_cast<std::uint64_t>(c)) % m_;
        }
        return h;
    }
};

int main() {
    RollingHash rh;
    std::string words[] = {"andi", "andi ", "budi", "adni", "andi"};
    for (const auto& w : words) {
        std::cout << "h(\"" << w << "\") = " << rh.hash(w) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

h("andi") = 2998642
h("andi ") = 92957934
h("budi") = 3035160
h("adni") = 2989342
h("andi") = 2998642

1. Baris m = 1'000'000'007ULL: bilangan prima besar (10^9 + 7) populer di algoritma kompetitif. Mengurangi collision hingga batas statistik.
2. Baris B = 31ULL: basis berupa bilangan prima yang sedikit lebih besar dari 26 (jumlah huruf alfabet). Memastikan setiap posisi karakter memberi kontribusi berbeda.
3. Baris h = (h * B_ + c) % m_;: skema Horner — setara dengan menghitung polinomial tetapi dalam O(n) tanpa eksponensiasi terpisah. Modulus di setiap langkah mencegah overflow uint64_t untuk string panjang.
4. Hasil h("andi") = 2998642 dua kali: deterministik — input sama menghasilkan output sama.
5. Hasil h("adni") = 2989342 != h("andi") = 2998642: permutasi karakter menghasilkan hash berbeda, yang menjadi kunci kegunaan rolling hash untuk pencarian substring (lihat Chapter Penerapan Hashing).

std::hash<T> di STL #

C++ menyediakan std::hash<T> di header <functional> untuk tipe bawaan. Inilah yang dipakai std::unordered_map<K, V> dan std::unordered_set<T> secara default.

Kode: Memakai std::hash #

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<int> hi;
    std::hash<double> hd;
    std::hash<std::string> hs;

    std::cout << "hash(42)       = " << hi(42) << '\n';
    std::cout << "hash(42)       = " << hi(42) << " (konsisten)\n";
    std::cout << "hash(3.14)     = " << hd(3.14) << '\n';
    std::cout << "hash(\"andi\")   = " << hs("andi") << '\n';
    std::cout << "hash(\"budi\")   = " << hs("budi") << '\n';
    return 0;
}

Output yang Dihasilkan:

hash(42)       = 42
hash(42)       = 42 (konsisten)
hash(3.14)     = 5464867211497793177
hash("andi")   = 1051165276492383067
hash("budi")   = 3010513491367729933

1. Baris std::hash<int> hi;: objek function yang meng-hash int. Implementasi libstdc++ biasanya identity: h(x) = x.
2. Baris std::hash<std::string> hs;: hash string memakai algoritma FNV-1a atau serupa, yang merupakan polynomial-like hash dengan XOR.
3. Hasil konsisten hash(42) = 42: deterministik dalam satu proses, namun tidak dijamin sama antar implementasi (libstdc++ vs libc++). Jangan menyimpan std::hash ke file untuk dibaca program lain — gunakan hash yang spesifik.
4. Hash double dan string menghasilkan angka besar: rentang penuh size_t (64-bit di sini). Nilai spesifik bergantung pada implementasi compiler; angka di atas diambil dari g++ 14.2.0 libstdc++. STL akan memetakan ke bucket internal via hash % bucket_count.

Perbandingan Metode #

Untuk tipe custom (mis. struct Point), kita bisa mengkombinasikan std::hash dari anggota field via pola hash_combine: seed ^= h(field) + 0x9e3779b9 + (seed << 6) + (seed >> 2);. Pola ini mendistribusi seragam dan menjadi idiom standar — akan kita pakai di Chapter unordered_map dan unordered_set.

Ringkasan #

• Hash function yang baik wajib deterministik, cepat, distribusi seragam, dan memiliki avalanche effect.
• Metode division h(k) = k mod m paling sederhana, mensyaratkan m prima.
• Metode multiplication h(k) = floor(m * (kA mod 1)) mengurangi ketergantungan pada m, boleh m = 2^p.
• Polynomial rolling hash h = (h*B + c) mod m cocok untuk string dan menjadi dasar algoritma Rabin-Karp.
• STL std::hash<T> menyediakan hash default untuk tipe bawaan; implementasi tidak portable antar compiler.
• Untuk tipe custom, kombinasi std::hash anggota via pola hash_combine adalah idiom standar.