📖 1. Motivasi Hash Table

Permasalahan: Menyimpan & mengakses data personel berdasarkan NIK

Direct Addressing

Ide: Gunakan key sebagai index array langsung

int table[1000];

// Insert
table[key] = value;   // O(1)

// Search
return table[key];    // O(1)

// Delete
table[key] = -1;      // O(1)
                    

Konsep Hashing

Gambar 14.1: Konsep dasar hashing

Komponen Hash Table

📖 2. Fungsi Hash

Karakteristik Fungsi Hash yang Baik

1. Deterministic: Key sama → hash sama
2. Uniform Distribution: Menyebar merata
3. Efficient: Cepat dihitung O(1)
4. Minimize Collision: Key berbeda → hash berbeda

Division Method

int hashDivision(int key, int m) {
    return key % m;
}

// h(12345) dengan m = 97
// = 12345 % 97 = 70
                    

Multiplication Method

int hashMultiplication(int key, int m) {
    const double A = 0.6180339887;
    double temp = key * A;
    temp = temp - (int)temp;  // Bagian fraksional
    return (int)(m * temp);
}
                    

Keuntungan: Nilai m tidak kritis, bisa power of 2

Hash untuk String

Polynomial Rolling Hash:

unsigned long hashString(const string& key, int m) {
    unsigned long hash = 0;
    unsigned long base = 31;  // Bilangan prima
    
    for (char c : key) {
        hash = (hash * base + c) % m;
    }
    
    return hash;
}

// hash("abc", 100) = 54
                    

🧠 Quiz: Fungsi Hash

📖 3. Collision

Gambar 14.2: Ilustrasi collision

Mengapa Collision Pasti Terjadi?

Dua Pendekatan Collision Handling

Contoh Collision

h(k) = k mod 7

Pola: Semua key bentuk 7k + 3 collision di slot 3

📖 4. Separate Chaining

Gambar 14.3: Hash table dengan separate chaining

💻 Implementasi Insert

void insert(int key, const string& value) {
    int index = hash(key);
    
    // Cek apakah key sudah ada
    for (auto& pair : table[index]) {
        if (pair.first == key) {
            pair.second = value;  // Update
            return;
        }
    }
    
    // Key belum ada, tambahkan
    table[index].push_back({key, value});
}
                    

💻 Implementasi Search & Delete

// Search
string* search(int key) {
    int index = hash(key);
    for (auto& pair : table[index]) {
        if (pair.first == key) {
            return &pair.second;
        }
    }
    return nullptr;  // Not found
}

// Delete
bool remove(int key) {
    int index = hash(key);
    for (auto it = table[index].begin(); it != table[index].end(); ++it) {
        if (it->first == key) {
            table[index].erase(it);
            return true;
        }
    }
    return false;
}
                    

Kompleksitas Separate Chaining

α = n/m adalah load factor

📖 5. Open Addressing

Linear Probing

Gambar 14.4: Linear probing

💻 Insert dengan Linear Probing

bool insert(int key, const string& value) {
    int index = hash(key);
    int i = 0;
    
    do {
        int probeIndex = (index + i) % size;
        
        // Slot kosong - bisa insert
        if (!occupied[probeIndex]) {
            keys[probeIndex] = key;
            values[probeIndex] = value;
            occupied[probeIndex] = true;
            return true;
        }
        
        // Linear probe: cek slot berikutnya
        i++;
        
    } while (i < size);
    
    return false;  // Table penuh
}
                    

Masalah: Primary Clustering

Quadratic Probing

Double Hashing

int h1(int k) { return k % m; }
int h2(int k) { return 1 + (k % (m-1)); }

int doubleHash(int k, int i, int m) {
    return (h1(k) + i * h2(k)) % m;
}
                    

✓ Menghindari clustering
✓ Distribusi probe lebih merata

🧠 Quiz: Linear Probing

Lazy Deletion

📖 6. Load Factor & Rehashing

Rehashing

Expected Probes (Open Addressing)

Kesimpulan: Jaga α ≤ 0.75 untuk performa baik!

📖 7. Aplikasi Hash Table

💻 Contoh: Counting

#include <unordered_map>

// Menghitung frekuensi karakter
string text = "hello world";
unordered_map<char, int> freq;

for (char c : text) {
    freq[c]++;  // O(1) per karakter
}

// freq['l'] = 3, freq['o'] = 2, ...
                    

💻 Contoh: Find Intersection

vector<int> findIntersection(const vector<int>& arr1, 
                             const vector<int>& arr2) {
    // Masukkan arr1 ke hash set - O(n)
    unordered_set<int> set1(arr1.begin(), arr1.end());
    
    // Cek arr2 yang ada di set1 - O(m)
    vector<int> result;
    for (int num : arr2) {
        if (set1.count(num)) {
            result.push_back(num);
            set1.erase(num);  // Avoid duplicates
        }
    }
    
    return result;  // Total: O(n + m)
}
                    

Tanpa hash table: O(n × m)