Belajar Data Structure - Hash Table (Hash Map)

#Pendahuluan

Setelah di episode 6 kita memahami stack dan queue — dua struktur linear fundamental — pada episode ini kita mempelajari hash table (hash map), struktur data yang memungkinkan lookup, insert, dan delete dengan rata-rata O(1). Hash table mungkin adalah struktur data paling banyak digunakan dalam pemrograman sehari-hari — Python dict, JavaScript Object, Java HashMap semuanya berbasis hash table.

Tetapi O(1) itu rata-rata, bukan jaminan. Jika kalian memahami bagaimana hash table bekerja di balik layar — termasuk bagaimana collision ditangani dan kapan performa menurun — kalian akan bisa membuat keputusan yang lebih baik tentang kapan harus menggunakannya dan bagaimana mengoptimalkannya.

#Konsep Dasar

#Hash Function

Hash function mengubah input (key) menjadi index numerik. Index ini digunakan untuk menentukan lokasi key di dalam array (bucket). Hash function yang baik harus:

• Deterministic: input yang sama selalu menghasilkan output yang sama
• Uniform: distribusi output merata ke semua bucket
• Cepat: bisa dihitung dalam waktu O(1)

#Collision

Ketika dua key berbeda menghasilkan index yang sama, ini disebut collision. Ada dua pendekatan utama untuk menangani collision:

#Chaining

Setiap bucket menyimpan linked list dari semua elemen yang menghasilkan index yang sama. Ketika collision terjadi, elemen baru ditambahkan ke linked list di bucket tersebut.

#Open Addressing

Semua elemen disimpan langsung dalam array. Ketika collision terjadi, cari slot berikutnya yang kosong (probing). Variasi:

• Linear probing: cek slot berikutnya secara berurutan
• Quadratic probing: gunakan interval kuadratik (1, 4, 9, ...)
• Double hashing: gunakan hash function kedua untuk interval

#Perbandingan

#Load Factor dan Rehash

#Load Factor

Load factor = jumlah elemen / jumlah bucket. Ketika load factor melebihi threshold (biasanya 0.75), hash table melakukan rehash — membuat array baru dengan ukuran lebih besar, lalu memindahkan semua elemen ke posisi baru berdasarkan ukuran array baru.

#Rehash

Rehash adalah operasi O(n) yang mahal, tetapi jarang terjadi karena setiap rehash menggandakan kapasitas. Secara amortized, insert tetap O(1).

Load factor dan rehash threshold

# Load factor threshold
THRESHOLD = 0.75
 
# Jika current_size / capacity > THRESHOLD:
#   capacity *= 2
#   rehash semua elemen

#Aplikasi Hash Table

• Dictionary/object: penyimpanan key-value
• Frequency counting: menghitung kemunculan elemen
• Two-sum pattern: mencari pair dengan jumlah tertentu
• Grouping: mengelompokkan data berdasarkan key
• Caching: menyimpan hasil komputasi untuk akses cepat
• Set: Python set adalah hash table tanpa value

#Implementasi dari Nol

Hash table dengan chaining

class HashTable:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
 
    def _hash(self, key):
        return hash(key) % self.capacity
 
    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)
 
    def put(self, key, value):
        if self.size / self.capacity > 0.75:
            self._resize()
 
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
 
    def delete(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return
        raise KeyError(key)
 
    def _resize(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

#Testing

Testing hash table

ht = HashTable()
ht.put("name", "Alice")
ht.put("age", 30)
ht.put("city", "Jakarta")
 
print(ht.get("name"))
print(ht.get("age"))
print(ht.get("city"))
 
ht.delete("age")
print(ht.size)

#Worst Case: O(n)

Ketika semua key menghasilkan hash yang sama (misal karena hash function yang buruk), semua elemen masuk ke bucket yang sama → lookup menjadi O(n) karena harus traverse linked list. Inilah mengapa hash function yang baik sangat penting.

Di production, hash table modern menggunakan strategi canggih seperti randomized hashing dan tree-backed buckets (Java 8 HashMap) untuk mencegah DoS attacks yang memanfaatkan collision.

#Penutup

Inti yang harus dibawa pulang:

• Hash function mengubah key → index; collision ditangani dengan chaining atau open addressing.
• Load factor > threshold → rehash (gandakan kapasitas).
• Rata-rata O(1) untuk get/put/delete, worst case O(n).
• Aplikasi: dictionary, frequency counting, two-sum, grouping, caching.
• Implementasi dari nol: array + hash function + chaining.

Di episode 8 selanjutnya kita akan membahas priority queue dan binary heap — struktur data di mana elemen dengan prioritas tertinggi selalu di depan, termasuk min-heap, max-heap, insert (bubble up), dan extract (heapify down). Priority queue adalah fondasi untuk Dijkstra's algorithm yang akan kita bahas di fase graph nanti!