Maps

Understanding Maps in Go

Hash Table Implementation

Maps in Go are hash tables that provide O(1) average-case lookup, insertion, and deletion. They're implemented as a hash table with buckets, where each bucket can hold up to 8 key-value pairs. When buckets overflow, they chain to overflow buckets.

Map Fundamentals

Declaration and Initialization

Maps must be initialized before use. A nil map panics on write but returns zero value on read. Understanding the difference between nil maps, empty maps, and maps with capacity is crucial.

// Various ways to create maps
var m1 map[string]int           // nil map - read-only!
m2 := make(map[string]int)      // empty map
m3 := make(map[string]int, 100) // with initial space for ~100 items

// Map literal
ages := map[string]int{
    "Alice": 30,
    "Bob":   25,
    "Carol": 35,
}

// Complex key types
type Point struct{ X, Y int }
grid := map[Point]string{
    {0, 0}: "origin",
    {1, 1}: "diagonal",
}

// Map with interface{} values
data := map[string]interface{}{
    "name":  "John",
    "age":   30,
    "active": true,
}

Basic Operations

Map operations in Go are straightforward but have important nuances. The two-value assignment form is idiomatic for checking existence, and the zero value behavior is predictable.

// Setting values
users := make(map[string]User)
users["u123"] = User{Name: "Alice"}

// Getting values - always check existence
user, exists := users["u123"]
if exists {
    fmt.Println("Found:", user.Name)
}

// Delete operation
delete(users, "u123")  // Safe even if key doesn't exist

// Zero value behavior
counts := map[string]int{}
counts["apples"]++  // Works! Zero value of int is 0

// Length
fmt.Println("Map size:", len(counts))

Iteration and Ordering

Range Loops

Map iteration order is deliberately randomized in Go to prevent dependence on unspecified behavior. Each iteration may produce a different order, even for the same map.

// Basic iteration
scores := map[string]int{"Alice": 95, "Bob": 87, "Carol": 92}

for name, score := range scores {
    fmt.Printf("%s: %d\n", name, score)
}

// Keys only
for name := range scores {
    fmt.Println("Student:", name)
}

// Sorted iteration
import "sort"

func sortedMapKeys(m map[string]int) []string {
    keys := make([]string, 0, len(m))
    for k := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    return keys
}

// Use sorted keys
for _, name := range sortedMapKeys(scores) {
    fmt.Printf("%s: %d\n", name, scores[name])
}

Advanced Map Patterns

Map of Slices

Maps combined with slices create powerful data structures for grouping and categorization. This pattern is common for building indexes and grouping related data.

// Grouping pattern
type Student struct {
    Name  string
    Grade string
}

func groupByGrade(students []Student) map[string][]Student {
    groups := make(map[string][]Student)
    for _, s := range students {
        groups[s.Grade] = append(groups[s.Grade], s)
    }
    return groups
}

// Multi-value map pattern
type MultiMap map[string][]string

func (m MultiMap) Add(key, value string) {
    m[key] = append(m[key], value)
}

func (m MultiMap) Get(key string) []string {
    return m[key]  // Returns nil if key doesn't exist
}

Nested Maps

Nested maps require careful initialization. Each level must be created before use, leading to verbose code that can be simplified with helper functions.

// 2D sparse matrix using nested maps
type SparseMatrix map[int]map[int]float64

func NewSparseMatrix() SparseMatrix {
    return make(SparseMatrix)
}

func (m SparseMatrix) Set(row, col int, val float64) {
    if m[row] == nil {
        m[row] = make(map[int]float64)
    }
    m[row][col] = val
}

func (m SparseMatrix) Get(row, col int) float64 {
    if rowMap, ok := m[row]; ok {
        return rowMap[col]
    }
    return 0  // Default value for sparse matrix
}

// Tree structure using maps
type TreeNode map[string]interface{}

func setPath(root TreeNode, path []string, value interface{}) {
    node := root
    for i, key := range path {
        if i == len(path)-1 {
            node[key] = value
        } else {
            if node[key] == nil {
                node[key] = make(TreeNode)
            }
            node = node[key].(TreeNode)
        }
    }
}

Concurrency and Maps

Thread Safety

Maps are not safe for concurrent access. Concurrent reads are safe, but any concurrent write (including delete) requires synchronization. Go provides multiple approaches for thread-safe map access.

// Option 1: Mutex-protected map
type SafeMap struct {
    mu sync.RWMutex
    m  map[string]int
}

func NewSafeMap() *SafeMap {
    return &SafeMap{
        m: make(map[string]int),
    }
}

func (sm *SafeMap) Get(key string) (int, bool) {
    sm.mu.RLock()
    defer sm.mu.RUnlock()
    val, ok := sm.m[key]
    return val, ok
}

func (sm *SafeMap) Set(key string, value int) {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    sm.m[key] = value
}

func (sm *SafeMap) Increment(key string) int {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    sm.m[key]++
    return sm.m[key]
}

// Option 2: sync.Map (for specific use cases)
var cache sync.Map

// Store
cache.Store("key1", "value1")

