PRAKTIKUM STRUKTUR DATA.9

PRAKTIKUM STRUKTUR DATA.9 HASHING

A. Definisi Praktikum

Praktikum ini merupakan kegiatan pembelajaran yang bertujuan untuk memahami dan mengimplementasikan struktur data Hashing dalam bahasa pemrograman Python. Hashing adalah teknik pemetaan data dari sebuah key menjadi sebuah indeks numerik menggunakan fungsi hash, sehingga proses penyimpanan dan pencarian data dapat dilakukan secara efisien, idealnya dalam waktu konstan O(1).

Dalam praktikum ini, mahasiswa membangun tiga jenis implementasi tabel hash, yaitu:

1. SimpleHashTable — tabel hash dasar tanpa penanganan collision.
2. LinearProbingHashTable — tabel hash dengan penanganan collision menggunakan teknik linear probing (mencari slot kosong berikutnya).
3. ChainingHashTable — tabel hash dengan penanganan collision menggunakan teknik chaining (setiap slot berisi list untuk menampung banyak data).
4. Selain implementasi, praktikum juga mencakup eksperimen dan analisis terhadap kedua teknik penanganan collision tersebut.

B. Tujuan Praktikum

Berdasarkan modul yang telah disediakan, tujuan dari praktikum ini adalah sebagai berikut:

1. Memahami prinsip dasar struktur data hash dan peran fungsi hash dalam pemetaan data.
2. Mengimplementasikan tabel hash dalam Python dengan penanganan collision menggunakan berbagai teknik, seperti linear probing dan separate chaining.
3. Melakukan operasi dasar pada tabel hash, termasuk penyisipan (insert), pencarian (search), dan penghapusan data.
4. Menganalisis kelebihan dan keterbatasan teknik hashing berdasarkan hasil implementasi dan pengujian.

Secara lebih rinci, melalui pengerjaan tugas soal 1 dan soal 2, mahasiswa secara spesifik bertujuan untuk:

• Soal 1 (Linear Probing) : Mengamati bagaimana collision ditangani dengan mencari slot kosong berurutan, serta memahami risiko clustering.
• Soal 2 (Chaining) : Mengamati bagaimana collision ditangani dengan menyimpan multiple item dalam satu slot menggunakan list, serta memahami fleksibilitas dan konsekuensi memorinya.

C. Hasil dan Analisis Praktikum

soal 1 :

class LinearProbingHashTable: 
    def __init__(self, size): 
        self.size = size 
        self.table = [None] * size 

    def hash_function(self, key): 
        return hash(key) % self.size 

    def insert(self, key, value): 
        index = self.hash_function(key) 
        original_index = index 
        while self.table[index] is not None: 
            if self.table[index][0] == key: 
                break 
            index = (index + 1) % self.size 
            if index == original_index: 
                raise Exception("Hash table penuh") 
        self.table[index] = (key, value) 

    def search(self, key): 
        index = self.hash_function(key) 
        original_index = index 
        while self.table[index] is not None: 
            if self.table[index][0] == key: 
                return self.table[index][1] 
            index = (index + 1) % self.size 
            if index == original_index: 
                break 
        return None 

jawaban a :

# a. Buat objek dengan ukuran tabel 5
ht = LinearProbingHashTable(5)

jawaban b :

# b. Masukkan 5 data
data = {"A": 10, "B": 20, "C": 30, "D": 40, "E": 50}
for key, value in data.items():
    ht.insert(key, value)
    print(f"Insert {key}:{value} | hash index = {ht.hash_function(key)}")

jawaban c :

# c. Cetak isi array self.table
print("\nIsi self.table setelah semua data dimasukkan:")
for i, slot in enumerate(ht.table):
    print(f"Indeks {i}: {slot}")

jawaban d :

Jika dua key memiliki hasil hash yang sama, maka terjadi collision (tabrakan) karena kedua key tersebut dipetakan ke indeks yang sama dalam tabel hash. Pada metode linear probing, ketika collision terjadi, data yang kedua tidak akan menimpa data pertama. Sebaliknya, sistem akan mencari slot kosong berikutnya secara berurutan (indeks +1, +2, dan seterusnya, dengan kembali ke awal tabel jika sudah mencapai akhir) hingga menemukan slot yang kosong. Setelah slot kosong ditemukan, data kedua akan disimpan di slot tersebut. Proses pencarian data nantinya juga akan mengikuti pola probing yang sama untuk menemukan key yang dicari.

Pada percobaan ini, tabel hash berukuran 5 diisi dengan 5 data menggunakan teknik linear probing untuk menangani collision. Data yang dimasukkan adalah “A”:10, “B”:20, “C”:30, “D”:40, dan “E”:50. Hasil hash menunjukkan bahwa key “A” dan “C” memiliki indeks yang sama yaitu 2, sehingga terjadi collision. Linear probing menangani hal ini dengan mencari slot kosong berikutnya, sehingga “C” ditempatkan di indeks 3. Berikut rincian hasil akhir tabel:

• Indeks 0 → (“B”, 20)
• Indeks 1 → (“D”, 40)
• Indeks 2 → (“A”, 10)
• Indeks 3 → (“C”, 30)
• Indeks 4 → (“E”, 50)

Kesimpulannya, linear probing berhasil menyimpan semua data tanpa ada yang tertimpa, namun metode ini berisiko menyebabkan clustering (penumpukan data berurutan) yang dapat memperlambat pencarian di masa mendatang.

output :

soal 2 :

class ChainingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

jawaban a :

# a. Gunakan ukuran tabel 3
ht = ChainingHashTable(3)

jawaban b :

