# Tugas Pendahuluan Modul 7 - Hash

Pembuat Soal: RE

Nama : Reinathan Ezkhiel Kurniawan
NPM  : 2406397675

## Teori (65 poin)

### 1. Jelaskan apa itu Hashing! Sebutkan dan jelaskan apa saja komponen yang ada dalam Hashing! <span style="color:red;"> (15 poin) </span>

**Hashing** adalah sebuah teknik dalam struktur data yang melakukan pemetaan (*mapping*) dari sebuah kunci (*key*) ke indeks dalam sebuah tabel melalui fungsi *hash* sehingga operasi pencarian, penyisipan, dan penghapusan dapat dilakukan dengan waktu rata - rata **O(1)**.

Komponen - komponen utama dalam *hashing* adalah :
* **hash function** : fungsi yang menerima *key* sebagai *input* dan menghasilkan indeks (atau *bucket*) pada tabel. Metode paling umum adalah **division method** dengan formula **h(k) = k mod m** k adalah *key* dan m adalah *tabel*.
* **hash table** : struktur penyimpanan dasar berupa *array* atau kumpulan *bucket* di mana hasil fungsi *hash* menentukan lokasi untuk menyimpan *value* atau pasangan *key-value*.
* **Collision resolution mechanism** : karena dua atau lebih *key* bisa menghasilkan indeks yang sama (*collision*), maka diperlukan mekanisme untuk menangani hal ini. (Contohnya di Nomor 2).
* *Load Factor* merupakan antara jumlah elemen yang tersimpan dengan jumlah *bucket*. Penting karena mempengaruhi performa dan dan menentukan saat untuk melakukan *rehashing*.
* **rehashing** terjadi bila *load factor* terlalu besar maka ukuran tabel diperbesar (misal di*double*) dan semua elemen di - *rehash* (dimasukkan ulang) ke tabel yang lebih besar agar performa tetap baik.

### Referensi:
GeeksforGeeks, “Hashing in Data Structure,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/hashing-data-structure/. [Diakses: 7-Nov-2025]

GeeksforGeeks, “Hash Table Data Structure,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/hash-table-data-structure/. [Diakses: 7-Nov-2025]

---

### 2. Jelaskan apa itu collision dalam hashing! Sebutkan dan jelaskan cara yang umum digunakan untuk mencegah terjadinya collision! <span style="color:red;"> (15 poin) </span>

*Collision* terjadi ketika dua atau lebih *key* berbeda dipetakan oleh fungsi *hash* ke indeks atau *bucket* yang sama dalam tabel *hash*.

Cara umum untuk mencegah *collision* :
* Gunakan **separate chaining**. Setiap *bucket* dalam *hash table* bukan hanya menyimpan satu elemen tapi sebuah daftar (**linked list**) atau truktur lainnya yang menyimpan semua elemen yang *hash*- nya sama. Jika terjadi *collision*, elemen baru tinggal ditambahkan ke *chain* di *bucket* yang sama.
* **Open addressing** dengan menyimpan langsung semua elemen dalam *hash table* (jika tidak ada *list* eksternal). bila tempat yang dihasilkan fungsi *hash* sudah terisi, maka dilakukan **probing** (mencari slot kosong berikutnya) dengan berbagai strategi seperti **linear probing**, **quadratic probing** dan **double hashing** (menggunakan *hash* kedua sebagai *offset* dalam *probing*).
* **Coalesced hashing** adalah kombinasi antara *chaining* dan *open addressing* saat terjadi *collision*, elemen ditempatkan di slot kosong yang ditemukan dan kemudian terhubung dalam suatu *chain* di dalam tabel itu sendiri.

### Referensi:
GeeksforGeeks, “Collision Resolution Techniques,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/collision-resolution-techniques/
. [Diakses: 7-Nov-2025]

GeeksforGeeks, “Separate Chaining Collision Handling Technique in Hashing,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/separate-chaining-collision-handling-technique-in-hashing/
. [Diakses: 7-Nov-2025]

---

### 3. Jelaskan apa itu Load Factor! Mengapa konsep rehashing menjadi penting? <span style="color:red;"> (10 poin) </span>