// Load
if val, ok := cache.Load("key1"); ok {
    fmt.Println("Found:", val)
}

// LoadOrStore
actual, loaded := cache.LoadOrStore("key2", "default")

// LoadAndDelete (Go 1.15+)
val, loaded := cache.LoadAndDelete("key1")

// Range
cache.Range(func(key, value interface{}) bool {
    fmt.Printf("%v: %v\n", key, value)
    return true  // Continue iteration
})

Channel-Based Map Access

For complex scenarios, using channels to serialize map access provides a clean, goroutine-safe interface without explicit locking.

// Map server pattern
type MapOp struct {
    action string  // "get", "set", "delete"
    key    string
    value  int
    resp   chan<int>
}

func mapServer(ops chan MapOp) {
    m := make(map[string]int)
    for op := range ops {
        switch op.action {
        case "get":
            op.resp <- m[op.key]
        case "set":
            m[op.key] = op.value
        case "delete":
            delete(m, op.key)
        }
    }
}

Common Patterns and Use Cases

Set Implementation

Go doesn't have a built-in set type, but maps with empty struct values provide an efficient implementation with O(1) membership testing.

// Set using map[T]struct{}
type StringSet map[string]struct{}

func NewStringSet(items ...string) StringSet {
    s := make(StringSet)
    for _, item := range items {
        s[item] = struct{}{}
    }
    return s
}

func (s StringSet) Add(item string) {
    s[item] = struct{}{}
}

func (s StringSet) Contains(item string) bool {
    _, ok := s[item]
    return ok
}

func (s StringSet) Remove(item string) {
    delete(s, item)
}

func (s StringSet) Union(other StringSet) StringSet {
    result := NewStringSet()
    for k := range s {
        result.Add(k)
    }
    for k := range other {
        result.Add(k)
    }
    return result
}

func (s StringSet) Intersection(other StringSet) StringSet {
    result := NewStringSet()
    for k := range s {
        if other.Contains(k) {
            result.Add(k)
        }
    }
    return result
}

Caching and Memoization

Maps are perfect for implementing caches and memoization, storing computed results to avoid redundant calculations.

// Simple cache with expiration
type CacheItem struct {
    value      interface{}
    expiration time.Time
}

type Cache struct {
    mu    sync.RWMutex
    items map[string]CacheItem
}

func NewCache() *Cache {
    return &Cache{
        items: make(map[string]CacheItem),
    }
}

func (c *Cache) Set(key string, value interface{}, ttl time.Duration) {
    c.mu.Lock()
    defer c.mu.Unlock()
    
    c.items[key] = CacheItem{
        value:      value,
        expiration: time.Now().Add(ttl),
    }
}

func (c *Cache) Get(key string) (interface{}, bool) {
    c.mu.RLock()
    defer c.mu.RUnlock()
    
    item, found := c.items[key]
    if !found {
        return nil, false
    }
    
    if time.Now().After(item.expiration) {
        go c.delete(key)  // Lazy deletion
        return nil, false
    }
    
    return item.value, true
}

// Memoization decorator
func memoize(fn func(int) int) func(int) int {
    cache := make(map[int]int)
    var mu sync.RWMutex
    
    return func(n int) int {
        mu.RLock()
        if val, ok := cache[n]; ok {
            mu.RUnlock()
            return val
        }
        mu.RUnlock()
        
        result := fn(n)
        
        mu.Lock()
        cache[n] = result
        mu.Unlock()
        
        return result
    }
}

Performance and Optimization

Performance Characteristics

Memory Optimization

// String interning for map keys
type StringInterner struct {
    mu    sync.RWMutex
    table map[string]string
}

func (si *StringInterner) Intern(s string) string {
    si.mu.RLock()
    if interned, ok := si.table[s]; ok {
        si.mu.RUnlock()
        return interned
    }
    si.mu.RUnlock()
    
    si.mu.Lock()
    defer si.mu.Unlock()
    si.table[s] = s
    return s
}

// Clearing maps efficiently
func clearMap(m map[string]int) {
    // Option 1: Delete all keys (keeps allocated memory)
    for k := range m {
        delete(m, k)
    }
    
    // Option 2: Replace with new map (releases memory)
    // m = make(map[string]int)
}

Common Pitfalls and Solutions

// Pitfall: Modifying map values
type User struct { Name string; Age int }
users := map[string]User{"alice": {"Alice", 30}}

// This won't compile!
// users["alice"].Age = 31  // Can't modify field of map value

// Solution 1: Copy, modify, write back
u := users["alice"]
u.Age = 31
users["alice"] = u

// Solution 2: Use pointer values
userPtrs := map[string]*User{"alice": {"Alice", 30}}
userPtrs["alice"].Age = 31  // This works!

// Safe deletion during iteration
for k, v := range m {
    if shouldDelete(v) {
        delete(m, k)  // Safe!
    }
}

// Check before type assertion
data := map[string]interface{}{}
if val, ok := data["key"]; ok {
    if str, ok := val.(string); ok {
        fmt.Println("String value:", str)
    }
}