DBMS - Hashing: A Panduan untuk Pemula

Hai, para ahli basis data masa depan! Hari ini, kita akan melihat dunia yang magis dari hashing dalam Sistem Manajemen Basis Data (DBMS). Jangan khawatir jika Anda belum pernah menulis baris kode sebelumnya - saya akan menjadi panduan yang ramah untuk Anda dalam perjalanan ini. Jadi, ambil keyboard virtual Anda (tikus), dan mari kita mulai!

Apa Itu Hashing?

Sebelum kita masuk ke detail, mari kita pahami apa itu hashing. Bayangkan Anda mengatur pustaka besar. instead of arranging books alphabetically, Anda memutuskan untuk memberi setiap buku nomor unik berdasarkan judulnya. Itu sebenarnya apa yang hashing lakukan dalam basis data - itu mengkonversi data ke nilai ukuran tetap (disebut hash) untuk penyimpanan dan pengambilan yang mudah.

Contoh Hashing Sederhana

Marilah kita mulai dengan contoh Python dasar untuk mengilustrasikan hashing:

def simple_hash(string):
total = 0
for char in string:
total += ord(char)
return total % 10

print(simple_hash("Hello"))  # Output: 2
print(simple_hash("World"))  # Output: 7

Dalam contoh ini, kita membuat fungsi hash yang sangat sederhana. Itu menambahkan nilai ASCII setiap karakter dalam string dan kemudian menggunakan operator modulo untuk mendapatkan nomor antara 0 dan 9. Ini adalah bentuk yang sangat dasar dari hashing, tetapi itu memberikan Anda gambaran tentang bagaimana itu bekerja.

Organisasi Hash

Sekarang kita memiliki pengetahuan dasar tentang hashing, mari kita lihat bagaimana itu diatur dalam basis data.

Tabel Hash

Tabel hash adalah tulang punggung organisasi hash. Bayangkan tabel hash sebagai array yang kaya di mana setiap elemen (sering disebut bucket) dapat menyimpan banyak item.

Berikut adalah implementasi sederhana tabel hash dalam Python:

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

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

def insert(self, key, value):
hash_key = self.hash_function(key)
self.table[hash_key].append((key, value))

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

# Menggunakan tabel hash kita
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # Output: 5
print(ht.get("grape"))  # Output: None

Tabel hash ini menggunakan fungsi hash() bawaan Python dan modulo untuk menentukan di mana menyimpan setiap pasangan key-value. Ketika kita ingin mengambil nilai, kita menggunakan proses yang sama untuk menemukan di mana itu disimpan.

Hash Statis

Hash statis seperti memiliki jumlah tetap rak di pustaka Anda. Anda tahu tepat berapa banyak buku yang dapat Anda simpan, tetapi Anda mungkin mengalami masalah jika Anda mendapat terlalu banyak buku tentang satu topik.

Pros dan Cons Hash Statis

Pros	Cons
Mudah untuk implementasi	Dapat menyebabkan distribusi yang tidak rata
Cepat untuk dataset kecil	Tidak fleksibel untuk dataset yang tumbuh
Performa yang dapat diprediksi	Mungkin menghabiskan ruang

Overflow Bucket

kadang-kadang, fungsi hash kita mungkin mengirimkan terlalu banyak item ke bucket yang sama. Ini disebut overflow bucket, dan itu seperti mencoba memaksa terlalu banyak buku ke satu rak.

Menangani Overflow

Ada beberapa cara untuk menangani overflow:

1. Chaining: Setiap bucket berisi daftar terhubung dari entri.
2. Open Addressing: Jika bucket penuh, kita mencari bucket kosong berikutnya.

Marilah kita implementasikan chaining dalam tabel hash sebelumnya:

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

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

def insert(self, key, value):
hash_key = self.hash_function(key)
for item in self.table[hash_key]:
if item[0] == key:
item[1] = value
return
self.table[hash_key].append([key, value])

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

# Menggunakan tabel hash berantai kita
cht = ChainedHashTable(10)
cht.insert("apple", 5)
cht.insert("banana", 7)
cht.insert("cherry", 3)
print(cht.get("apple"))  # Output: 5
print(cht.get("cherry"))  # Output: 3

Dalam implementasi ini, setiap bucket dapat menampung beberapa pasangan key-value, memecahkan masalah overflow.

Hash Dinamis

Hash dinamis seperti memiliki pustaka ajaib yang tumbuh rak baru saat Anda membutuhkannya. Itu lebih fleksibel daripada hash statis dan dapat menyesuaikan dengan dataset yang tumbuh.

Hash Ekstensibel

Salah satu bentuk hash dinamis populer adalah hash ekstensibel. Itu menggunakan struktur direktori yang dapat tumbuh atau menyusut sesuai kebutuhan.

Berikut adalah implementasi sederhana hash ekstensibel:

class ExtendibleHashTable:
def __init__(self, bucket_size=2):
self.bucket_size = bucket_size
self.global_depth = 1
self.directory = [[] for _ in range(2**self.global_depth)]

def hash_function(self, key):
return hash(key) % (2**self.global_depth)

def insert(self, key, value):
hash_key = self.hash_function(key)
if len(self.directory[hash_key]) < self.bucket_size:
self.directory[hash_key].append((key, value))
else:
self._split(hash_key)
self.insert(key, value)

def _split(self, index):
self.global_depth += 1
new_directory = [[] for _ in range(2**self.global_depth)]
for i, bucket in enumerate(self.directory):
new_index = i if i < index else i + 2**(self.global_depth-1)
new_directory[new_index] = bucket
self.directory = new_directory

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.directory[hash_key]:
if k == key:
return v
return None

# Menggunakan tabel hash ekstensibel kita
eht = ExtendibleHashTable()
eht.insert("apple", 5)
eht.insert("banana", 7)
eht.insert("cherry", 3)
eht.insert("date", 9)
print(eht.get("apple"))  # Output: 5
print(eht.get("date"))   # Output: 9

Implementasi ini memungkinkan tabel hash untuk tumbuh secara dinamis saat item ditambahkan.

Organisasi dan Operasi

Sekarang kita telah melihat dasar-dasar hashing dan beberapa implementasi, mari kita ringkaskan operasi kunci dan kompleksitas waktunya:

Operasi	Kompleksitas Waktu Rata-Rata	Kasus Terburuk
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Search	O(1)	O(n)

Kasus rata-rata biasanya sangat cepat, itu adalah sebabnya hashing sangat populer. Namun, dalam kasus terburuk (ketika semua item hash ke bucket yang sama), performa dapat menurun ke tingkat daftar terhubung.

Kesimpulan

Selamat! Anda baru saja mengambil langkah pertama Anda ke dunia hashing dalam DBMS. Ingat, hashing tentang mencari keseimbangan antara kecepatan dan ruang. Ini adalah alat yang kuat yang, jika digunakan dengan benar, dapat meningkatkan signifikan operasi basis data Anda.

Sebagai Anda terus melanjutkan perjalanan Anda dalam ilmu komputer, Anda akan menemukan hashing dalam banyak konteks lain - dari penyimpanan password hingga sistem caching. Setiap kali Anda menggunakan dictionary di Python atau objek di JavaScript, Anda sedang mendapatkan keuntungan dari keajaiban hashing!

Terus latihan, tetap curiga, dan selamat coding!

Credits: Image by storyset