# b. Masukkan key-value
data = {"apel": 100, "melon": 200, "lemon": 300, "pisang": 400}
print("Proses insert:")
for key, value in data.items():
    index = ht.hash_function(key)
    ht.insert(key, value)
    print(f"  Insert '{key}':{value} -> hash index = {index}")

jawaban c :

# c. Cetak isi tabel (self.table)
print("\nIsi self.table (seluruh slot):")
for i, slot in enumerate(ht.table):
    print(f"Slot {i}: {slot}")

# Menampilkan semua data per slot dengan rapi
print("\nData yang disimpan di setiap slot:")
for i, slot in enumerate(ht.table):
    if slot:
        print(f"Slot {i}: {[(k, v) for k, v in slot]}")
    else:
        print(f"Slot {i}: []")

jawaban d :

Dalam metode chaining, setiap slot pada tabel hash tidak hanya menyimpan satu nilai, melainkan berupa sebuah list (atau linked list) yang dapat menampung banyak pasangan key-value. Ketika terjadi collision (dua atau lebih key memiliki indeks hash yang sama), data baru tidak dipindahkan ke slot lain, melainkan langsung ditambahkan (append) ke dalam list yang sudah ada pada slot tersebut. Dengan kata lain, semua key yang mengalami collision akan disimpan bersama dalam satu slot sebagai kumpulan pasangan (key, value). Keuntungannya adalah tidak ada batasan jumlah data per slot dan tidak terjadi clustering, namun pencarian bisa menjadi lebih lambat jika satu slot menyimpan terlalu banyak data karena harus menelusuri list secara berurutan.

Pada percobaan ini, tabel hash berukuran 3 diisi dengan 4 data (“apel”:100, “melon”:200, “lemon”:300, “pisang”:400) menggunakan teknik chaining untuk menangani collision. Ketika dua key (apel dan melon) menghasilkan indeks hash yang sama (indeks 0), chaining menangani collision dengan menyimpan kedua data tersebut dalam satu list di slot yang sama tanpa memindahkan ke slot lain. Hasil akhir menunjukkan slot 0 berisi dua data sekaligus, sementara slot lainnya masing-masing berisi satu data.

Poin-poin penjelasan:

• Ukuran tabel: 3
• Data: “apel”:100, “melon”:200, “lemon”:300, “pisang”:400
• Collision: “apel” dan “melon” sama-sama memiliki hash index = 0
• Penanganan: Kedua data disimpan dalam satu list di slot 0 → [(‘apel’,100), (‘melon’,200)]
• Hasil akhir: Slot 0 = 2 data, Slot 1 = 1 data, Slot 2 = 1 data
• Kelebihan: Tidak ada clustering, fleksibel menampung banyak data per slot

output :

D. Kesimpulan

Berdasarkan praktikum yang telah dilakukan mengenai struktur data hashing, mulai dari implementasi hash table sederhana, penanganan collision dengan linear probing, hingga percobaan dengan teknik chaining, dapat ditarik beberapa kesimpulan sebagai berikut:

1. Hashing adalah teknik pemetaan key ke indeks array menggunakan fungsi hash, yang memungkinkan proses penyisipan dan pencarian data berlangsung sangat cepat, idealnya dalam waktu konstan O(1). Fungsi hash yang baik harus bersifat deterministik, menghasilkan sebaran merata (uniform distribution), dan efisien dalam perhitungan.
2. Collision (tabrakan) merupakan masalah yang tidak dapat dihindari dalam implementasi hash table, terutama ketika ukuran tabel terbatas atau fungsi hash kurang ideal. Collision terjadi ketika dua atau lebih key yang berbeda menghasilkan indeks hash yang sama.
3. Linear probing adalah salah satu teknik penanganan collision dengan cara mencari slot kosong berikutnya secara berurutan ketika terjadi tabrakan. Teknik ini sederhana dan hemat memori karena tidak memerlukan struktur data tambahan. Namun, kelemahannya adalah rentan terhadap clustering (penumpukan data pada area berurutan) yang dapat memperlambat kinerja pencarian seiring bertambahnya data.
4. Chaining adalah teknik penanganan collision di mana setiap slot hash table berupa list yang dapat menampung banyak pasangan key-value. Ketika terjadi collision, data baru langsung ditambahkan ke dalam list pada slot yang sama tanpa dipindahkan ke slot lain. Teknik ini lebih fleksibel, tidak mengalami masalah clustering, dan tidak membatasi jumlah data per slot. Namun, kelemahannya adalah membutuhkan memori tambahan untuk struktur list, serta pencarian bisa melambat jika satu slot menyimpan terlalu banyak data (worst case O(n)).
5. Pemilihan teknik penanganan collision harus disesuaikan dengan kebutuhan aplikasi. Linear probing cocok untuk sistem dengan keterbatasan memori dan beban data (load factor) yang relatif rendah. Sementara itu, chaining lebih sesuai untuk sistem yang mengutamakan fleksibilitas dan keandalan, serta dapat mengakomodasi jumlah data yang tidak diketahui sebelumnya.
6. Melalui praktikum ini, mahasiswa tidak hanya memahami konsep teoritis hashing, tetapi juga mampu mengimplementasikan secara langsung tiga jenis hash table (sederhana, linear probing, dan chaining) dalam bahasa Python, melakukan operasi dasar seperti insert dan search, serta menganalisis kelebihan dan keterbatasan masing-masing teknik berdasarkan hasil pengujian.

Dengan demikian, praktikum ini memberikan bekal yang cukup bagi mahasiswa untuk menerapkan struktur data hash table dalam pengembangan sistem nyata, seperti database indexing, sistem cache, lookup table, dan berbagai aplikasi yang memerlukan akses data cepat dan efisien.

sekian praktikum dari saya terimakasih ^^