Arrays, Slices and Maps: The Three Essential Containers

Learning Objectives

Core Concepts

7.1 Arrays: Fixed-Size Value Types

An array is the most basic data structure in Go: a contiguous block of memory made up of elements of the same type.

1. What: the length is part of the array type. [5]int and [10]int are two completely different types. An array must have its length specified at declaration, and that length cannot change.
2. Why: Go chooses fixed-length arrays so that the memory size is known at compile time, yielding very high access efficiency and avoiding the overhead of dynamic allocation.
3. How: go var a [5]int // declared and initialized to the zero value [0 0 0 0 0] b := [3]int{1, 2, 3} c := [...]int{1, 2, 3} // the compiler infers the length as 3 Note: an array is a value type. When an array is passed as a function argument, its entire contents are copied. On a 64-bit platform, passing an array of length N costs $N \times \text{sizeof(Element)}$ memory.

7.2 Slices: Dynamic Arrays with Reference Semantics

A slice is an abstraction over an array underneath, providing a dynamically sized view.

1. What: a slice is itself a data structure (a Slice Header) containing three fields:

   • Pointer: a pointer to the slice's starting element in the underlying array.
   • Len: the number of elements in the slice.
   • Cap: the capacity of the underlying array, i.e. the number of elements from the start position to the end of the array.

   A slice is not a reference type; it is a value type (the header — 24 bytes: pointer 8 + len 8 + cap 8 — is copied when passed), but it shares the same underlying array with its sibling slices.

2. Why: to combine the performance of static arrays with the flexibility of dynamic arrays. By sharing the underlying array, slice operations (such as reslicing) complete in $O(1)$ time without copying data.

3. How:

   • Creation: go s := make([]int, 3, 5) // len=3, cap=5, underlying array length 5 s2 := []int{1, 2, 3} // len=3, cap=3
   • Slice expression: s[low:high:max]
   • s[low:high]: takes elements from index low to high-1.
   • s[low:high:max]: besides taking elements, it caps the new slice's maximum capacity at max - low. This is commonly used to prevent data leaks or to reuse memory.
   • Iteration: use for range.

7.3 append and the Growth Mechanism

append is the most common slice operation, used to add elements to the end of a slice.

1. Growth threshold and strategy (Go 1.18+): When the slice runs out of capacity, append allocates a new underlying array and copies the data. The growth strategy is:

   • When oldcap < 256, the new capacity is roughly 2x the old capacity (about doubling).
   • When oldcap >= 256, the new capacity grows by the formula newcap += (newcap + 3*256)/4 (roughly 1.25x), then rounds up to a memory size class.
   • Engineering practice: do not rely on the exact growth factor. If you know the approximate size of a slice, preallocate capacity with make([]T, 0, n) to avoid the allocation and copying cost of repeated growth.

2. The shared-underlying-array trap: If the slice has enough capacity, append does not trigger growth and writes directly into the underlying array. If multiple slices share the same underlying array, a modification through one slice affects the others.

7.4 map: A Hash Table

A map is Go's built-in hash table implementation, used for key-value storage.

1. What: map[K]V, where K must be a type supporting == and != (such as int, string, struct, etc.; slices, maps and functions are not allowed).
2. Iteration is unordered: when for range iterates over a map, the order of key-value pairs is random. It may differ on every run.
3. Deletion:
   • delete(map, key): removes the given key.
   • Spec semantics: deleting elements during a for range loop is legal. The spec states: if an entry not yet reached is deleted during iteration, it will not be produced.
   • New entries: whether an entry inserted during iteration is produced is undefined (it may or may not show up), so do not add entries during iteration.
   • Concurrency safety: a native map is not concurrency-safe. Concurrent reads and writes on the same map trigger fatal error: concurrent map reads and map writes or concurrent map writes — an unrecoverable fatal error.

Example Code

Example 1: Slice Growth and the Shared-Underlying-Array Trap

This example shows the underlying array being detached when append triggers growth, and the side effects of sharing the underlying array when capacity is sufficient.

package main

import "fmt"

func main() {
    // Scenario 1: capacity runs out, growth triggers, and the underlying arrays separate
    fmt.Println("=== Scenario 1: growth detaches the underlying array ===")
    s1 := []int{1, 2, 3}
    fmt.Printf("s1: %v, cap: %d\n", s1, cap(s1))

    // At this point s1 has cap=3, so append needs to grow
    s2 := append(s1, 4)
    fmt.Printf("s1: %v, cap: %d\n", s1, cap(s1))
    fmt.Printf("s2: %v, cap: %d\n", s2, cap(s2))
    fmt.Println("s1 and s2 now have separate underlying arrays and do not affect each other.")
    fmt.Println()

    // Scenario 2: capacity is sufficient, writing directly into the shared array affects the original slice
    fmt.Println("=== Scenario 2: enough capacity, shared underlying array ===")
    // Create a slice with spare capacity
    s3 := make([]int, 2, 5) // len=2, cap=5
    s3[0] = 10
    s3[1] = 20

    // Create s4 based on s3, pointing at s3's second element
    s4 := s3[1:2] // len=1, cap=4, points at s3[1]

    fmt.Printf("s3: %v\n", s3)
    fmt.Printf("s4: %v\n", s4)

    // Append to s4. Because s4 has enough cap (4 > 1), no growth happens,
    // and it writes directly into s3's underlying array at s3[2].
    s4 = append(s4, 99)

    fmt.Printf("s3: %v\n", s3) // s3 is modified!
    fmt.Printf("s4: %v\n", s4)
    fmt.Println("Note: s3[2] was modified by s4's append, because they share the underlying array.")
}

