Hashing

Motivasi: Pencarian Sekejap Mata

Selama ini, kita mengenal algoritma pencarian seperti Sequential Search (mencari satu per satu) atau Binary Search (bagi dua). Meskipun Binary Search sangat cepat, waktu pencariannya tetap bergantung pada jumlah data. Bagaimana jika kita ingin kecepatan konstan, di mana mencari data di antara 10 barang maupun 1 juta barang memakan waktu yang sama?

Jawabannya adalah Hashing.

Ide utamanya adalah menerjemahkan nilai data itu sendiri langsung menjadi alamat lokasinya. Ibarat Anda mencari rumah teman. Daripada Anda mengetuk pintu dari ujung jalan satu per satu, teman Anda memberikan alamat spesifik. Anda bisa langsung menuju rumah tersebut dalam satu kali jalan.

Fungsi Hash (Hash Function)

Untuk menerjemahkan data menjadi alamat indeks dalam Array, kita menggunakan Fungsi Hash. Fungsi ini harus cepat dihitung dan menyebarkan data secara merata agar tidak menumpuk di satu indeks.

Metode yang paling umum adalah Modulus (Sisa Bagi). Data dibagi dengan ukuran tabel (misal MaxEl = 10), dan sisa baginya dijadikan alamat.

• Contoh: Data 77 mod 10 = 7. Data disimpan di indeks 7.
• Contoh: Data 85 mod 10 = 5. Data disimpan di indeks 5.

Masalah Tabrakan (Collision)

Karena ukuran Array biasanya terbatas, tabrakan data pasti akan terjadi. Misalnya data 22 dan 32 sama-sama menghasilkan indeks 2 jika menggunakan modulus 10. Keduanya akan berebut tempat yang sama.

Untuk menanganinya, kita menggunakan teknik Chaining (Pembentukan Rantai). Daripada mencari indeks lain, kita jadikan setiap indeks tersebut sebagai kepala dari sebuah Linked List. Data yang bertabrakan akan digandengkan satu sama lain seperti gerbong kereta.

Implementasi dengan Chaining

Teknik Chaining menggabungkan keunggulan akses cepat dari Array dan kelenturan memori dari Linked List. Kita membuat Array di mana setiap elemennya adalah sebuah penunjuk (first) ke daftar data.

Logika Memasukkan Data (Insert)

1. Hitung indeks menggunakan fungsi modulus.
2. Jika indeks tersebut masih kosong, pasang data baru sebagai elemen pertama.
3. Jika sudah ada isinya (Terjadi Tabrakan), sambungkan data baru di akhir rantai.

void InsertValue(Bucket table[], int x) {
    int index = x % MaxEl; // Hitung indeks hash
    
    Node *newNode = Allocation(x);
    if (table[index].first == NULL) {
        table[index].first = newNode;
    } else {
        // Terjadi tabrakan, telusuri sampai ujung rantai
        Node *temp = table[index].first;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}