Maps

The idea in one minute#

A map is a hash table: it hashes the key to a number, uses that number to pick a place in an array, and stores the key and value there. A map value in Go is a single pointer to a runtime structure, so copying a map variable gives you a second name for the same table.

Since Go 1.24 the table is a Swiss table: slots are organized in groups of eight, and each group keeps one control byte per slot holding seven bits of the hash, so a lookup can reject or match all eight slots with a couple of machine instructions before it compares any key.

Maps are fast and convenient, cost more memory per entry than a slice, have no order, and are not safe for concurrent writes.

An analogy#

A cloakroom with numbered racks. Your ticket number (the hash) says which rack to walk to. Each rack has eight hooks, and a small card at the end lists a two-digit code for the coat on each hook. The attendant glances at the card, sees which hooks could be yours, and only then looks at the coats. When too many racks are full, the cloakroom adds racks and re-hangs.

A picture#

flowchart TB
  K["key 'tenant-42'"] --> H["hash(key, seed)<br/>64 bits"]
  H --> H1["H1: upper 57 bits<br/>choose the group"]
  H --> H2["H2: lower 7 bits<br/>fingerprint"]
  H1 --> G
  subgraph G["Group: 8 control bytes + 8 slots"]
    direction TB
    CTRL["control: 3A  7F  12  empty  3A  empty  55  empty"]
    SLOTS["slots:  k0,v0  k1,v1  k2,v2  -  k4,v4  -  k6,v6  -"]
  end
  H2 -->|"compare against all 8 at once"| CTRL
  CTRL -->|"candidates: slots 0 and 4"| CMP["compare full keys"]
  CMP -->|"match"| V["value"]
  CMP -->|"no match, group has an empty slot"| MISS["not present"]
  CMP -->|"no match, group full"| NEXT["probe the next group"]
  class K neutral
  class H,H1,H2 compute
  class CTRL,SLOTS memory
  class CMP,NEXT queue
  class V,MISS neutral

How it really works#

Using maps#

m := make(map[string]int, 1000)     // size hint: avoids regrowth
m["a"] = 1
v := m["missing"]                   // zero value, no panic
v, ok := m["a"]                     // "comma ok": distinguishes absent from zero
delete(m, "a")
for k, v := range m { }             // order is deliberately randomized
clear(m)                            // remove everything (Go 1.21)

• Keys must be comparable: numbers, strings, pointers, arrays, structs of comparable fields. Not slices, maps or functions.
• A nil map reads as empty and panics on write.
• Iteration order is randomized on purpose so nobody depends on it. For a stable order, sort the keys: slices.Sorted(maps.Keys(m)).
• You cannot take the address of a map element (&m[k]): entries move when the table grows. For a struct value, read it, modify it and write it back, or store pointers.

Inside#

• The map variable is a pointer to a header: element count, hash seed, and the directory of tables. That is why passing a map to a function lets the function modify it, and why len(m) is constant time.
• Each map has its own random seed, so the same keys hash differently in each map and each run. This defeats attacks that send keys chosen to collide.
• A group holds 8 control bytes then 8 key/value slots. The 7-bit fingerprint check filters out almost all non-matching slots without touching the keys.
• Growth: when a table passes its load factor (7/8 of slots used) it doubles. Large maps are split into several independent tables behind a directory, so a growth step rehashes one bounded table rather than everything at once — keeping worst-case insert latency low.
• Deleting does not shrink. A map that grew to a million entries keeps that memory after you delete them; reassign a fresh map to release it.

All of this is internal and has changed before (the pre-1.24 design used buckets of eight with overflow chains). The behaviour in “Using maps” is what the language guarantees.

What a map costs#

For each entry: the key, the value, one control byte, and the empty slots implied by the load factor. A map[int64]int64 uses very roughly 20–40 bytes per entry against 16 for a pair of slice elements. Three consequences:

• For small, dense integer keys, a slice is smaller and several times faster.
• For a handful of entries, a linear scan of a slice often beats hashing.
• If keys or values contain pointers, the garbage collector must scan the map. A map with tens of millions of pointer-carrying entries is a real GC cost (III.04); map[int64]int64 or an index into a flat slice is not.

Concurrency#

Concurrent reads are fine. A write concurrent with anything else is a data race, and the runtime usually detects it and crashes with fatal error: concurrent map writes — on purpose, since silent corruption would be worse. Options:

Sets, and maps of slices#

seen := map[string]struct{}{}        // a set: struct{} occupies zero bytes
seen[k] = struct{}{}

groups[k] = append(groups[k], v)     // works when k is absent: append to a nil slice

Code#

// maps.go — reference semantics, random order, memory per entry, and map vs slice.
package main

import (
	"fmt"
	"runtime"
	"sort"
	"testing"
)

func heapInUse() uint64 {
	runtime.GC()
	var m runtime.MemStats
	runtime.ReadMemStats(&m)
	return m.HeapAlloc
}

func main() {
	// A map value is a pointer: both names see the write.
	a := map[string]int{"x": 1}
	b := a
	b["y"] = 2
	fmt.Println("a after writing through b:", len(a), "entries")

	// Iteration order differs from run to run and loop to loop.
	m := map[int]bool{}
	for i := 0; i < 8; i++ {
		m[i] = true
	}
	for pass := 0; pass < 3; pass++ {
		fmt.Print("order: ")
		for k := range m {
			fmt.Print(k, " ")
		}
		fmt.Println()
	}
	keys := make([]int, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	fmt.Println("sorted:", keys)

	// Bytes per entry.
	const n = 1_000_000
	before := heapInUse()
	big := make(map[int64]int64, n)
	for i := int64(0); i < n; i++ {
		big[i] = i
	}
	mapBytes := heapInUse() - before

	before = heapInUse()
	sl := make([]int64, n)
	for i := range sl {
		sl[i] = int64(i)
	}
	sliceBytes := heapInUse() - before
	fmt.Printf("\n%d entries: map %.1f bytes/entry, []int64 %.1f bytes/entry\n",
		n, float64(mapBytes)/n, float64(sliceBytes)/n)

	// Lookup speed: hashing vs indexing.
	sink := int64(0)
	rm := testing.Benchmark(func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			sink += big[int64(i%n)]
		}
	})
	rs := testing.Benchmark(func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			sink += sl[i%n]
		}
	})
	fmt.Printf("lookup: map %d ns, slice %d ns\n", rm.NsPerOp(), rs.NsPerOp())

	// Deleting does not return memory; a fresh map does.
	for i := int64(0); i < n; i++ {
		delete(big, i)
	}
	afterDelete := heapInUse()
	big = nil
	fmt.Printf("heap after deleting all keys: %.0f MB; after dropping the map: %.0f MB\n",
		float64(afterDelete)/1e6, float64(heapInUse())/1e6)
	runtime.KeepAlive(sl)
	_ = sink
}

Remember this#

• A map variable is a pointer to a hash table; copies share it.
• No order, no address-of an element, panic on writing a nil map, crash on concurrent writes.
• Swiss-table layout: groups of 8 slots with 7-bit fingerprints; grows by doubling; never shrinks.
• A map costs more memory and time per element than a slice. Use a slice when keys are small dense integers.

Try it#

1. Run maps.go. How many bytes per entry did the map cost on your machine? Change the value type to a 64-byte struct and predict the new figure before measuring.
2. Write two goroutines that write the same map without a lock. Read the crash. Fix it with a mutex, then with sharding.
3. Build a word-frequency counter for a large text with map[string]int, then print the top ten in a stable order.

Check yourself#

1. Why does passing a map to a function let the function modify the caller’s map?
2. What is the 7-bit fingerprint for?
3. When is a slice a better choice than a map?