These are the notes for Go episode 16. In episode 15 a map found the price of a samosa instantly, with no loop we could see. Today we open the map up, and the best way to understand it is to invent it ourselves: from a slow list search, to shelves (buckets) and a hash function, to collisions, load factor, growth and rehashing, random seeds against hash flooding, and finally Go's real design: the old bucket map (Go 1.0 to 1.23) and the Swiss Tables map (Go 1.24). Then the rules the design forces on us: comparable key types, the strange NaN key, why you can't take the address of a map entry, why a map is reference-like, and why maps are not safe for concurrent use.
Every example runs as-is in the SyntaxPilot compiler (language: Go). Outputs and errors are from real runs with Go 1.24. Facts about Go's map design come from the Go source code (internal/runtime/maps and runtime/map_noswiss.go in Go 1.24) and the Go blog post Faster Go maps with Swiss Tables (Michael Pratt, 26 February 2025).
The problem: a million names in one long register
Picture a hostel register with a million names, written in the order people arrived. Someone asks: is user999999 staying here? With no other plan, you read from the top, one name at a time. Checking every item in order is called a linear search.
package main
import "fmt"
func main() {
names := make([]string, 1_000_000)
for i := range names {
names[i] = fmt.Sprint("user", i)
}
checks := 0
for _, n := range names {
checks++
if n == "user999999" {
break
}
}
fmt.Println("found after", checks, "checks")
}
found after 1000000 checks
A million checks for one question, and double the names means double the work. Yet a map with a million entries answers in roughly the same time as a map with ten. How?
Invent it: shelves and a rule (buckets and a hash function)
Libraries solved this long ago:
| In a library | In a map |
|---|---|
| Numbered shelves | Buckets: separate places that each hold a few entries |
| A fixed rule: name → shelf number | Hash function: turns a key into a number (the hash) |
| Search only that one shelf | Fast lookup: a few checks, not a million |
A table built this way is a hash table, and that is what a Go map is.
Our first rule: take the first letter of the name, count from A, and take the remainder after dividing by 4.
package main
import "fmt"
func shelf(name string) int {
return int(name[0]-'A') % 4
}
func main() {
shelves := make([][]string, 4)
for _, n := range []string{"Asha", "Ravi", "Meena", "Sunil",
"Sita", "Suresh", "Sana", "Bhavna"} {
s := shelf(n)
shelves[s] = append(shelves[s], n)
}
for i, s := range shelves {
fmt.Println("shelf", i, s)
}
}
shelf 0 [Asha Meena]
shelf 1 [Ravi Bhavna]
shelf 2 [Sunil Sita Suresh Sana]
shelf 3 []
Every S name piles onto shelf 2 and shelf 3 is empty. Two different keys landing in the same bucket is a collision. A rule that looks at only one letter causes lots of them: it is a bad hash function.
A better hash: mix every byte
A good hash function mixes every byte of the key, so similar keys land far apart. Go's standard library has FNV-1a (Fowler–Noll–Vo) in hash/fnv:
package main
import (
"fmt"
"hash/fnv"
)
func main() {
shelves := make([][]string, 4)
for _, n := range []string{"Asha", "Ravi", "Meena", "Sunil",
"Sita", "Suresh", "Sana", "Bhavna"} {
h := fnv.New32a()
h.Write([]byte(n))
s := h.Sum32() % 4
shelves[s] = append(shelves[s], n)
}
fmt.Println(shelves)
}
[[Sunil Sana] [Ravi Bhavna] [Asha Sita] [Meena Suresh]]
- Two names on every shelf: an even spread.
- Run it again and
Ravilands on the same shelf every time: the same key always gives the same hash. A hash function must be deterministic. - Collisions still happen (there are far more possible names than shelves). That's fine: inside a bucket the map compares keys with
==. The hash narrows the search; equality confirms the match.
Load factor, growth and rehashing
More guests, same shelves: the shelves get long and we're back to slow searching.
package main
import (
"fmt"
"hash/fnv"
"slices"
)
func main() {
for _, shelves := range []int{4, 256} {
count := make([]int, shelves)
for i := range 1000 {
h := fnv.New32a()
h.Write([]byte(fmt.Sprint("user", i)))
count[h.Sum32()%uint32(shelves)]++
}
fmt.Println(shelves, "shelves, longest:", slices.Max(count))
}
}
4 shelves, longest: 250
256 shelves, longest: 8
- Load factor = number of entries ÷ number of buckets. Here 1000 ÷ 4 = 250, then 1000 ÷ 256 ≈ 4.
- When the load factor gets too high, the map grows: it makes more buckets (usually double).
- The bucket was
hash % number of buckets. Change the number of buckets and almost every entry belongs somewhere new, so every entry is placed again. That's rehashing. - Rehashing costs time, so a map grows only when it is too full, not on every insert.
- If you know the size up front, give
makea size hint:make(map[string]int, 1000)allocates room for about 1000 entries once and avoids repeated growth.
Hash seeds and hash flooding
If the hash rule is fixed and public, an attacker can craft thousands of keys that all land in one bucket (for example, field names in a JSON request sent to your web server). Every lookup becomes a long linear search and the server slows to a crawl. This is a hash flooding attack (a kind of denial of service).
The fix is a seed: a secret random number mixed into the hash. With a different seed, the same key lands in a different bucket, so nobody can plan the collisions ahead of time. Every Go map picks its own random seed when it is created (m.seed = uintptr(rand()) in internal/runtime/maps/map.go).
The package hash/maphash gives you the same kind of seeded hash the runtime uses:
package main
import (
"fmt"
"hash/maphash"
)
func main() {
a := maphash.MakeSeed()
b := maphash.MakeSeed()
same := maphash.String(a, "chai") == maphash.String(a, "chai")
fmt.Println(same)
fmt.Println(maphash.String(a, "chai")%8, maphash.String(b, "chai")%8)
}
Two real runs:
true
3 7
true
7 0
The first line is always true (same seed, same hash). The bucket numbers change with every run, because the seeds are random; your numbers will differ. This is also one reason map iteration order changes between runs: entries sit in different places each time.
Go's real map before Go 1.24: buckets of 8
The Go runtime's source (runtime/map_noswiss.go) describes our shelves almost exactly:
bucket array: [ bucket 0 ][ bucket 1 ][ bucket 2 ] ...
each bucket: up to 8 key/value pairs + a few hash bits per entry
full bucket: [ bucket 2 ] → [ overflow bucket ] → [ overflow bucket ]
- An array of buckets, each holding up to 8 key/value pairs.
- The low-order bits of the hash pick the bucket; a few high-order bits of each hash are kept in the bucket to tell entries apart quickly.
- More than 8 keys in one bucket? An extra overflow bucket is chained on.
- The map grew when the average load reached 6.5 entries per bucket (8 × 13/16, about 80% full).
- Growth was incremental: entries were moved a few at a time during later writes, so no single insert paid for the whole move.
Go 1.24: Swiss Tables
Go 1.24 (February 2025) rebuilt the map on Swiss Tables, a design from Google's Abseil C++ library, with changes for Go's needs. Real-life picture: a housing society's parcel room.
| Parcel room | Go 1.24 map |
|---|---|
| Racks of 8 cubbies, one parcel each | A group of 8 slots; a slot holds one key/value pair |
| A strip of 8 stickers on each rack | An 8-byte control word: one control byte per slot (empty, deleted, or in use + 7 hash bits) |
| Glance at the strip, open only matching cubbies | Compare H2 against all 8 control bytes in one step |
| Rack room too full? Open a new room, move just that room | Tables of at most 1024 entries, listed in a directory; growth copies at most 1024 entries |
How a lookup works:
- Hash the key (64 bits, with the map's seed).
- Split it: H1 = upper 57 bits, H2 = lower 7 bits.
- The top bits of the hash pick the table from the directory (this is extendible hashing: the number of bits used grows as the map gets more tables).
- H1 picks the first group to check.
- Compare H2 with all 8 control bytes at once (clever bit tricks, one operation). Only slots whose 7 bits match are opened and compared with
==. A 7-bit match is wrong only about 1 in 128 times. - No match and the group has an empty slot? The key isn't in the map. Otherwise move to the next group (quadratic probing).
Numbers from the Go source and the Go blog:
| Fact | Value | Source |
|---|---|---|
| Slots per group | 8 | abi.SwissMapGroupSlots, map.go |
| Control word | 8 bytes, one per slot | map.go |
| H1 / H2 | upper 57 bits / lower 7 bits | map.go |
| Maximum fill | 7 of 8 slots (maxAvgGroupLoad = 7) |
group.go |
| Maximum entries per table | 1024 (maxTableCapacity) |
table.go |
| Speed vs Go 1.23 | map operations up to 60% faster in microbenchmarks | Go blog |
| Whole applications | about 1.5% geometric-mean CPU improvement | Go blog |
Deleting an entry from a full group leaves a tombstone (a "deleted" mark) so later searches don't stop too early. None of this changes your code: same map[K]V, new engine.
Why keys must be comparable
Every lookup ends with == on the key. So a key type must be comparable (its values can be compared with ==). A struct is comparable only if all its fields are.
package main
import "fmt"
type order struct {
table int
items []string
}
type seat struct {
row, num int
}
func main() {
bad := map[order]int{}
good := map[seat]string{{1, 2}: "Asha"}
fmt.Println(bad, good)
}
# command-line-arguments
./main.go:15:16: invalid map key type order
Remove bad and the seat key works:
func main() {
good := map[seat]string{{1, 2}: "Asha"}
fmt.Println(good[seat{1, 2}], len(good))
}
Asha 1
The back door: any keys
any can hold a value of any type and counts as comparable, so map[any]bool compiles. But if a slice gets in, the runtime can't hash it:
package main
import "fmt"
func main() {
seen := map[any]bool{}
seen["chai"] = true
seen[42] = true
fmt.Println(len(seen))
seen[[]int{1, 2}] = true
fmt.Println("never printed")
}
2
panic: runtime error: hash of unhashable type []int
goroutine 1 [running]:
main.main()
/tmp/main.go:10 +0x198
exit status 2
A panic is a crash while the program runs (episode 26). With interface keys, the comparable check happens at run time.
NaN keys
In floating-point maths, 0/0 has no answer, so the result is NaN ("not a number"), from math.NaN(). NaN is never equal to anything, not even itself.
package main
import (
"fmt"
"math"
)
func main() {
m := map[float64]string{}
nan := math.NaN()
m[nan] = "first"
m[nan] = "second"
v, ok := m[nan]
fmt.Printf("%d %v %q %v\n", len(m), nan == nan, v, ok)
delete(m, nan)
fmt.Println(len(m))
clear(m)
fmt.Println(len(m))
}
2 false "" false
2
0
- Each NaN write adds a new entry, because the new key never
==the old one. - Lookup and
deletecan never find a NaN key. - Only
clear(Go 1.21) removes them. Avoid float keys that can be NaN.
Entries move: no address of a map entry
Growth moves entries to new slots, so a pointer to an entry would go stale. Go forbids it:
package main
import "fmt"
type item struct {
price int
}
func main() {
menu := map[string]item{"chai": {20}}
menu["chai"].price = 25
p := &menu["chai"]
fmt.Println(menu, p)
}
# command-line-arguments
./main.go:11:5: cannot assign to struct field menu["chai"].price in map
./main.go:12:11: invalid operation: cannot take address of menu["chai"] (map index expression of struct type item)
Two fixes: copy, change, store back, or store pointers so the struct lives outside the map:
package main
import "fmt"
type item struct {
price int
}
func main() {
menu := map[string]item{"chai": {20}}
it := menu["chai"]
it.price = 25
menu["chai"] = it
ptrs := map[string]*item{"samosa": {15}}
ptrs["samosa"].price = 18
fmt.Println(menu, ptrs["samosa"].price)
}
map[chai:{25}] 18
Maps are reference-like
package main
import (
"fmt"
"unsafe"
)
func raisePrices(menu map[string]int) {
for item := range menu {
menu[item] += 5
}
}
func main() {
menu := map[string]int{"chai": 20, "samosa": 15}
raisePrices(menu)
big := make(map[int]int, 1_000_000)
fmt.Println(menu, unsafe.Sizeof(menu), unsafe.Sizeof(big))
}
map[chai:25 samosa:20] 8 8
- The function changed the caller's map.
- Both map variables are 8 bytes (on a 64-bit machine): a map variable is just a pointer to the runtime's map structure (the header that holds the seed, the count and the directory of tables).
- Go passes everything by value; for a map the value copied is that pointer, so maps behave like references. That's why
backup := todayshared the map in episode 15. unsafe.Sizeofreports a variable's size in bytes. Theunsafepackage steps around Go's safety rules: use it to learn, rarely in real code.
Maps are not safe for concurrent use
A goroutine is a function running at the same time as the rest of the program, started with go before a call (episode 43). Two goroutines writing one map:
package main
import (
"fmt"
"time"
)
func main() {
orders := map[int]int{}
for counter := 0; counter < 2; counter++ {
go func() {
for i := 0; i < 100000; i++ {
orders[i]++
}
}()
}
time.Sleep(time.Second)
fmt.Println(len(orders))
}
fatal error: concurrent map writes
goroutine 18 [running]:
internal/runtime/maps.fatal({0x4b6e83?, 0x0?})
/usr/local/go1.24.7/src/runtime/panic.go:1058 +0x18
main.main.func1()
/tmp/main.go:13 +0x2f
created by main.main in goroutine 1
...
- If one write grows the map and moves entries while another write is in progress, the map would be corrupted.
- The map keeps a small "writing" flag and checks it, so it fails loudly instead of silently returning wrong data.
- It is a fatal error, not a panic:
recovercan't catch it; the whole program stops. - Rule: if any goroutine writes a map, no other goroutine may read or write it at the same time without synchronisation.
The fix is a lock. sync.Mutex lets only one goroutine at a time run the code between Lock and Unlock (episode 45):
package main
import (
"fmt"
"sync"
"time"
)
func main() {
orders := map[int]int{}
var mu sync.Mutex
for counter := 0; counter < 2; counter++ {
go func() {
for i := 0; i < 100000; i++ {
mu.Lock()
orders[i]++
mu.Unlock()
}
}()
}
time.Sleep(time.Second)
mu.Lock()
fmt.Println(len(orders), orders[7])
mu.Unlock()
}
100000 2
(time.Sleep is a crude way to wait; episode 45 replaces it with sync.WaitGroup. Episode 50 covers sync.Map.)
Common mistakes (and the real error messages)
| You wrote | Real error / what happens | Fix |
|---|---|---|
map[order]int where order has a []string field |
invalid map key type order |
keys built from comparable fields |
seen[[]int{1, 2}] = true in a map[any]bool |
panic: runtime error: hash of unhashable type []int |
only put comparable values in any keys |
menu["chai"].price = 25 |
cannot assign to struct field menu["chai"].price in map |
copy, change, store back; or map[string]*item |
p := &menu["chai"] |
invalid operation: cannot take address of menu["chai"] (map index expression of struct type item) |
same as above |
| NaN as a key | no error: entries pile up, never found | avoid NaN keys; clear |
| two goroutines writing one map | fatal error: concurrent map writes |
sync.Mutex (ep 45) |
| relying on iteration order | no error: order changes (random seeds) | sort the keys |
Mini project: your own tiny hash map
Put the whole idea together: buckets, a hash, comparison with ==, and growth.
package main
import (
"fmt"
"hash/fnv"
)
type entry struct {
key string
val int
}
type HashMap struct {
buckets [][]entry
count int
}
func hash(key string) uint32 {
h := fnv.New32a()
h.Write([]byte(key))
return h.Sum32()
}
func (m *HashMap) Set(key string, val int) {
if m.buckets == nil {
m.buckets = make([][]entry, 4)
}
b := hash(key) % uint32(len(m.buckets))
for i, e := range m.buckets[b] {
if e.key == key {
m.buckets[b][i].val = val
return
}
}
m.buckets[b] = append(m.buckets[b], entry{key, val})
m.count++
if m.count > 2*len(m.buckets) { // load factor above 2: grow
old := m.buckets
m.buckets = make([][]entry, 2*len(old))
m.count = 0
for _, bucket := range old {
for _, e := range bucket {
m.Set(e.key, e.val) // rehash
}
}
}
}
func (m *HashMap) Get(key string) (int, bool) {
if m.buckets == nil {
return 0, false
}
b := hash(key) % uint32(len(m.buckets))
for _, e := range m.buckets[b] {
if e.key == key {
return e.val, true
}
}
return 0, false
}
func main() {
var m HashMap
for i := range 20 {
m.Set(fmt.Sprint("item", i), i*10)
}
m.Set("item3", 999)
v, ok := m.Get("item3")
fmt.Println(v, ok, m.count, len(m.buckets))
_, ok = m.Get("pizza")
fmt.Println(ok)
}
999 true 20 16
false
20 entries, grown from 4 to 16 buckets. Methods (func (m *HashMap)) come in episode 20; here they simply attach Set and Get to the type.
Practice
- Count how many collisions the first-letter rule and FNV-1a cause for 26 names
A..Z+"x"and 26 names all starting withS, using 8 buckets. - Change the mini project to grow when the load factor passes 4. How many buckets after 100 inserts?
- Write a program that proves a map variable is shared: pass it to a function that deletes a key.
- Make the concurrent counter safe and print the total of all values (it should be 200000).
Solutions
1.
package main
import (
"fmt"
"hash/fnv"
)
func first(s string) uint32 { return uint32(s[0]-'A') % 8 }
func fnv1a(s string) uint32 {
h := fnv.New32a()
h.Write([]byte(s))
return h.Sum32() % 8
}
func longest(names []string, f func(string) uint32) int {
count := make([]int, 8)
best := 0
for _, n := range names {
count[f(n)]++
best = max(best, count[f(n)])
}
return best
}
func main() {
var names []string
for i := range 26 {
names = append(names, fmt.Sprintf("S%c", 'a'+i))
}
fmt.Println("first letter:", longest(names, first))
fmt.Println("fnv-1a:", longest(names, fnv1a))
}
first letter: 26
fnv-1a: 4
The first-letter rule puts all 26 names in one bucket; FNV-1a spreads them (longest bucket 4, close to the average 3.25).
- Change
2*len(m.buckets)to4*len(m.buckets)and insert 100 keys. Growth happens when count passes 16, 32, 64: 4 → 8 → 16 → 32 buckets. Printinglen(m.buckets)gives:
32
3.
package main
import "fmt"
func soldOut(menu map[string]int, item string) {
delete(menu, item)
}
func main() {
menu := map[string]int{"chai": 20, "samosa": 15}
soldOut(menu, "samosa")
fmt.Println(menu)
}
map[chai:20]
4.
package main
import (
"fmt"
"sync"
"time"
)
func main() {
orders := map[int]int{}
var mu sync.Mutex
for counter := 0; counter < 2; counter++ {
go func() {
for i := 0; i < 100000; i++ {
mu.Lock()
orders[i]++
mu.Unlock()
}
}()
}
time.Sleep(time.Second)
mu.Lock()
total := 0
for _, v := range orders {
total += v
}
mu.Unlock()
fmt.Println(total)
}
200000
Quick quiz
What does this print?
func main() {
m := map[float64]int{}
m[math.NaN()] = 1
m[math.NaN()] = 2
m[1.5] = 3
m[1.5] = 4
fmt.Println(len(m))
}
- A.
2 - B.
3 - C.
4 - D. compile error
Answer
B. 3. NaN never equals NaN, so each NaN write is a new key (2 entries). 1.5 == 1.5, so the second write updates the first (1 entry). Total 3.
Interview questions
- How does a hash map find a key without searching every entry?
- What is a collision? How do hash tables deal with it?
- What is the load factor, and what happens when it gets too high?
- Why does a Go map use a random seed per map? What is hash flooding?
- Describe Go's map before Go 1.24 (buckets of 8, overflow buckets, load factor 6.5).
- What changed in Go 1.24? Explain groups, control words, H1 and H2.
- Why must map keys be comparable? What happens with a slice inside an
anykey? - What happens with NaN keys?
- Why can't you take the address of a map element?
- Is a map passed by reference? What is actually copied?
- What happens when two goroutines write to a map? How do you fix it?
Glossary
| Term | Meaning | Example |
|---|---|---|
| Linear search | checking every item in order until you find the one you want | 1,000,000 checks for the last name |
| Hash table | storage split into buckets; a key's hash picks its bucket | a Go map |
| Bucket | one place in a hash table that holds a few entries | shelf 2: [Sunil Sita Suresh Sana] |
| Hash function | a rule that turns a key into a number | FNV-1a, first-letter rule |
| Hash (hash value) | the number a hash function returns | h.Sum32() |
| Deterministic | same input always gives the same output | shelf("Ravi") is 1 both times |
| Collision | two different keys landing in the same bucket | all S names on shelf 2 |
| FNV-1a | a simple, fast hash that mixes every byte | fnv.New32a() |
| Even spread | keys distributed evenly across buckets | 2 · 2 · 2 · 2 |
| Load factor | entries ÷ buckets | 1000 ÷ 4 = 250 |
| Growth | making more buckets when the load factor is too high | 4 → 8 → 16 buckets |
| Rehashing | placing every entry again after growth | hash % newCount |
| Size hint | the second argument to make for a map |
make(map[int]int, 1000) |
| Incremental growth | moving entries a little at a time instead of all at once | old Go maps; Swiss table splits |
| Hash flooding | an attack that sends keys built to collide | thousands of keys in one bucket |
| Seed | a secret random number mixed into the hash | maphash.MakeSeed() |
hash/maphash |
package exposing the runtime's kind of seeded hash | maphash.String(seed, "chai") |
| Overflow bucket | an extra bucket chained on when one is full (old design) | bucket → overflow → overflow |
| Swiss Tables | hash table design from Google's Abseil library, used by Go since 1.24 | groups + control words |
| Abseil | Google's open-source C++ library where Swiss Tables come from | absl::flat_hash_map |
| Slot | storage for one key/value pair | 8 per group |
| Group | 8 slots plus a control word | a rack of 8 cubbies |
| Control word / control byte | 8 bytes per group, one per slot: empty, deleted, or used + 7 hash bits | the sticker strip |
| H1 / H2 | upper 57 bits (pick the group) / lower 7 bits (stored in the control byte) | |
| Probing | moving on to the next group when there's no match | quadratic probing |
| Tombstone | a "deleted" mark that keeps probe sequences working | deleting from a full group |
| Table | one complete Swiss table, at most 1024 entries in Go | |
| Directory | the array of tables a large map uses | picked by top hash bits |
| Extendible hashing | using more hash bits to pick tables as the map grows | 1 table → 2 → 4 |
| Comparable | a type whose values can be compared with == |
int, string, seat |
any |
the empty interface: holds a value of any type | map[any]bool |
| Panic | a crash while the program runs | hash of unhashable type []int |
| NaN | "not a number": the result of 0/0; never equal to itself | math.NaN() |
clear |
built-in (Go 1.21) that removes all entries | clear(m) |
| Stale pointer | a pointer to memory whose contents moved | why &m[k] is forbidden |
| Reference-like | a value that contains a pointer, so copies share data | maps, slices |
| Pass by value | arguments are copied into the function | the map pointer is copied |
unsafe.Sizeof |
size in bytes of a variable | 8 for any map variable |
| Goroutine | a function running at the same time as the rest of the program | go func() { ... }() |
| Concurrent use | more than one goroutine using the same data at the same time | two writers on one map |
| Fatal error | an error that stops the program and can't be recovered | concurrent map writes |
| Mutex / lock | lets only one goroutine at a time into a section of code | sync.Mutex, Lock, Unlock |
time.Sleep |
pauses the current goroutine | time.Sleep(time.Second) |
Summary
- A map is a hash table: hash the key (with a per-map seed), jump to its bucket, confirm with
==. - Collisions are normal; a good hash function spreads keys evenly.
- Load factor = entries ÷ buckets; too high → grow and rehash. Use a size hint in
makewhen you know the size. - A random seed per map stops hash flooding and makes iteration order vary.
- Up to Go 1.23: buckets of 8, overflow buckets, grow at 6.5 per bucket, incremental growth.
- Go 1.24: Swiss Tables: groups of 8 slots with a control word, H1/H2, at most 7/8 full, tables of ≤ 1024 entries in a directory. Up to 60% faster map operations in microbenchmarks.
- Keys must be comparable; slices inside
anykeys panic; NaN keys are never found. - No
&m[k]and nom[k].field = v: entries move. - A map variable is one pointer: passing it shares the map.
- Maps are not safe for concurrent use:
fatal error: concurrent map writes. Guard them withsync.Mutex.
Next episode: strings, bytes and runes: UTF-8, why len counts bytes, runes, immutable strings, the strings package, strings.Builder, and the bytes and unicode packages.
Sources: Faster Go maps with Swiss Tables, the Go Blog; Go 1.24 source: src/internal/runtime/maps/map.go, group.go, table.go, src/runtime/map_noswiss.go.