*Load Factor* pada *hash table* merupakan rasio antara jumlah elemen yang tersimpan (**n**) dengan jumlah **bucket** atau **slot** dalam tabel (**m**) maka *Load Factor* = **n**/**m**.

Semakin besar *Load Factor* maka semakin banyak elemen yang saling bersaing untuk *bucket* yang sama (meningkatkan *collision*, dan waktu pencarian rata-rata menjadi lebih besar dari O(1)).

Dengan memantau *load factor* dan menetapkan **threshold** maka sistem dapat melakukan *rehashing* (memperbesar tabel dan me-*rehash* elemen) agar tabel tetap memiliki *load factor* yang wajar dan menjaga performa tetap dalam jangkauan kompleksitas **O(1)**.

Maka, konsep *rehashing* menjadi penting karena ketika *load factor* sudah melewati batas yang ditetapkan, maka tabel perlu di *re-size* dan semua elemen dipetakan ulang ke *bucket* baru agar distribusi *key* lebih baik dan *collision* lebih sedikit. Tanpa *rehashing* maka performa struktur *hash* akan menurun drastis.
### Referensi:
GeeksforGeeks, “Load Factor and Rehashing,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/load-factor-and-rehashing/. [Diakses: 7-Nov-2025]

GeeksforGeeks, “Introduction to Hashing,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/introduction-to-hashing-2/. [Diakses: 7-Nov-2025]

---

### 4. Jelaskan mengenai template `std::unordered_map` dan `std_unordered_set` pada library STL! Apa perbedaan diantara keduanya? <span style="color:red;"> (15 poin) </span>

`std::unordered_map< Key, T>` : kontainer asosiasi yang tak berurut. Kontainer menyimpan pasangan *key-value*. Implementasi dasarnya menggunakan *hash table* sehingga rata-rata waktu untuk operasi *insert*,*find*,*erase* adalah O(1).

`std::unordered_set< Key, T>` adalah kontainer asosiasi yang tak berurut yang menyimpan hanya *key* dan tidak menyimpan *mapped value*. Juga berbasis *hash table*, artinya operasi *insert*,*find*,*erase* rata - rata O(1).

Perbedaan nya adalah :
* `unordered_map` menyimpan pasangan *key-value* sedangkan `unordered_set` hanya menyimpan *key*.
* `unordered_map` lebih cocok untuk struktur data seperti `dictionary` dimana kita ingin akses berdasarkan *key* untuk mendapatkan *value*. `unordered_set` cocok untuk koleksi unik elemen yang hanya ingin kita cek keberadaanya.
* Pada `unordered_map` terdapat *method* untuk mengambil/ mengubah **mapped value** (`map[key]`, `at(key)`), sedangkan `unordered_set` hanya menyediakan *method* untuk *insert*,*find*,*erase* elemen *key* saja.
* Penggunaan `unordered_map` akan menyebabkan *overhead* memori sedikit lebih besar daripada `unordered_set` karena menyimpan *value*.

### Referensi:
GeeksforGeeks, “Unordered Map in C++ STL,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/cpp/unordered_map-in-cpp-stl/. [Diakses: 7-Nov-2025]
- GeeksforGeeks, “Unordered Sets in C++ STL,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/cpp/unordered_set-in-cpp-stl/. [Diakses: 7-Nov-2025]

---

### 5. Mengapa searching menggunakan Hash Map biasanya lebih cepat daripada algoritma searching konvensional (Linear Search, Binary Search)? Jelaskan! <span style="color:red;"> (10 poin) </span>

*Searching* menggunakan *hash map* seperti `std::unordered_map` yang umumnya lebih cepat karena :
* Waktu akses rata - rata untuk operati pencarian di *hash table* adalah **O(1)**. Karena kita langsung menggunakan *hash function* untuk mendapatkan indeks *bucket* dan kemudian mencari elemen.
* Sementara algoritma pencarian konvensional **lienar search** memiliki waktu **O(n)** karena harus memerika satu per satu elemen hingga ditemukan.
* *Binary Search* memiliki waktu O(log n) tetapi memerlukan data yang sudah diurutkan dan akses acak ke elemen (masih lebih lambat daripada *hash table* apabila berfungsi dengan baik).
* Karena *hash table* tidak bergantung pada **urutan** dan melakukan perhitungan *hash* kemudian langsung akses, maka untuk banyak kasus penggunaan di mana kita hanya perlu menentukan eksistensi *key* dan *value*, maka *Hash Map* memberikan performa yang sangat baik.

### Referensi:
GeeksforGeeks, “Hash Table Data Structure,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/dsa/hash-table-data-structure/. [Diakses: 7-Nov-2025]

Programiz, “Hash Table Data Structure,” Programiz. [Online]. Available: https://www.programiz.com/dsa/hash-table. [Diakses: 7-Nov-2025]

---

## Praktik (35 poin)

Mr. Adolf adalah seorang dosen Sastra Mesin di universitas terkemuka di Jerman. Ia ingin membuat database nilai yang efisien **untuk menyimpan dan mencari data mahasiswa dengan cepat**.

Mr. Adolf sudah membuat kerangka kode dari sistem database yang ia inginkan. Akan tetapi, ia sedang sibuk menghadiri konferensi di universitas seni di Austria. Kamu adalah **asdos** dari Mr. Adolf, dan beliau meminta kamu untuk mengimplementasikan **logika hashing** menggunakan C++ tanpa STL.

### Lengkapi kode di bawah! <span style="color:red;"> (20 poin) </span>

Gunakan nama dan NPM mahasiswa sekreatif mungkin untuk menghindari plagiarisme

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

struct Mahasiswa {
    std::string nama;
    long long npm; 
};

bool operator==(const Mahasiswa& a, const Mahasiswa& b) {
    return (a.npm == b.npm) && (a.nama == b.nama);
    
}

struct KeyValuePair {
    Mahasiswa key; 
    int value; 

    KeyValuePair(const Mahasiswa& k, int v) : key(k), value(v) {}
    
};

class MyHashMap {
private:
    int n; 
    int m; 
    std::vector<std::list<KeyValuePair>> table;
    const float MAX_LOAD_FACTOR = 0.75;

 
    int hashFunction(Mahasiswa key) {
       unsigned long long HashMhs = 0; 
       const unsigned long long PrimeNum = 131;

       for (char c : key.nama) {
        HashMhs = HashMhs * PrimeNum + static_cast<unsigned char>(c);
       }
       HashMhs = HashMhs * PrimeNum + static_cast<unsigned char>(key.npm);
       return static_cast<int>(HashMhs % m);
    }

    void rehash() {
       int MLama = m; 
       m = m * 2; 

       std::vector<std::list<KeyValuePair>> oldTable = table; 
       table.clear(); 
       table.resize(m);
       n = 0; 

       for (int i = 0; i < MLama ; i++) { 
        for (const auto& KV : oldTable[i]) {
            insert(KV.key, KV.value);
        }
       }    
    }

public:
    
    MyHashMap(int size = 10) {
        n = 0;
        m = size;
        table.resize(m);
    }

    void insert(Mahasiswa key, int value) {
        
        if ((float)(n + 1) / m > MAX_LOAD_FACTOR) {
            rehash();
        }

        int index = hashFunction(key);
        auto& chain = table[index]; 

        for(auto& KV : chain) { 
            if(KV.key == key) {
                KV.value = value; 
                return;
            }
        }

        chain.push_back(KeyValuePair(key, value)); 
        n++;
        
    }

    int search(Mahasiswa key) {
        int index = hashFunction(key);
        auto& chain = table[index];

        for(auto& KV : chain) {
            if(KV.key == key) {
                return KV.value;
            }
        }
        return -1;  
    }

    void remove(Mahasiswa key) {
        int index = hashFunction(key);
        auto& chain = table[index];
        
        for (auto it = chain.begin(); it != chain.end(); ++it) {
            if(it -> key == key) { 
                chain.erase(it); 
                n--;
                return;
            }
         }       
    }
};

int main() {
    MyHashMap studentMap;

    Mahasiswa Rei = {"Reinathan Ezkhiel", 2406397601LL};
    Mahasiswa Coki = {"Reyhan Batara", 2406397602LL};
    Mahasiswa Otniel = {"Otniel Sianturi", 2406397603LL};
    Mahasiswa Josh  = {"Joshua Ricardo", 2406397603LL};
    

    studentMap.insert(Rei, 92);
    studentMap.insert(Coki, 85);
    studentMap.insert(Otniel, 78);
    studentMap.insert(Josh, 67);

    std::cout << "Nilai Reinathan Ezkhiel: " << studentMap.search(Rei) << std::endl;
    std::cout << "Nilai Reyhan Batara: " << studentMap.search(Coki) << std::endl;
    std::cout << "Nilai Otniel Sianturi: " << studentMap.search(Otniel) << std::endl;
    std::cout << "Nilai Joshua Ricardo: " << studentMap.search(Otniel) << std::endl;
    
    studentMap.insert(Rei, 30);
    studentMap.insert(Coki, 45);
    studentMap.insert(Otniel, 18);
    studentMap.insert(Josh, 27);

    std::cout << "Nilai Reinathan Ezkhiel (update): " << studentMap.search(Rei) << std::endl;
    std::cout << "Nilai Reyhan Batara (update): " << studentMap.search(Coki) << std::endl;
    std::cout << "Nilai Otniel Sianturi(update): " << studentMap.search(Otniel) << std::endl;
    std::cout << "Nilai Joshua Ricardo(update): " << studentMap.search(Otniel) << std::endl;

    studentMap.remove(Otniel);
    studentMap.remove(Coki);
    
    std::cout << "Nilai Otniel Sianturi setelah dihapus (harus -1): " << studentMap.search(Otniel) << std::endl;
    std::cout << "Nilai Reyhan Batara setelah dihapus (harus -1): " << studentMap.search(Coki) << std::endl;

    return 0;
}

**Screenshot Output:**

---

### Refactor Kode <span style="color:red;"> (10 poin) </span>

Mr. Adolf sudah menerima program database nilai yang kamu buat. Akan tetapi, beliau penasaran dengan perbedaan implementasi **separate chaining** dengan **open addressing**. Oleh karena itu, Mr. Adolf meminta kamu untuk **mengubah** program yang kamu buat untuk mengimplementasikan open addressing dengan **linear probing**.

**Program Baru:**

#include <iostream>
#include <string>
#include <vector>


struct Mahasiswa {
    std::string nama;
    long long npm; 
};

bool operator==(const Mahasiswa& a, const Mahasiswa& b) {
    return (a.npm == b.npm) && (a.nama == b.nama);
    
}

struct Entry {
    Mahasiswa key; 
    int value; 
    bool terisi; 
    bool dihapus;

    Entry() : value(0), terisi(false), dihapus(false) {}
    
};

class MyHashMap {
private:
    int n; 
    int m; 
    std::vector<Entry> table;
    const float MAX_LOAD_FACTOR = 0.75;

 
    int hashFunction(Mahasiswa key) {
       unsigned long long HashMhs = 0; 
       const unsigned long long PrimeNum = 131;

       for (char c : key.nama) {
        HashMhs = HashMhs * PrimeNum + static_cast<unsigned char>(c);
       }
       HashMhs = HashMhs * PrimeNum + static_cast<unsigned char>(key.npm);
       return static_cast<int>(HashMhs % m);
    }

    void rehash() {
       int MLama = m; 
       m = m * 2; 

       std::vector<Entry> oldTable = table; 
       table.clear(); 
       table.resize(m);
       n = 0; 

       for (int i = 0; i < MLama ; i++) { 
        if (oldTable[i].terisi && !oldTable[i].dihapus) {
            insert(oldTable[i].key, oldTable[i].value);
        }
       }    
    }

public:
    // Constructor
    MyHashMap(int size = 10) {
        n = 0;
        m = size;
        table.resize(m);
    }

    void insert(Mahasiswa key, int value) {
        // Cek load factor
        if (static_cast<float>(n + 1) / m > MAX_LOAD_FACTOR) {
            rehash();
        }

        int index = hashFunction(key);
        int firstDeleted = -1;

        for (int i = 0; i < m; ++i) { 
            int current = (index + i)%m;
            Entry& e = table[current];
        
            if(e.terisi && e.dihapus && firstDeleted == -1) {
                firstDeleted = current;
            }

            if(!e.terisi) { 
                int target = (firstDeleted != -1) ? firstDeleted : current;
                table[target].key = key;
                table[target].value = value; 
                table[target].terisi = true; 
                table[target].dihapus = false;
                n++;
                return;
            }

            if(!e.dihapus && e.key == key) {
                e.value = value;
                return;
            }
        }
     }       

    int search(const Mahasiswa& key){
        int index = hashFunction(key);

        for(int i = 0; i < m; ++i) {
            int current = (index + i) % m;
            const Entry& e = table[current];

            if(!e.terisi && !e.dihapus) {
                return -1;
            }
        
         if(!e.terisi && !e.dihapus && e.key == key) {
                return e.value;
         }
    }
}

    void remove(Mahasiswa key) {
        int index = hashFunction(key);
        
        for (int i = 0; i < m; ++i) {
        int current = (index + i) % m;
        Entry& e = table[current];

        if(!e.terisi && !e.dihapus) { 
            return;
        }

        if(e.terisi && !e.dihapus && e.key == key) {
            e.dihapus = true; 
            n--; 
            return;
        }
    }
  }       
};

int main() {
    MyHashMap studentMap;

    Mahasiswa Rei = {"Reinathan Ezkhiel", 2406397601LL};
    Mahasiswa Coki = {"Reyhan Batara", 2406397602LL};
    Mahasiswa Otniel = {"Otniel Sianturi", 2406397603LL};
    Mahasiswa Josh  = {"Joshua Ricardo", 2406397603LL};
    

    studentMap.insert(Rei, 92);
    studentMap.insert(Coki, 85);
    studentMap.insert(Otniel, 78);
    studentMap.insert(Josh, 67);

    std::cout << "Nilai Reinathan Ezkhiel: " << studentMap.search(Rei) << std::endl;
    std::cout << "Nilai Reyhan Batara: " << studentMap.search(Coki) << std::endl;
    std::cout << "Nilai Otniel Sianturi: " << studentMap.search(Otniel) << std::endl;
    std::cout << "Nilai Joshua Ricardo: " << studentMap.search(Otniel) << std::endl;
    
    studentMap.insert(Rei, 30);
    studentMap.insert(Coki, 45);
    studentMap.insert(Otniel, 18);
    studentMap.insert(Josh, 27);

    std::cout << "Nilai Reinathan Ezkhiel (update): " << studentMap.search(Rei) << std::endl;
    std::cout << "Nilai Reyhan Batara (update): " << studentMap.search(Coki) << std::endl;
    std::cout << "Nilai Otniel Sianturi(update): " << studentMap.search(Otniel) << std::endl;
    std::cout << "Nilai Joshua Ricardo(update): " << studentMap.search(Otniel) << std::endl;

    studentMap.remove(Otniel);
    studentMap.remove(Coki);

    std::cout << "Nilai Otniel Sianturi setelah dihapus (harus -1): " << studentMap.search(Otniel) << std::endl;
    std::cout << "Nilai Reyhan Batara setelah dihapus (harus -1): " << studentMap.search(Coki) << std::endl;


    return 0;
}

**Screenshot Output:**
---

### Sebutkan dan jelaskan perubahan apa saja yang kamu lakukan pada kode baru! <span style="color:red;"> (5 poin) </span>

* Menghapus Struktur List (*Chaining*) : sebelumnya setiap indeks tabel menyimpan `std::list<KeyValuePair>` untuk menampung beberapa elemen jika terjadi *collision*. Pada *refactor*, setiap indeks hanya menyimpan satu objek `Entry`, sehingga tidak perlu *list* lagi.
* Diperlukan penanda slot dihapus dalam *open addressing* agar `search` tetap bisa melanjutkan *probing* setelah penghapusan (tambahan atribut `dihapus` di `struct Entry`).
* Diganti menjadi:

struct Entry {
    Mahasiswa key;
    int value;
    bool terisi;
    bool dihapus;
};

* Mengubah Mekanisme **Collision Handling** pada sebelumnya, jika terjadi tabrakan, data baru dimasukkan ke *list* (*chaining*).Sekarang menggunakan *linear probing

for (int i = 0; i < m; ++i) {
    int current = (index + i) % m;
}

* Penyesuaian Operasi `insert()`,`search()`, dan `remove()`
* **Insert**:Jika key sudah ada maka **update** `value`. Jika slot penuh,lanjut `probing`. Jika *load factor* melebihi batas → panggil `rehash()`.
* **Search**: Lanjut *probing* hingga menemukan `key` yang cocok atau slot kosong murni (`terisi == false` dan `dihapus == false`).
* **Remove**: Tidak menghapus fisik slot, tapi hanya menandainya sebagai `dihapus = true` (**tombstone**).
* Sekarang `rehash()` menyalin seluruh **Entry aktif** ke tabel baru berukuran dua kali lebih besar. Tidak perlu memindahkan *list*, cukup reinsert data yang *terisi && !dihapus*.
* `std::vector<std::list<KeyValuePair>>` diubah menjadi `std::vector<Entry>`.
* Jumlah bucket tetap m, tapi setiap bucket hanya berisi satu elemen.

---

## <span style="color:red;">NOTE:</span> Pelajari `std::unordered_map`, `std::unordered_set`, penggunaan library `sstream`, dan penggunaan iterator untuk mempermudah pengerjaan CS!