Expected output:

=== Scenario 1: growth detaches the underlying array ===
s1: [1 2 3], cap: 3
s1: [1 2 3], cap: 3
s2: [1 2 3 4], cap: 6
s1 and s2 now have separate underlying arrays and do not affect each other.

=== Scenario 2: enough capacity, shared underlying array ===
s3: [10 20 0]
s4: [20]
s3: [10 20 99]
s4: [20 99]
Note: s3[2] was modified by s4's append, because they share the underlying array.

Example 2: Map Iteration and Deletion

This example shows map insert/update/lookup/delete, and the semantics of safely deleting elements during iteration.

package main

import "fmt"

func main() {
    // 1. Create and initialize
    m := map[string]int{
        "a": 1,
        "b": 2,
        "c": 3,
    }

    // 2. Insert, update, lookup
    m["d"] = 4 // insert
    m["a"] = 10 // update
    val, ok := m["b"] // lookup; ok is true
    fmt.Printf("m['b']: %v, ok: %v\n", val, ok)

    // 3. Check whether a key exists
    if _, exists := m["e"]; !exists {
        fmt.Println("Key 'e' does not exist")
    }

    // 4. Iteration and deletion
    fmt.Println("Before delete:")
    for k, v := range m {
        fmt.Printf("%s: %d\n", k, v)
    }

    // Deleting during iteration is legal.
    // Spec: entries not yet reached that are deleted are no longer produced.
    fmt.Println("\nDeleting 'a' during iteration:")
    for k, v := range m {
        if k == "a" {
            delete(m, k)
            fmt.Printf("Deleted %s\n", k)
        }
    }

    fmt.Println("\nAfter delete:")
    for k, v := range m {
        fmt.Printf("%s: %d\n", k, v)
    }
}

Expected output:

m['b']: 2, ok: true
Key 'e' does not exist
Before delete:
a: 10
b: 2
c: 3
d: 4

Deleting 'a' during iteration:
Deleted a

After delete:
b: 2
c: 3
d: 4

(Note: map iteration order is random; the output above is just one possibility. It only needs to contain b, c, d and no a.)

Common Mistakes & Pitfalls

Best Practices

Exercises

1. Concept question: Explain why var a [5]int and var b [10]int are different types, while []int and []int are the same type.

2. Coding exercise: Write a function RemoveDuplicates that takes a []int slice and returns a deduplicated []int slice. Requirements:

   • Each element appears exactly once in the result.
   • Preserve the order of each element's first appearance in the original slice.
   • Do not use any external libraries.

3. Advanced/debugging exercise: The code below is meant to find duplicate elements in a slice, but has a logic error. Find the problem and fix it, so that each duplicated element appears exactly once in the result, in the order of its first repeat.

   ```go package main

   import "fmt"

   func FindDuplicates(nums []int) []int { seen := make(map[int]bool) var duplicates []int for _, num := range nums { if seen[num] { duplicates = append(duplicates, num) } else { seen[num] = true } } return duplicates }

   func main() { nums := []int{1, 2, 3, 2, 4, 1, 5} fmt.Println(FindDuplicates(nums)) } `` *(Note: the expected output is[2 1]`, because 2 and 1 are duplicated, and 2 is encountered a second time before 1 is.)*

Reference Answers

package main

import "fmt"

func RemoveDuplicates(nums []int) []int {
    seen := make(map[int]bool)
    var result []int
    for _, num := range nums {
        if !seen[num] {
            seen[num] = true
            result = append(result, num)
        }
    }
    return result
}

func main() {
    nums := []int{1, 2, 3, 2, 4, 1, 5}
    fmt.Println(RemoveDuplicates(nums)) // prints: [1 2 3 4 5]
}

package main

import "fmt"

func FindDuplicates(nums []int) []int {
    seen := make(map[int]bool)
    duplicates := make(map[int]bool)
    var result []int

    for _, num := range nums {
        if seen[num] {
            // If already marked as duplicate, skip it
            if !duplicates[num] {
                duplicates[num] = true
                result = append(result, num)
            }
        } else {
            seen[num] = true
        }
    }
    return result
}

func main() {
    nums := []int{1, 2, 3, 2, 4, 1, 5}
    fmt.Println(FindDuplicates(nums)) // prints: [2 1]
}

Lesson Summary