Week 7 – Hashing

Hashing adalah sebuah searching and storing method dengan cara mengakses lokasi/index penyimpanan data secara langsung. Hashing tidak memerlukan data yang terurut (seperti binary search) dan tidak memerlukan perbandingan nilai data. Hashing erupakan searching method yang cepat namun makan banyak memory.

Sedikit ilustrasi yang tidak penting dan layak untuk di-skip : 
Misalkan anda menyimpan barang anda di loker dan anda lupa nomor lokernya. Maka anda akan men-check isi semua loker satu-satu (binary search). Bayangkan jika anda tidak lupa. Anda dengan akan sangat-cepat-dan-tepat-gk-usah-mikir-lama-tinggal-gerak-kaki-dan-tangan menemukan loker yang berisi barang anda (Hashing).
end of boring illustration 😀

Istilah dalam hashing:

  1. Hash Table
    Array tempat penyimpanan data yang dialokasikan berdasar hash
    function.
  2. Hash Function
    Fungsi untuk menentukan posisi/index data pada hash table dengan
    rumus atau teknik khusus. Pada umumnya dibuat sederhana, dan
    data harus terdistribusi secara merata dalam hash table.
  3. Collision
    Kondisi di mana nilai data yang berbeda mendapatkan nilai
    hashing atau posisi pada hash table yang sama. Collision
    sebaiknya dihindari ketika membuat hash function dan apabila terjadi, harus segera ditangani.

Hash Table:
Berisi data yang sudah ditempatkan sesuai hash function.
ukurannya sebaiknya lebih besar dibandingkan jumlah data yang ada.

Hash Function:
Beberapa contoh teknik hash function yang sudah ada:

  1. Digit Selection / Truncation (Pemotongan)
    mengambil sebagian atau sepotong dari nilai kunci
    eg. 14110110033 diambil 4 digit dari tengah menjadi 1101.
  2. Folding (melipat atau membagi)
    nilai kunci dibagi menjadi kelompok-kelompok yang sama besar,
    kemudian dijumlahkan.
    eg. 14110110033 dibagi 3 menjadi 1411, 0110, 033, lalu dijumlah
    (dalam kasus ini, 4 + 4 + 4 digit menghasilkan ukuran hash table
    9999 + 9999 + 999 size array yang dibutuhkan ~ 21.000 ).
  3. Modular arithmetic / divisor (membagi/memodulus)
    nilai kunci di modulus sebuah pembagi (pembagi umumnya prima).
    nilai pembagi kemudian menjadi ukuran hash table.
    eg. 14110110033 % 1011 = 576, ukuran hash table 1011.
  4. Multiplication (Perkalian)
    nilai kunci dikalikan sebuah angka (bisa juga dirinya sendiri),
    kemudian diambil beberapa digit (biasanya digit tengah).
    eg. 12345 * 12345 = 152399025, diambil tengah = 399.

Collision:
Beberapa teknik menghindari collision (data bertabrakan) yang sudah ada:

  1. Open Addressing:
    Data dimasukkan ke index lain yang masih kosong.
    Jadul, tidak efektif, annoying, gajelas tujuannya.

    • Linear Probing
      telusuri table di sampingnya sampai ada tempat yang kosong. Bisa dimulai dari awal atau dari nilai yang didapat dari hash function.
    • Quadratic Probing
      telusuri table dengan men-skip index sesuai
      nilai kuadratik (1, 4, 9, 16, …).
    • Double Hashing
      apabila terjadi collision, data dimasukkan ke dalam
      hash function berikutnya (dan seterusnya).
    • Rehashing
      apabila hash table mendekati penuh (70%), akan dibentuk
      hash table baru yang ukurannya lebih besar, kemudian
      data yang ada dipindahkan ke hash table tersebut.
  2. Separate Chaining:
    Metode mengatasi collision dengan menggunakan array of linked list.
    Metode ini mirip dengan radix sort. Pertama menyiapkan hash table
    berupa array of linked list. Kemudian apabila terjadi collision, maka
    data tersebut di link dengan data sebelumnya (dengan next dan prev).

WHILE (!(SUCCEED = TRY() ) ) {
IF (SUCCEED) KEEPLEARNING();
PRINTF (“:D”); }

Ditulis oleh:

  1. Adrian Hartanto Tedja (14110110033)
  2. Reza Satyawijaya (14110110074)
  3. Sintya Oktaviani (14110110021)

Leave a comment