Map internals, hashing and growth

A map variable does not hold a table. It holds a header: a pointer to the table the runtime owns, a count and a flag that says whether the table is being grown. That is why a map is cheap to pass, why two variables can name the same table, and why the language forbids taking the address of an element: growth moves elements, so a pointer into the table would not stay valid. The previous lesson used maps from the outside; this one opens the box.

A map is a header

Assignment copies the three words of the header, not the entries, so both names see the same table. Reassigning one name points that name at another table and leaves the other name where it was. This is the same distinction as a slice header in the slices internals lesson, with a count instead of a capacity.

package main import "fmt" func main() { stock := map[string]int{"go": 3, "rust": 2} alias := stock alias["go"] = 30 fmt.Println("stock sees:", stock["go"]) replaced := map[string]int{"go": 1} stock = replaced fmt.Println("alias still sees:", alias["go"], "stock now:", stock["go"]) fmt.Println("lengths:", len(alias), len(stock)) }

go run alias.go

stock sees: 30
alias still sees: 30 stock now: 1
lengths: 2 1

The first write through alias changed stock, because there is one table. The reassignment then gave stock a fresh one-entry table, and alias still holds the old one with two entries, which is why the lengths differ at the end.

Groups, hashes and growth

Since Go 1.24 the table is a Swiss table: an array of groups of eight slots, each group with a word of control bytes. The hash of a key picks a group with its high bits and marks the slot with a byte of its low bits, so a lookup compares one byte per slot before it compares a key. The table grows when it is about seven-eighths full: a bigger group array is allocated, the old groups are kept beside it, and entries move over on later writes instead of in one pause. A size hint lets make allocate a table that already fits the entries a program expects.

package main import ( "fmt" "testing" ) func fill(hint int) { m := make(map[int]int, hint) for i := 0; i < 2000; i++ { m[i] = i } } func main() { without := testing.AllocsPerRun(5, func() { fill(0) }) with := testing.AllocsPerRun(5, func() { fill(2000) }) fmt.Println("allocations without a size hint:", without) fmt.Println("allocations with a size hint: ", with) }

go run growth.go

allocations without a size hint: 29
allocations with a size hint: 9

Filling two thousand entries without a hint costs 29 allocations against 9 with make(map[int]int, 2000). The difference is not the entries, which are stored in the table, but the table arrays: each growth allocates a new one and leaves the old to the collector. A hint does not change what the map holds or how it is used, only how many times the runtime has to grow it.

The hash seed makes the order random

Every map gets its own hash seed when it is created, and the runtime uses it to mix the key before choosing a group. The seed is what makes iteration order differ between two maps that hold the same keys, and between two runs of the same program: there is no insertion order to recover, even in principle. The hash/maphash package exposes the same idea for a program that needs its own seeded hash, such as a cache keyed by user input.

package main import ( "fmt" "hash/maphash" ) func main() { a := maphash.MakeSeed() b := maphash.MakeSeed() first := maphash.String(a, "go") again := maphash.String(a, "go") other := maphash.String(b, "go") fmt.Println("same seed, same key:", first == again) fmt.Println("two seeds, same key:", first == other) }

go run seed.go

same seed, same key: true
two seeds, same key: false

One seed gives one hash for one string, every time; a second seed gives another hash for the same string. A program that needs a stable order sorts the keys or keeps a slice beside the map, as the sorting lesson shows.

Keys that never equal themselves

A map finds a key by comparing it, and the only value in Go that is not equal to itself is a floating-point NaN. Storing one works, the length counts it, and a range finds it, but a lookup with the same NaN misses, because NaN == NaN is false. It is the one key that can be inserted and then never read, and it cannot even be deleted: delete(m, math.NaN()) finds nothing to delete.

package main import ( "fmt" "math" ) func main() { m := map[float64]string{} m[math.NaN()] = "nan" fmt.Println("len:", len(m)) v, ok := m[math.NaN()] fmt.Printf("lookup: %q present: %v\n", v, ok) for k := range m { fmt.Println("range finds:", k, m[k]) } }

go run nan.go

len: 1
lookup: "" present: false
range finds: NaN

The entry stays in the table and the program can only lose it by dropping the whole map. The lesson is general: a key type whose values are not properly comparable for the program's purposes is a bug waiting in the data, not in the map.

