Struktur Data: Hashing

gambar 1

Hello hai! Di minggu kali ini, aku mau membahas tentang materi struktur data yang sudah aku pelajari yaitu hashing. Check this out!

Konsep Dasar Hashing

Dalam pemrograman, hashing merupakan salah satu teknik penting yang digunakan untuk menyimpan dan mengambil data secara efisien berdasarkan sebuah key. Dengan hashing, kita dapat mencari data dengan cepat tanpa harus menelusuri seluruh isi penyimpanannya. Cara kerja hashing yaitu dengan mengubah key menjadi sebuah angka dengan menggunakan fungsi hash, yang kemudian angka tersebut menjadi tempat penyimpanan data di dalam hash table.

gambar 2. cara kerja hash

Fungsi Hash

Fungsi hash adalah komponen inti dalam teknik hashing yang digunakan untuk mengubah key menjadi indeks dalam struktur penyimpanan seperti array. Kualitas fungsi hash sangat menentukan efisiensi dan akurasi proses penyimpanan data dan pencarian data. Oleh karena itu sebuah fungsi hash yang baik harus memiliki beberapa sifat penting:

• Deterministik: setiap input yang sama selalu menghasilkan indeks yang sama.
• Sebaran merata (uniform distribution): hasil hash dari sekumpulan key harus merata di seluruh slot tabel, agar tidak terjadi penumpukan di satu area.
• Efisien dihitung: proses perhitungan nilai hash harus cepat dan ringan, agar tidak mengurangi keunggulan performa.

Contoh sederhana dari fungsi hash dalam konteks numerik adalah operasi modulo (%). Misal, kita memiliki key berupa bilangan bulat dan ukuran tabel adalah 10, maka:

hash(key) = key % 10

Hasilnya adalah angka antara 0 hingga 9, yang dapat digunakan sebagai indeks untuk menyimpan data dalam array. Untuk tipe data non-numerik, fungsi hash akan mengubah karakternya menjadi bilangan ASCII, lalu menjumlahkannya dan kemudian dikonversi ke indeks dengan operasi modulo.

Permasalahan Collision

Salah satu tantangan utama hashing yaitu collision. Collision adalah kondisi ketika ada lebih dari 1 key yang menghasilkan indeks hash yang sama. Karena hash table memiliki jumlah slot yang terbatas, sangat memungkinkan beberapa key akan ditempatkan di indeks yang sama terutama jika tabelnya cukup kecil. Contoh, kita memiliki hash table dengan ukuran 5. Kemudian kita memasukkan key 10 dan 15, keduanya akan ditempatkan ke indeks 0.

Collision tidak dapat dihindari. Oleh karena itu, terdapat strategi penanganan collision (collision handling). Terdapat dua teknik utama yang umum digunakan untuk menangani collision:

• Linear Probing: Jika slot sudah terisi, maka akan mencari slot kosong berikutnya searah jarum jam secara berurutan hingga menemukan tempat yang tersedia.
• Chaining: Setiap slot tidak hanya menyimpan satu nilai, tetapi menyimpan koleksi nilai (biasanya dalam bentuk list atau linked list). Semua key yang mengalami collision di indeks yang sama akan disimpan bersama di struktur tersebut.

Linear probing lebih hemat memori tetapi rentan terhadap masalah clustering (penumpukan item di area tertentu). Sementara itu chaining lebih fleksibel dalam menampung banyak item di satu slot, namun memerulukan struktur data tambahan dan sedikit lebih kompleks.

Praktikum

1. Hash table sederhana

class SimpleHashTable: #membuat class bernama SimpleHashTable
  def __init__(self, size):
    self.size = size #menyimpan nilai size ke dalam objek
    self.table = [None] * size #membuat array kosong sebanyak ukuran tabel

  def hash_function(self, key): #hash key: fungsi untuk mengubah key menjadi index
    return hash(key) % self.size

  def insert(self, key, value): #insert: fungsi untuk menyimpan data
    index = self.hash_function(key) #memanggil fungsi hash  untuk mencari index
    self.table[index] = value #menyimpan  value ke index tersebut

  def search(self, key): #search: fungsi untuk mencari data berdasarkan kunci
    index = self.hash_function(key)
    return self.table[index]

#Contoh penggunaan
ht = SimpleHashTable(10) #hash table berukuran 10
ht.insert('apel', 100) #menyimpan key 'apel', valuenya 100
ht.insert('pisang', 200)

print("Nilai untuk 'apel':", ht.search('apel')) 
print("Nilai untuk 'pisang':", ht.search('pisang'))

Penjelasan: Hash table sederhana bekerja dengan cara mengubah key menjadi indeks menggunakan fungsi hash, kemudian value disimpan pada posisi indeks tersebut di dalam array. Ketika pencarian data dilakukan, key akan di-hash kembali agar diketahui lokasi penyimpanannya.

gambar 2. output 1

