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.

// TwoSumHashMap mencari indeks dua angka yang jika dijumlahkan sama dengan target
// Kompleksitas Waktu: O(n) - satu pass melalui array
// Kompleksitas Ruang: O(n) - menyimpan hingga n elemen dalam map
func TwoSumHashMap(nums []int, target int) []int {
    // Map untuk menyimpan nilai yang sudah dilihat dan indeksnya
    seen := make(map[int]int)
    
    for i, num := range nums {
        // Hitung complement yang diperlukan
        complement := target - num
        
        // Cek apakah complement ada di map
        if idx, found := seen[complement]; found {
            // Kita menemukan pasangan!
            return []int{idx, i}
        }
        
        // Simpan nilai current dan indeksnya untuk iterasi berikutnya
        seen[num] = i
    }
    
    return []int{}
}

// GroupAnagrams mengelompokkan string yang merupakan anagram
// Kompleksitas Waktu: O(n * k log k) dimana n adalah jumlah string, k adalah panjang string terpanjang
// Kompleksitas Ruang: O(n * k) untuk menyimpan semua string
func GroupAnagrams(strs []string) [][]string {
    // Map dengan sorted string sebagai key
    groups := make(map[string][]string)
    
    for _, str := range strs {
        // Sort string untuk mendapatkan signature yang sama untuk anagram
        // Contoh: "eat" dan "tea" keduanya menjadi "aet"
        sorted := sortString(str)
        
        // Tambahkan ke group yang sesuai
        groups[sorted] = append(groups[sorted], str)
    }
    
    // Convert map ke slice of slices
    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    
    return result
}

// Helper function untuk sort string
func sortString(s string) string {
    runes := []rune(s)
    // Simple bubble sort untuk demonstration
    for i := 0; i < len(runes); i++ {
        for j := i + 1; j < len(runes); j++ {
            if runes[i] > runes[j] {
                runes[i], runes[j] = runes[j], runes[i]
            }
        }
    }
    return string(runes)
}

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.

// DListNode untuk doubly linked list
type DListNode struct {
    Key   int
    Value int
    Prev  *DListNode
    Next  *DListNode
}

// LRUCache mengimplementasikan Least Recently Used cache
type LRUCache struct {
    capacity int
    cache    map[int]*DListNode
    head     *DListNode // Dummy head (most recent)
    tail     *DListNode // Dummy tail (least recent)
}

// NewLRUCache membuat LRU cache baru
func NewLRUCache(capacity int) *LRUCache {
    // Buat dummy nodes untuk mempermudah operasi
    head := &DListNode{}
    tail := &DListNode{}
    head.Next = tail
    tail.Prev = head
    
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*DListNode),
        head:     head,
        tail:     tail,
    }
}

// Get mengambil value dari cache
// Kompleksitas Waktu: O(1)
// Kompleksitas Ruang: O(1)
func (lru *LRUCache) Get(key int) int {
    if node, found := lru.cache[key]; found {
        // Move node ke head (mark sebagai recently used)
        lru.moveToHead(node)
        return node.Value
    }
    return -1
}

// Put menambahkan atau update key-value di cache
// Kompleksitas Waktu: O(1)
// Kompleksitas Ruang: O(1)
func (lru *LRUCache) Put(key int, value int) {
    if node, found := lru.cache[key]; found {
        // Key sudah ada, update value dan move ke head
        node.Value = value
        lru.moveToHead(node)
        return
    }
    
    // Key baru, buat node baru
    newNode := &DListNode{Key: key, Value: value}
    lru.cache[key] = newNode
    lru.addToHead(newNode)
    
    // Cek apakah melebihi capacity
    if len(lru.cache) > lru.capacity {
        // Hapus node paling jarang digunakan (tail)
        removed := lru.removeTail()
        delete(lru.cache, removed.Key)
    }
}

// addToHead menambahkan node tepat setelah dummy head
func (lru *LRUCache) addToHead(node *DListNode) {
    node.Prev = lru.head
    node.Next = lru.head.Next
    lru.head.Next.Prev = node
    lru.head.Next = node
}

// removeNode menghapus node dari posisi saat ini
func (lru *LRUCache) removeNode(node *DListNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

// moveToHead memindahkan node ke head (mark sebagai recently used)
func (lru *LRUCache) moveToHead(node *DListNode) {
    lru.removeNode(node)
    lru.addToHead(node)
}

// removeTail menghapus dan return node sebelum dummy tail
func (lru *LRUCache) removeTail() *DListNode {
    node := lru.tail.Prev
    lru.removeNode(node)
    return node
}

func main() {
    // Test HashMap
    fmt.Println("HashMap Tests:")
    hm := NewHashMap(10)
    hm.Put("apple", 5)
    hm.Put("banana", 3)
    hm.Put("orange", 7)
    
    if val, found := hm.Get("apple"); found {
        fmt.Printf("apple: %d\n", val) // 5
    }
    
    fmt.Printf("Size: %d, Load Factor: %.2f\n", hm.Size(), hm.LoadFactor())
    
    // Test Two Sum
    fmt.Println("\nTwo Sum Tests:")
    nums := []int{2, 7, 11, 15}
    result := TwoSumHashMap(nums, 9)
    fmt.Printf("Indices: %v\n", result) // [0 1]
    
    // Test Group Anagrams
    fmt.Println("\nGroup Anagrams Tests:")
    strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
    groups := GroupAnagrams(strs)
    fmt.Printf("Anagram groups: %v\n", groups)
    
    // Test LRU Cache
    fmt.Println("\nLRU Cache Tests:")
    cache := NewLRUCache(2)
    cache.Put(1, 1)
    cache.Put(2, 2)
    fmt.Printf("Get 1: %d\n", cache.Get(1))       // returns 1
    cache.Put(3, 3)                                // evicts key 2
    fmt.Printf("Get 2: %d\n", cache.Get(2))       // returns -1 (not found)
    cache.Put(4, 4)                                // evicts key 1
    fmt.Printf("Get 1: %d\n", cache.Get(1))       // returns -1 (not found)
    fmt.Printf("Get 3: %d\n", cache.Get(3))       // returns 3
    fmt.Printf("Get 4: %d\n", cache.Get(4))       // returns 4
}

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.