Elements have no address

Because growth moves entries, m[k] is not addressable: the compiler refuses &m[k], and it refuses to write a field of a struct stored in a map, since that write would need the address of the element. The fix is to read the struct, change the copy and store it back, or to keep pointers in the map when the identity of the value matters.

package main import "fmt" type counter struct { n int } func main() { m := map[string]counter{"a": {n: 1}} m["a"].n++ fmt.Println(m["a"].n) }

go build -o address address.go

# command-line-arguments
./address.go:11:2: cannot assign to struct field m["a"].n in map

The message names the operation rather than the map: cannot assign to struct field m["a"].n in map. Writing m["a"] = counter{n: 2} is fine, and so is a map of *counter, because then the pointer is the element and the struct lives elsewhere. The structs lesson returns to this when it covers copies.

Exercises

  1. Fill a map with a million entries with and without a size hint and compare the allocation counts. How many growths does each version need for two thousand entries?
  2. Write a lookup that uses math.NaN as a key and deletes the entry by ranging over the map and calling delete with the key the range gave. Why does that work when a direct delete does not?
  3. Keep a map[string]*User and a map[string]User of the same data. Which one lets you change a field in place, and what does the other need?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does assigning one map variable to another copy?

    Answer

    The header: the pointer, the count and the growth flag

    Maps are reference types by header: the assignment copies three words and both names keep the same table.

  2. What does this program print? package main import "fmt" func main() { stock := map[string]int{"go": 3, "rust": 2} alias := stock alias["go"] = 30 fmt.Println("stock sees:", stock["go"]) replaced := map[string]int{"go": 1} stock = replaced fmt.Println("alias still sees:", alias["go"], "stock now:", stock["go"]) fmt.Println("lengths:", len(alias), len(stock)) }

    Answer

    stock sees: 30 / alias still sees: 30 stock now: 1 / lengths: 2 1

    alias and stock share the table until stock is reassigned; the alias keeps the old table with the write.

  3. When does a map table grow?

    Answer

    When it is about seven-eighths full

    The Swiss table grows near a load factor of 7/8, and the old groups move over incrementally.

  4. What does this program print? package main import ( "fmt" "hash/maphash" ) func main() { a := maphash.MakeSeed() b := maphash.MakeSeed() first := maphash.String(a, "go") again := maphash.String(a, "go") other := maphash.String(b, "go") fmt.Println("same seed, same key:", first == again) fmt.Println("two seeds, same key:", first == other) }

    Answer

    same seed, same key: true / two seeds, same key: false

    One seed hashes a string the same way twice; two seeds give different hashes.

  5. What does make(map[string]int, 1000) change?

    Answer

    It reserves table space for about 1000 entries, so fewer growths are needed

    The hint sizes the table; the map still starts empty with length zero.

  6. What does this program print? package main import ( "fmt" "math" ) func main() { m := map[float64]string{} m[math.NaN()] = "nan" fmt.Println("len:", len(m)) v, ok := m[math.NaN()] fmt.Printf("lookup: %q present: %v\n", v, ok) for k := range m { fmt.Println("range finds:", k, m[k]) } }

    Answer

    len: 1 / lookup: "" present: false / range finds: NaN

    The entry is stored and ranged over, but NaN != NaN makes the lookup miss.

  7. What does the compiler say about this program? package main import "fmt" type counter struct { n int } func main() { m := map[string]counter{"a": {n: 1}} m["a"].n++ fmt.Println(m["a"].n) }

    Answer

    cannot assign to struct field m["a"].n in map

    A map element has no address, so a field of a struct in a map cannot be assigned.

  8. Why is an element of a map not addressable?

    Answer

    Growth moves entries, so a pointer into the table would not stay valid

    An address into a table that moves is exactly what the language refuses to hand out.

  9. Two maps hold the same keys in the same insertion order. What is true of their iteration order?

    Answer

    It may differ, because each map has its own hash seed

    The seed is per map, so equal contents do not mean equal order.

  10. You need a stable order over a map. What does the course recommend?

    Answer

    Collect the keys into a slice and sort it

    Insertion order is not kept by any map implementation; sorting the keys is the reliable way.

The code on this page was run with go 1.26.10 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev