04. Hash Maps and Sets

Hash maps solve the biggest limitation of arrays: finding a value by content instead of by position. Arrays need O(n) to search. Hash maps do it in O(1). This single property makes them the most-used data structure in real code and interviews alike.

How Hash Maps Work

A hash map stores key-value pairs. You give it a key, it runs a hash function to compute an index, and stores the value at that index in an internal array.

key "alice" → hash("alice") → 3 → store at index 3
key "bob"   → hash("bob")   → 7 → store at index 7

Lookup "alice" → hash("alice") → 3 → found at index 3, O(1)

The hash function converts any key into an integer. A good hash function distributes keys evenly across the array. A bad one puts everything in the same slot (collision), degrading to O(n).

Go's map

Go's built-in map is a hash map:

// Create and use
ages := map[string]int{
    "alice": 30,
    "bob":   25,
}

ages["carol"] = 28       // insert — O(1)
age := ages["alice"]     // lookup — O(1)
delete(ages, "bob")      // delete — O(1)

// Check existence
if age, ok := ages["dave"]; ok {
    fmt.Println(age)
}

Maps in Go are unordered. Iteration order is randomized on purpose. If you need order, you need a different structure.

Operation Costs

Worst case happens when all keys hash to the same bucket (collision). In practice with Go's built-in map, this essentially never happens. Treat it as O(1).

Sets

A set is a collection of unique values with O(1) membership testing. Go doesn't have a built-in set type. Use a map with empty struct values:

// Set of strings
seen := map[string]struct{}{}

seen["alice"] = struct{}{} // add
delete(seen, "alice")      // remove

if _, ok := seen["bob"]; ok { // membership test — O(1)
    fmt.Println("bob exists")
}

Why struct{} instead of bool? It uses zero bytes of memory. A map[string]bool works too but wastes 1 byte per entry.

Pattern: Frequency Counting

Count how often each element appears. The most common hash map pattern.

// Count character frequencies — O(n)
func charFreq(s string) map[rune]int {
    freq := map[rune]int{}
    for _, ch := range s {
        freq[ch]++
    }
    return freq
}

// Are two strings anagrams?
func isAnagram(s, t string) bool {
    if len(s) != len(t) {
        return false
    }
    freq := map[rune]int{}
    for _, ch := range s {
        freq[ch]++
    }
    for _, ch := range t {
        freq[ch]--
        if freq[ch] < 0 {
            return false
        }
    }
    return true
}

Pattern: Two Sum (Index Lookup)

Store values you've seen so you can find complements in O(1):

LeetCode 1 - Two Sum

// Find two numbers that add to target — O(n)
func twoSum(nums []int, target int) (int, int) {
    seen := map[int]int{} // value → index
    for i, n := range nums {
        complement := target - n
        if j, ok := seen[complement]; ok {
            return j, i
        }
        seen[n] = i
    }
    return -1, -1
}

Without a hash map, this is O(n²) — check every pair. With a hash map, one pass.

Pattern: Deduplication

Remove duplicates while preserving order:

func unique(nums []int) []int {
    seen := map[int]struct{}{}
    result := []int{}
    for _, n := range nums {
        if _, ok := seen[n]; !ok {
            seen[n] = struct{}{}
            result = append(result, n)
        }
    }
    return result
}

Pattern: Grouping

Group elements by a computed key:

// Sort characters in a string (for anagram grouping)
func sortString(s string) string {
    b := []byte(s)
    sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
    return string(b)
}

// Group words by their sorted characters (anagram groups)
func groupAnagrams(words []string) map[string][]string {
    groups := map[string][]string{}
    for _, w := range words {
        key := sortString(w)
        groups[key] = append(groups[key], w)
    }
    return groups
}

When to Use Hash Maps

• You need O(1) lookup by key
• Counting frequencies
• Detecting duplicates
• Caching computed results (memoization)
• Mapping relationships (graph adjacency lists)

When NOT to Use Hash Maps

• You need sorted order → use a BST or sorted slice
• Keys are small integers (0 to n) → use an array (faster, less memory)
• You need range queries ("all keys between 5 and 10") → use a BST
• Memory is extremely tight → hash maps have overhead per entry

Practice Problems

Key Takeaways

• Hash maps give O(1) average lookup, insert, and delete by hashing keys to array indices
• Go's map[K]V is the built-in hash map; use map[K]struct{} for sets
• Collisions degrade to O(n) but are rare in practice
• Core patterns: frequency counting, two-sum/complement lookup, deduplication, grouping
• Hash maps trade memory for speed — every entry has overhead beyond the key and value
• If you need order or range queries, a hash map is the wrong choice