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:
Hash Map: Memberikan akses O(1) ke node berdasarkan key
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.
Last updated