tugas

Tugas Mandiri 3: Desain dan Implementasi Tabel Hash (Hash Table & Collision Resolution)

Tugas 4: Perancangan Tabel Hash dan Resolusi Tabrakan Kunci (Collision Resolution)

Eksplorasi mendalam mengenai rancang bangun struktur data Tabel Hash (Hash Table) kustom menggunakan bahasa Python, berfokus pada perancangan fungsi hash aritmatika serta evaluasi metode penyelesaian tabrakan kunci (collision resolution).

1. Mekanisme Fungsi Hash dan Resolusi Tabrakan

Tabel hash memetakan kunci arbitrary ke dalam slot indeks array berukuran terbatas mm menggunakan fungsi pemetaan hash h(k)h(k). Jika dua kunci berbeda menghasilkan indeks yang identik (h(k1)=h(k2)h(k_1) = h(k_2)), terjadi tabrakan kunci (collision).

  • Metode Pembagian (Division Method):
h(k)=k(modm),dengan m dipilih bilangan prima yang jauh dari pangkat duah(k) = k \pmod m, \quad \text{dengan } m \text{ dipilih bilangan prima yang jauh dari pangkat dua}
  • Metode Perkalian (Multiplication Method):
h(k)=⌊m(kA(mod1))⌋,0<A<1h(k) = \lfloor m (k A \pmod 1) \rfloor, \quad 0 < A < 1
  • Resolusi Open Addressing - Linear Probing: Mencari slot kosong berikutnya secara sekuensial:
h(k,i)=(h′(k)+i)(modm)h(k, i) = (h'(k) + i) \pmod m
  • Resolusi Open Addressing - Quadratic Probing: Meminimalisir primary clustering dengan penambahan kuadratik:
h(k,i)=(h′(k)+c1i+c2i2)(modm)h(k, i) = (h'(k) + c_1 i + c_2 i^2) \pmod m
  • Chaining (Separate Chaining): Setiap slot tabel hash menampung kepala senarai berantai (linked list) yang menyimpan seluruh pasangan pasangan kunci-nilai bertabrakan.

2. Evaluasi Faktor Muatan (Load Factor)

Rasio faktor muatan α=nm\alpha = \frac{n}{m} dianalisis secara berkala. Ketika nilai α>0.7\alpha > 0.7, operasi rehashing otomatis dijalankan untuk menggandakan ukuran tabel dan mendistribusikan ulang elemen guna menjaga kompleksitas pencarian rata-rata tetap berada pada O(1)\mathcal{O}(1).

3. Berkas Tugas Terlampir

  • Berkas slide presentasi evaluasi: TUGAS_ASD_Pertemuan10.pptx yang menyajikan perbandingan empiris jumlah probe, visualisasi fenomena clustering, dan implementasi kode fungsi hash.

Attachments

Back to Academics