Hash Tables (Maps)

Section 4: Hash Tables (Maps)

Penjelasan Konsep

Hash table adalah struktur data yang menyimpan pasangan key-value dengan akses yang sangat cepat. Bayangkan seperti perpustakaan yang sangat terorganisir di mana Anda bisa langsung melompat ke lokasi buku tertentu tanpa perlu mencari satu per satu. Hash table menggunakan fungsi hash yang mengkonversi key menjadi indeks array, memungkinkan akses O(1) dalam kasus rata-rata.

Konsep pentingnya adalah hash collision, ketika dua key berbeda menghasilkan hash value yang sama. Ini ditangani dengan teknik seperti chaining (menggunakan linked list di setiap bucket) atau open addressing (mencari slot kosong berikutnya).

Kompleksitas Operasi

Dalam kasus rata-rata, operasi insert, delete, dan lookup pada hash table memiliki kompleksitas O(1). Namun dalam kasus terburuk (banyak collision), kompleksitas bisa turun menjadi O(n). Load factor, yaitu rasio jumlah elemen terhadap jumlah bucket, mempengaruhi performa. Hash table yang baik akan melakukan rehashing ketika load factor melewati threshold tertentu.

Contoh Implementasi

package main

import "fmt"

// HashNode merepresentasikan node dalam chaining
type HashNode struct {
    Key   string
    Value int
    Next  *HashNode
}

// HashMap adalah implementasi hash table dengan chaining
type HashMap struct {
    buckets []*HashNode
    size    int
    capacity int
}

// NewHashMap membuat hash map baru
func NewHashMap(capacity int) *HashMap {
    return &HashMap{
        buckets:  make([]*HashNode, capacity),
        size:     0,
        capacity: capacity,
    }
}

// hash function sederhana
// Kompleksitas Waktu: O(k) dimana k adalah panjang key
func (hm *HashMap) hash(key string) int {
    hashValue := 0
    for _, char := range key {
        hashValue = (hashValue*31 + int(char)) % hm.capacity
    }
    return hashValue
}

// Put menambahkan atau update key-value pair
// Kompleksitas Waktu: O(1) average, O(n) worst case jika banyak collision
// Kompleksitas Ruang: O(1)
func (hm *HashMap) Put(key string, value int) {
    index := hm.hash(key)
    
    // Cek apakah key sudah ada (update case)
    current := hm.buckets[index]
    for current != nil {
        if current.Key == key {
            current.Value = value
            return
        }
        current = current.Next
    }
    
    // Key belum ada, insert di awal chain (insert case)
    newNode := &HashNode{
        Key:   key,
        Value: value,
        Next:  hm.buckets[index],
    }
    hm.buckets[index] = newNode
    hm.size++
}

// Get mengambil value berdasarkan key
// Kompleksitas Waktu: O(1) average, O(n) worst case
// Kompleksitas Ruang: O(1)
func (hm *HashMap) Get(key string) (int, bool) {
    index := hm.hash(key)
    
    current := hm.buckets[index]
    for current != nil {
        if current.Key == key {
            return current.Value, true
        }
        current = current.Next
    }
    
    return 0, false
}

// Delete menghapus key-value pair
// Kompleksitas Waktu: O(1) average, O(n) worst case
// Kompleksitas Ruang: O(1)
func (hm *HashMap) Delete(key string) bool {
    index := hm.hash(key)
    
    // Kasus khusus: head adalah yang akan dihapus
    if hm.buckets[index] != nil && hm.buckets[index].Key == key {
        hm.buckets[index] = hm.buckets[index].Next
        hm.size--
        return true
    }
    
    // Traverse chain untuk mencari key
    current := hm.buckets[index]
    for current != nil && current.Next != nil {
        if current.Next.Key == key {
            current.Next = current.Next.Next
            hm.size--
            return true
        }
        current = current.Next
    }
    
    return false
}

// Size mengembalikan jumlah elemen
func (hm *HashMap) Size() int {
    return hm.size
}

// LoadFactor menghitung rasio elemen terhadap bucket
func (hm *HashMap) LoadFactor() float64 {
    return float64(hm.size) / float64(hm.capacity)
}

Studi Kasus: Two Sum dengan Hash Map

Problem ini mendemonstrasikan kekuatan hash map untuk mengoptimasi pencarian. Dibandingkan dengan two pointers yang memerlukan sorting, pendekatan hash map bisa bekerja pada array yang tidak terurut.

Studi Kasus: LRU Cache

LRU (Least Recently Used) Cache adalah struktur data yang menggabungkan hash map dan doubly linked list untuk memberikan akses O(1) dengan eviction policy yang efisien. Ini sangat umum digunakan dalam sistem caching seperti browser cache, database cache, dan CDN.

Penjelasan Kompleksitas LRU Cache

LRU Cache mencapai kompleksitas O(1) untuk kedua operasi Get dan Put dengan menggabungkan dua struktur data:

  1. Hash Map: Memberikan akses O(1) ke node berdasarkan key

  2. Doubly Linked List: Memungkinkan penghapusan dan penambahan node di posisi mana pun dalam O(1)

Doubly linked list digunakan karena kita perlu bisa menghapus node dari tengah list (ketika item diakses dan perlu dipindah ke depan) dalam O(1). Dengan singly linked list, kita perlu traverse untuk menemukan node sebelumnya yang akan memakan O(n). Dummy head dan tail nodes mempermudah edge case handling sehingga kita tidak perlu cek null pointer.

PreviousStack dan QueueNextLRU Cache

Last updated