2. Penanganan Collision dengan Linear Probing

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

  def hash_function(self, key): #fungsi untuk mengubah key menjadi index
    return hash(key) % self.size #menghasilkan indeks dari key

  def insert(self, key, value): #fungsi untuk menyimpan data
    index = self.hash_function(key) #mencari indeks awal dari key
    original_index = index #menyimpan indeks awal

    while self.table[index] is not None: #jika indeks terisi, maka cari slot lain
      if self.table[index] [0] == key: #mengecek apakah ada yang sama dengan key
        break #jika key sama, maka loop berhenti dan data diperbarui
      index = (index + 1) % self.size #jika indeks penuh, pindah ke indeks berikutnya
      if index == original_index: #jika indeks sudah balik ke awal, berarti tabel sudah penuh
        raise Exception('Hash table penuh') #menampilkan error, hash table penuh

    self.table[index] = (key, value)

  def search(self, key): #fungsi untuk mencari data
    index = self.hash_function(key) #mencari indeks awal
    original_index = index #menyimpan indeks awal

    while self.table[index] is not None: #selama slot masih ada, terus cari data
      if self.table[index] [0] == key: #mengecek apakah key cocok
        return self.table[index] [1]
      index = (index + 1) % self.size #jika key belum ketemu, pindah ke indeks berikutnya
      if index == original_index: #jika tabel penuh
        break #stop pencarian
    return None

#Contoh penggunaan
ht = LinearProbingHashTable(5) #hash table berukuran 5
ht.insert('apel', 100)
ht.insert('pisang', 200)
ht.insert('melon', 300)

print("Nilai untuk 'apel: ", ht.search('apel'))
print("Nilai untuk 'melon': ", ht.search('melon'))

gambar 3. output 2

Penjelasan: Kode tersebut merupakan hash table dengan menggunakan metode linear probing untuk mengatasi masalah collision. Jika dua key memiliki indeks yang sama, maka data baru tidak akan langsung menimpa data lama, melainkan akan mencari slot kosong berikutnya secara berurutan hingga menemukan tempat kosong.

3. Penanganan Collision dengan Chaining

class ChainingHashTable: 
  def __init__(self, size):
    self.size = size
    self.table = [[] for _ in range(size)] #membuat list kosong di setiap indeks

  def hash_function(self, key): #fungsi untuk mengubah key menjadi indeks
    return hash(key) % self.size

  def insert(self, key, value): #fungsi untuk menyimpan data
    index = self.hash_function(key)
    for i, (k, v) in enumerate(self.table[index]): #loop semua data yang ada di indeks tersebut
      if k == key: #mengecek apakah key sudah ada
        self.table[index] [i] = (key, value) #jika key sudha ada, data lama diupdate
        return
    self.table[index].append((key, value)) #jika key belum ada, data ditambahkan ke list pd indeks

  def search(self, key): #fungsi untuk mencari data
    index = self.hash_function(key) #mencari indeks key
    for k, v in self.table[index]: #loop semua data pada indeks tersebt
      if k == key: #mengecek apakah key cocok
        return v #jika cocok, fungsi mengembalikan value
    return None

#COntoh penggunaan
ht = ChainingHashTable(5) #hash table berukuran 5
ht.insert('apel', 100)
ht.insert('pisang', 200)
ht.insert('melon', 300)

print("Nilai untuk 'apel': ", ht.search('apel'))
print("Nilai untuk 'melon': ", ht.search('melon'))

gambar 4. output 3

Penjelasan: Kode tersebut merupakan hash table dengan metode chaining untuk menangani collision. Jika beberapa key memiliki indeks yang sama, data tidak akan dipindah ke slot lain, melainkan tetap disimpan bersama dalam sebuah list pada indeks tersebut. Saat pencarian data, program akan menelusuri isi list dalam indeks.

Tugas

1. Eksperimen sederhana linear probing

Instruksi:

• Buat objek LinearProbingHashTable dengan ukuran tabel 5
• Masukkan pasangan key-value: “A”: 10, “B”: 20, “C”: 30, “D”: 40, “E”: 50
• Cetak isi array self.table
• Jelaskan apa yang terjadi jika dua key memiliki hasil hash yang sama.

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: 
      index = (index + 1) % self.size 
      if index == original_index: 
        raise Exception('Hash table penuh') 

    self.table[index] = (key, value)

ht = LinearProbingHashTable(5)
ht.insert('A', 10)
ht.insert('B', 20)
ht.insert('C', 30)
ht.insert('D', 40)
ht.insert('E', 50)

print(ht.table)

gambar 5. output 4

Bagaimana jika ada dua key memiliki hasil hash yang sama? Seperti yang sudah aku tulis di atas, jika dua key memiliki hasil hash yang sama (collision), maka data baru tidak akan langsung ditimpa, melainkan akan mencari slot kosong berikutnya secara urut hingga menemukan tempat kosong.

2. Percobaan Dasar Chaining

Instruksi:

• Gunakan ukuran tabel 3
• Masukkan key-value: “apel”: 100, “melon”: 200, “lemon”: 300, “pisang”: 400
• Cetak isi tabel dan tampilkan semua data yang disimpan di setiap slot
• Jelaskan bagaimana collision ditangani dalam bentuk metode chaining

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)
    self.table[index].append((key, value))

ht = ChainingHashTable(3)
ht.insert('apel', 100)
ht.insert('melon', 200)
ht.insert('lemon', 300)
ht.insert('pisang', 400)

print(ht.table)

gambar 6. output 5

Bagaimana collision ditangani dalam metode chaining? Collision ditangani dengan cara menyimpan data di dalam list pada indeks yang sama.

And yeah that’s all untuk materi hashing. Thanks for reading and see u next week!

Github: https://github.com/Rosifaaulia/Praktikum-Struktur-Data.git

gambar 7.