Panduan untuk Pemula: Hashing dalam DBMS

Halo, para ahli basis data masa depan! Hari ini, kita akan melihat dunia magis hashing dalam Sistem Manajemen Basis Data (DBMS). Jangan khawatir jika Anda belum pernah menulis baris kode sebelumnya - saya akan menjadi panduan Anda dalam perjalanan ini. mari grab perisai virtual Anda (papan ketik), dan mari kita mulai!

Apa Itu Hashing?

Sebelum kita masuk ke detailnya, mari kita memahami apa itu hashing. Bayangkan Anda sedang mengatur perpustakaan besar. Daripada menempatkan buku-buku secara alfabetis, Anda memutuskan untuk memberikan setiap buku nomor unik berdasarkan judulnya. Itu sebenarnya apa yang hashing lakukan dalam basis data - itu mengkonversi data menjadi nilai ukuran tetap (disebut hash) untuk penyimpanan dan pengambilan yang mudah.

Contoh Hashing Sederhana

mari mulai dengan contoh Python sederhana 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 sangat sederhana. Itu menjumlahkan nilai ASCII setiap karakter dalam string dan kemudian menggunakan operator modulo untuk mendapatkan nomor antara 0 dan 9. Ini adalah bentuk yang sangat sederhana dari hashing, tetapi itu memberikan Anda ide tentang bagaimana itu bekerja.

Organisasi Hashing

Sekarang kita memiliki pemahaman 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 khusus di mana setiap elemen (sering disebut bucket) dapat menyimpan banyak item.

Ini 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.

Hashing Statis

Hashing statis seperti memiliki jumlah tetap rak di perpustakaan Anda. Anda tahu secara pasti berapa banyak buku yang dapat Anda simpan, tetapi Anda mungkin mengalami masalah jika Anda mendapat terlalu banyak buku tentang satu topik.

Pros dan Kontra Hashing Statis

Pros	Kontra
Mudah untuk implementasi	Dapat menyebabkan distribusi yang tidak merata
Cepat untuk dataset kecil	Tidak fleksibel untuk dataset yang tumbuh
Kinerja yang dapat diprediksi	Mungkin membuang ruang

Overflow Bucket

Kadang-kadang, fungsi hash kita mungkin mengirimkan terlalu banyak item ke dalam satu bucket. Ini disebut overflow bucket, dan itu seperti mencoba memasukkan terlalu banyak buku ke dalam 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.

mari implementasikan chaining di 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 menahan banyak pasangan key-value, memecahkan masalah overflow.

Hashing Dinamis

Hashing dinamis seperti memiliki perpustakaan yang dapat tumbuh rak baru saat Anda membutuhkannya. Itu lebih fleksibel daripada hashing statis dan dapat menyesuaikan dengan dataset yang tumbuh.

Hashing Ekstensibel

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

Ini adalah implementasi sederhana hashing 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 baru ditambahkan.

Organisasi dan Operasi

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

Operasi	Kompleksitas Waktu Rata-rata	Kasus Terburuk
Masukkan	O(1)	O(n)
Hapus	O(1)	O(n)
Pencarian	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 dalam satu bucket), kinerja dapat menurun menjadi seperti daftar terhubung.

Kesimpulan

Selamat! Anda telah mengambil langkah pertama ke dunia hashing dalam DBMS. Ingat, hashing tentang menemukan keseimbangan antara kecepatan dan ruang. Itu adalah alat yang kuat yang, saat digunakan dengan benar, dapat meningkatkan operasi basis data Anda secara signifikan.

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

Terus latih, tetap curiga, dan kodingsenang!

Credits: Image by storyset