Maps in Go

📚 Comprehensive Guide ⏱️ 25 min read 🎯 Intermediate Level

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 Internals

  • Buckets: Each map has 2^B buckets (B is the bucket bits)
  • Load Factor: Maps grow when average items per bucket exceeds 6.5
  • Hash Function: Go uses a fast, non-cryptographic hash
  • Growth: Maps double in size when growing, with gradual evacuation

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.

⚠️ Iteration Order

Never rely on map iteration order! Go randomizes it intentionally. If you need ordered output, collect keys and sort them first. 

// 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.

⚠️ Race Conditions

  • Concurrent map writes cause runtime panic
  • Use go run -race to detect races
  • Even concurrent read + write is unsafe
  • sync.Map has overhead; use mutexes for better control
// 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

Operation Average Case Worst Case Notes
Get O(1) O(n) Worst case with all hash collisions
Set O(1) O(n) May trigger growth and rehashing
Delete O(1) O(n) Doesn't shrink map
Iteration O(n) O(n) Random order each time
len() O(1) O(1) Maintained counter
Growth O(n) O(n) Gradual evacuation

Memory Optimization

Memory Best Practices

  • Preallocate: Use make(map[K]V, hint) when size is known
  • Clear maps: Set to nil or make new to release memory
  • String keys: Consider interning for repeated strings
  • Pointer values: Store pointers for large structs
  • Delete unused: Remove entries to prevent unbounded growth
// 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

⚠️ Map Gotchas

  • Nil maps: Can read but not write
  • Non-addressable values: Can't take address of map values
  • Iteration mutations: Safe to delete during iteration
  • Key types: Must be comparable (no slices, maps, functions)
  • Concurrent access: Will panic without synchronization
// 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)
    }
}

🎯 Practice Exercises

Exercise 1: LRU Cache

Implement a Least Recently Used (LRU) cache using a map and a doubly-linked list.

Exercise 2: Graph Representation

Create an adjacency list representation of a graph using maps and implement DFS/BFS.

Exercise 3: Word Frequency Counter

Build a concurrent word frequency counter that processes multiple files in parallel.

Exercise 4: JSON to Map

Write a function that converts arbitrary JSON to nested maps and handles all types.

Next: Structs & Methods →