Hash Maps

The 30-second version

You use one every day: Go's map[string]int, JavaScript's Map and {} objects, Python's dict, Redis, database hash indexes, caches. This topic shows what happens inside: why lookups are fast, when they stop being fast, and the bugs that come from not knowing.

Try it. The top row has no rule: coats hang in the order guests arrived, so finding one means checking hooks one by one. The bottom row uses a real hash function (we'll build it in §02):

Why it matters

With 12 coats the difference is small. With a million user records it's the difference between one step and up to a million steps per lookup. In Big-O notationBig-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles. terms, a lookup by searching is O(n): the work grows with the number of items. A hash map lookup is O(1) on average: the work stays the same however big the map gets.

"On average" is the catch, and most of this topic is about it:

• Two keys can get the same slot (a collision). §03 shows how tables cope.
• A table that gets too full slows down, so it has to grow. §04 shows how, and why that's still cheap on average.
• Deleting is trickier than it looks (§05), keys need well-behaved equality (§07), and attackers can deliberately make every key collide (§11).

Hash functions: turning a key into a slot number

What a table's hash function must do

A Hash functionHash functionA function that turns any input (a string, a file) into a fixed-size number or fingerprint. The same input always gives the same output, and small changes give very different outputs — used to spread keys across buckets or servers, and (with cryptographic hashes like SHA-256) to detect tampering. for a hash table needs three properties:

1. Deterministic. The same key must always give the same number, or you'd look in the wrong bucket and never find your value again.
2. Fast. It runs on every insert and lookup. A few nanoseconds is the budget.
3. Well spread. Similar keys (user1, user2) should land far apart, so keys fill the buckets evenly instead of piling into a few.

Notice what's not on the list: being secure. Password hashing and file checksums use slow, cryptographic hashes like SHA-256. A hash table wants something much cheaper, though §11 shows why a little secrecy still helps.

A real hash function you can read: FNV-1a

(If Go syntax is new, the Go primer takes 90 seconds.) FNV-1aFNV-1aA simple, fast hash function (not for security) that gives the same result in every language and every process, so it suits anything that must agree across machines (routing, sharding, checksums of keys). is one of the simplest good hash functions. Start from a fixed number, then for each ByteByte8 bits — enough to store a number from 0 to 255, or one ASCII character. Network speeds are usually quoted in bits per second, file sizes in bytes. of the key: mix the byte in with XORXORA bit operation: each output bit is 1 if exactly one of the two input bits is 1. XOR a byte with a key and you get scrambled bits; XOR the result with the same key again and you get the original back., then multiply by a prime to smear those bits across the whole number.

func fnv1a(s string) uint32 {
    h := uint32(2166136261)   // the "offset basis": a fixed start value
    for i := 0; i < len(s); i++ {
        h ^= uint32(s[i])     // mix in one byte
        h *= 16777619         // the FNV prime: spreads the bits around
    }
    return h
}

fmt.Println(fnv1a("apple"), fnv1a("apples")) // 280767167 607608612

Go and Node print the same numbers, because both run the same steps on the same bytes. Go also ships this function as hash/fnv (fnv.New32a()), and gives the same 280767167 for "apple". Notice that adding one letter changed the hash completely. That's the "well spread" property at work.

From a big number to a bucket

The hash is a number up to about 4 billion; the table might have 8 buckets. The classic way to shrink it is the remainder, moduloModulo (%)The remainder after division: 17 % 8 = 1, because 17 = 2 × 8 + 1. For a non-negative number it gives a result between 0 and n−1, which is exactly what a bucket index needs. (In Go and JS a negative left side gives a negative result: -7 % 3 is -1.): 280767167 % 8 = 7, so "apple" goes in bucket 7.

Real tables usually keep their size a power of two (8, 16, 32…) for a neat reason: then h % size equals h & (size - 1), a bit maskBit mask (& (n−1))Keeping only the lowest bits of a number with bitwise AND. When n is a power of two, h & (n−1) gives the same answer as h % n, but in a single fast CPU instruction. that just keeps the last few bitsBitThe smallest unit of data: a single 0 or 1. Eight bits make a byte.. With 8 buckets, size - 1 is binary 111, so the bucket is the hash's last 3 bits. One AND instruction instead of a much slower division.

Play with it. Watch the bytes get mixed in one at a time, and the highlighted last bits become the bucket:

Collisions: chaining vs open addressing

Collisions are guaranteed

There are endless possible string keys but only, say, 8 buckets. By the pigeonhole principlePigeonhole principleIf you put more than n items into n boxes, at least one box gets two. With more possible keys than buckets, some keys must share a bucket., as soon as you store 9 keys, at least two share a bucket. Even a perfect hash function can't avoid that.

Worse, collisions show up long before the table is full. Here's one: with 8 buckets, "banana" and "cherry" both land in bucket 0 (type them into the widget in §02 to check). This is the birthday paradoxBirthday paradoxWith just 23 people, there's a better than even chance two share a birthday. In general, a collision becomes more likely than not after about 1.2 × √(number of buckets) random keys — long before the table is full.: in a room of only 23 people, two probably share a birthday, even though there are 365 days to choose from.

Rule of thumb: with m buckets, the chance of a collision passes 50% after about 1.2 × √m keys. That's the 23 for 365 and the 38 for 1,000 you see in the widget. The point is that it grows with √m, not with m: a table with a million buckets will probably have a collision after only about 1,200 keys. So every hash table needs a plan for collisions from day one.

Plan A: separate chaining

In separate chainingSeparate chainingA collision strategy where each bucket holds a small list of all the keys that hashed there. A lookup hashes to the bucket, then walks its list., each bucket holds a small list (a "chain") of every key that hashed there.

• Insert: hash to the bucket, append to its list.
• Lookup: hash to the bucket, then compare your key against each key in that list, one by one.

It's simple and never "fills up": lists just get longer. The cost is memory and speed: each list entry is usually its own separately created piece of memory (an Memory allocationMemory allocationAsking for a piece of memory to store a value. Stack allocation is nearly free; heap allocation costs more and the memory must later be freed — by you (C), or by a garbage collector (Go, JS).) reached through a PointerPointer (*T, &v)A value that holds the memory address of another value instead of a copy of it. In Go, &v takes v's address and *T is the type “pointer to T”; changes made through a pointer are seen by everyone holding it. JS objects behave like this automatically., which is slow to follow (see CPU Caches §04). Java's HashMap is a chaining design, and so was Go's map before Go 1.24 (with up to 8 keys per bucket before it chains on an extra bucket).

Plan B: open addressing

In open addressingOpen addressingA collision strategy where every key lives directly in the array, one per slot. If a key's home slot is taken, it tries other slots in a fixed order (probing) until it finds a free one., there are no lists. Every key lives directly in the array, one key per slot. If a key's home slot is taken, it tries other slots in a fixed order until one is free. The simplest order is linear probingLinear probingThe simplest open-addressing order: if slot i is taken, try i+1, then i+2, and so on, wrapping around at the end. Fast on CPUs because the slots it checks sit next to each other in memory.: try the next slot, then the next, wrapping around at the end.

• Insert: start at the home slot; step forward until you find an empty slot.
• Lookup: start at the home slot; step forward until you find the key (hit) or an empty slot (miss: if the key existed, it would have been placed before this gap).

Each slot you look at is one probeProbeOne slot (or bucket) a lookup has to look at. Counting probes is how you measure how much work a lookup did.. Neighbouring slots sit side by side in memory, which makes probing cache-friendly: the CPU copies memory into its small, fast CPU cacheCPU cacheSmall, very fast memory on the CPU chip (L1, L2, L3) that keeps copies of recently used data. Reading from cache takes ~1–10 ns; reading from RAM takes ~100 ns. in 64-byte chunks, so when it reads one slot, the next few slots usually arrive in the same chunk for free. A chaining list node somewhere else in memory needs a fresh, slow trip to RAM. Most modern fast tables (Go's since 1.24, Rust's, Google's Abseil, Python's dict) use some form of open addressing.

See both, side by side

Same keys, same real hash, same 8 buckets. Insert the keys one at a time, then look up a few, including the missing lemon and fig:

Watch what happens at slots 0–3 on the right. banana, cherry and grape all want slot 0, so they fill 0, 1, 2. Then kiwi, whose home is slot 1, gets pushed all the way to slot 3, even though nothing else hashed to 1. Runs of full slots grow, and anything landing in a run makes it longer. This is called clusteringClusteringIn linear probing, full slots tend to clump into long runs: any key that lands anywhere in a run gets added at its end, making the run longer still. Long runs mean long lookups., and it's why, once the first five keys are in, looking up the missing lemon takes 5 probes on the right but only 3 comparisons on the left.

Neither is "wrong". Open addressing usually wins on speed for small keys and values; chaining degrades more gracefully when the table gets very full. The next section is about not letting it get that full.

Load factor and resizing

Fuller tables are slower tables

6 keys in 8 slots is a load factor of 6/8 = 0.75. As it rises, two things happen: more collisions (chaining lists get longer), and with open addressing, longer runs of full slots (the clustering from §03). A missing key suffers most, because its lookup has to walk to the end of a run before it can say "not here".

Drag the slider and watch the runs grow. The numbers are probe counts on this one table, so they're exact, not timings:

The curve isn't a straight line; it explodes near full. For linear probing, the textbook estimate for a miss is about ½ · (1 + 1/(1 − α)²) probes, where α is the load factor: 2.5 at α = 0.5, 8.5 at 0.75, 50 at 0.9. That's why every open-addressing table sets a maximum load factor and grows before reaching it. Common limits: 0.75 for many textbook tables, 7/8 for Go's Swiss tables (§09), which check 8 slots at once and so tolerate fuller tables.

Growing: double, then rehash everything

You can't just copy the old array into the start of a bigger one. A key's slot is hash % size, so when the size changes, the slot changes. Growing means allocating the new array and re-inserting every key into it: rehashingRehashingRe-inserting every key into a new, bigger array when a table grows. Each key's slot is computed again from its hash, because the slot number depends on the table size.. (The key's hash doesn't change; only the bucket picked from it.)

Step through a real one. The table holds at most 3/4 of its slots, so the 4th key triggers a grow from 4 to 8 slots:

1func (m *Map) Put(key string, val int) {
2    if (m.count+1)*4 > len(m.slots)*3 { // > 3/4?
3        m.grow() // double, re-insert all
4    }
5    mask := len(m.slots) - 1
6    i := int(hash(key)) & mask
7    for m.slots[i].full { // probe on
8        i = (i + 1) & mask
9    }
10    m.slots[i] = slot{true, key, val}
11    m.count++
12}

With a power-of-two size, doubling just means using one more bit of the hash. That's why each key's home slot either stays the same (the new bit is 0: kiwi stays at 1) or moves up by exactly the old size (the new bit is 1: mango's home moves from 1 to 1 + 4 = 5). Keys that collided often stop colliding.

Expensive sometimes, cheap on average

A grow copies every key, so that one insert costs O(n). That sounds bad until you count how rarely it happens. Because the size doubles each time, the next grow is twice as far away. Add up all the work:

Count it for n inserts. The grows copy 1 + 2 + 4 + … keys, and the last grow copies fewer than n (there were fewer than n keys when it happened). Each term is double the one before, so the whole sum is less than twice the last term: under 2n copies in total. Add the n inserts themselves, and n inserts do under 3n units of work: fewer than 3 per insert, however large n gets. (Slide the widget to 33 inserts: the 33rd insert copies 32 keys, and the average jumps to 2.91.) That's an amortizedAmortized costThe average cost per operation over a long sequence, when most operations are cheap and a rare one is expensive — e.g. appending to a slice is O(1) amortized even though an occasional append copies everything. O(1) insert: the occasional expensive step is paid for by all the cheap ones around it. Big-O §06 covers amortized analysis in general; Go's append grows slices the same way (Stack & Heap).

When "cheap on average" isn't good enough

Amortized O(1) still means that one insert, somewhere, copies the whole table. For a map with 50 million entries, that one insert can take a long time, and the request that triggered it sees a p99p99 (99th percentile)The value that 99% of measurements are below — i.e. how bad the slowest 1% is. Averages hide slow outliers; p99 shows them. latency spike. Two ways around it:

• Incremental resizing. Incremental resizingIncremental resizingGrowing a hash table a little at a time: each insert or delete moves a few old entries to the new array, instead of one operation pausing to move them all. allocates the new array but keeps the old one, and every later insert or delete moves a few old buckets across. Lookups check both arrays until the move is done. Go's map up to Go 1.23 worked this way ("evacuating" two buckets per write), and Redis rehashes its dictionaries in small steps for the same reason.
• Many small tables. Go 1.24's Swiss-table map caps each internal table at 1,024 slots and splits a full table into two, so a single grow never copies more than about a thousand entries, no matter how large the map is (§09).

Both trade a little complexity for no single huge pause.

Build one: linear probing, tombstones and growth

The deletion trap

Recall the lookup rule from §03: probe forward until you find the key, or an empty slot. An empty slot proves the key isn't there, because an insert would have used that gap.

Deleting breaks that proof. If you empty a slot in the middle of a run, every key placed after it in the run becomes unreachable. Step through both ways to delete cherry:

1func (m *Map) find(key string) int {
2    mask := len(m.slots) - 1
3    i := int(hash(key)) & mask
4    for {
5        s := m.slots[i]
6        if s.state == empty {
7            return -1 // stop: not here
8        }
9        if s.state == full && s.key == key {
10            return i
11        }
12        i = (i + 1) & mask // keep going
13    }
14}

A tombstoneTombstoneA marker meaning “this key was deleted”, left in place of actually erasing it. An LSM tree writes one because it can't edit its immutable files (compaction removes both later); an open-addressing hash table leaves one in the slot so lookups for later keys keep probing past it. is a third slot state, between "empty" and "full":

Tombstones have a cost: they still lengthen probe paths, so a table with lots of deletes slows down even if few keys are live. That's why our table counts tombstones toward its load factor, and why a grow throws them all away (it re-inserts live keys only). Separate chaining doesn't have this problem: deleting just unlinks one entry from one list.

The whole thing in one sitting

Here's a complete string-keyed map with linear probing, tombstones and doubling. It's a teaching toy (use the built-in map!), but every piece maps to a real design decision from §02–§05.

type state uint8

const (
    empty   state = iota // never used: a lookup can stop here
    full                 // holds a live key
    deleted              // tombstone: "keep probing past me"
)

type slot[V any] struct {
    state state
    key   string
    val   V
}

type Map[V any] struct {
    slots []slot[V] // length is always a power of two
    count int       // live keys
    used  int       // live keys + tombstones (both lengthen probes)
}

func New[V any]() *Map[V] { return &Map[V]{slots: make([]slot[V], 8)} }

// find returns the slot index holding key, or -1.
func (m *Map[V]) find(key string) int {
    mask := len(m.slots) - 1
    for i := int(hash(key)) & mask; ; i = (i + 1) & mask {
        switch s := &m.slots[i]; {
        case s.state == empty:
            return -1 // ← empty ends the search
        case s.state == full && s.key == key:
            return i
        } // tombstone or another key: keep probing
    }
}

func (m *Map[V]) Get(key string) (V, bool) {
    if i := m.find(key); i >= 0 {
        return m.slots[i].val, true
    }
    var zero V
    return zero, false
}

func (m *Map[V]) Put(key string, val V) {
    if i := m.find(key); i >= 0 {
        m.slots[i].val = val // existing key: update in place
        return
    }
    if (m.used+1)*4 > len(m.slots)*3 { // would pass 3/4 full?
        m.grow()
    }
    mask := len(m.slots) - 1
    i := int(hash(key)) & mask
    for m.slots[i].state == full { // stop at empty OR tombstone
        i = (i + 1) & mask
    }
    if m.slots[i].state == empty {
        m.used++ // reusing a tombstone doesn't raise used
    }
    m.slots[i] = slot[V]{full, key, val}
    m.count++
}

func (m *Map[V]) Delete(key string) {
    if i := m.find(key); i >= 0 {
        m.slots[i] = slot[V]{state: deleted} // ← tombstone, not empty
        m.count--
    }
}

func (m *Map[V]) grow() {
    old := m.slots
    size := len(old)
    if m.count*2 >= size { // mostly live keys → double;
        size *= 2          // mostly tombstones → same size, cleaned
    }
    m.slots = make([]slot[V], size)
    m.count, m.used = 0, 0
    for _, s := range old {
        if s.state == full {
            m.Put(s.key, s.val) // rehash into the new array
        }
    }
}

hash is the fnv1a function from §02 under a shorter name. To run the code, add func hash(s string) uint32 { return fnv1a(s) } in Go, or const hash = fnv1a; in JS. Using the map:

m := New[int]()
for i, k := range []string{"banana", "cherry", "grape", "apple"} {
    m.Put(k, i)
}
m.Delete("cherry")
fmt.Println(m.Get("grape")) // 2 true  ← found past the tombstone

Using Go's map well

Creating, reading, writing

counts := map[string]int{} // or make(map[string]int), or make(map[string]int, 1000)
for _, w := range strings.Fields("the cat saw the dog") {
    counts[w]++ // ← a missing key reads as 0, so counting just works
}
fmt.Println(counts["the"], counts["zebra"]) // 2 0

n, ok := counts["zebra"] // "comma-ok": was the key really there?
fmt.Println(n, ok)       // 0 false

delete(counts, "cat")    // no-op if the key isn't there
fmt.Println(len(counts)) // 3

Rule 1: a nil map can be read, but not written

var m map[string]int   // declared, never made: m is nil
fmt.Println(m["x"], len(m)) // 0 0   ← reading is fine
m["x"] = 1             // panic: assignment to entry in nil map

A nil map has no table at all, so there's nowhere to put the key. This usually bites in structs: a map field starts as nil, so give the struct a constructor that calls make, or create the map on first use.

Rule 2: iteration order is random, on purpose

ages := map[string]int{"ana": 31, "ben": 25, "cleo": 40, "dan": 19}
for run := 1; run <= 3; run++ {
    for name := range ages {
        fmt.Print(name, " ")
    }
    fmt.Println()
}

dan ana ben cleo
ana ben cleo dan
dan ana ben cleo

The language spec says the order is unspecified, and the runtime goes further: every range loop starts at a random position. That way, nobody's code can come to depend on an order that a future Go version might change. Small maps often look stable, as two runs above do. Don't be fooled.

When you need an order, sort the keys:

for _, name := range slices.Sorted(maps.Keys(ages)) {
    fmt.Print(name, "=", ages[name], " ") // ana=31 ben=25 cleo=40 dan=19
}

Rule 3: values are copies, so structs need care

type User struct{ Name string; Visits int }
users := map[string]User{"ana": {Name: "Ana"}}

users["ana"].Visits++
// compile error: cannot assign to struct field users["ana"].Visits in map

users["ana"] hands you a copy of the struct, and changing a field of a temporary copy would do nothing, so the compiler refuses. The map is also free to move its entries around when it grows, which is why you can't take a pointer into it either (&users["ana"] is a compile error too). Two fixes:

u := users["ana"]   // copy out
u.Visits++          // change the copy
users["ana"] = u    // write it back

ptrs := map[string]*User{"ana": {Name: "Ana"}}
ptrs["ana"].Visits++ // changes the User it points to

The labels are a bit unfair: both are fine. Copy-and-write-back keeps values compact inside the table; pointers make updates easy but add an allocation and a PointerPointer (*T, &v)A value that holds the memory address of another value instead of a copy of it. In Go, &v takes v's address and *T is the type “pointer to T”; changes made through a pointer are seen by everyone holding it. JS objects behave like this automatically. hop per entry. For small structs, copying is usually faster.

Rule 4: a map is a reference

A map variable holds a pointer to the runtime's table. Passing a map to a function, or assigning it to another variable, shares the same table:

func addVisit(m map[string]int) { m["ana"]++ }

visits := map[string]int{}
addVisit(visits)
fmt.Println(visits["ana"]) // 1  ← the function changed our map

To get an independent copy, use maps.Clone(m).

The toolbox: clear and the maps package

Deleting entries while ranging over the same map is allowed and safe. Adding entries while ranging is allowed too, but the new entries may or may not show up in that loop.

Rule 5: concurrent writes crash the program

m := map[int]int{}
var wg sync.WaitGroup
for g := 0; g < 2; g++ {
    wg.Add(1)
    go func() {
        defer wg.Done()
        for i := 0; i < 1_000_000; i++ {
            m[i] = i // two goroutines writing one map, no lock
        }
    }()
}
wg.Wait()

fatal error: concurrent map writes

goroutine 17 [running]:
internal/runtime/maps.fatal({0x47eb71?, 0x0?})
...

A map write may move entries around (§04, §05), and a second goroutine in the middle of that could corrupt memory. So Go's map keeps a cheap "someone is writing" flag, and if it catches two goroutinesGoroutineA very lightweight task in Go, started with the go keyword. The Go runtime runs thousands of them on just a few OS threads. at it, it stops the program with a fatal errorFatal error (Go)A runtime failure that ends the program immediately. Unlike a panic, it can't be caught with recover(). Go uses it for problems like concurrent map writes, where carrying on could corrupt memory., which, unlike a panic / recoverpanic / recoverpanic is Go's crash-the-program error (like an uncaught throw). recover, called inside a deferred function, catches it — but only in the same goroutine., recover() can't catch. The check is best-effort: it can miss races. go test -race is far more reliable, though it too only reports races that actually happen while it runs, so your tests need to exercise the concurrent paths (Race Conditions).

Concurrent reads are fine. Any write mixed with reads or writes from other goroutines needs protection. The standard fix is a mutexLock (mutex)A “do not disturb” sign for a piece of data: only the task holding the lock may touch it; others wait their turn. next to the map:

type SafeCounts struct {
    mu sync.Mutex
    m  map[string]int
}

func (c *SafeCounts) Inc(key string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.m[key]++
}

The Locks topic covers mutexes, sync.RWMutex for read-heavy maps, and splitting one map into many independently locked shards (Locks §10). sync.Mapsync.MapA map type in Go's sync package that many goroutines can use at once without your own lock. It's tuned for two cases: keys written once and read many times, or goroutines working on separate keys. is a ready-made concurrent map, but it's tuned for two specific patterns (write-once/read-many caches, or goroutines touching separate keys). For anything else, a plain map plus a mutex is usually simpler and as fast.

What makes a good key: equality, composite keys and NaN

Every lookup does two things: hash the key to find the right bucket, then compare with == (or the language's equivalent) to find the right entry inside it. So a key type needs a hash and an equality check that agree with each other.

Go: only comparable types can be keys

Go allows a type as a map key only if it's comparablecomparable (Go)Go's name for types whose values can be checked with ==: numbers, strings, bools, pointers, channels, interfaces, and structs or arrays made only of those. Only comparable types can be map keys. Slices, maps and functions are not.: values can be checked with ==. Numbers, strings, bools, pointers and channels are; so are structs and arrays made only of those. That makes composite keys easy:

type Point struct{ X, Y int }

visited := map[Point]bool{}
visited[Point{3, 4}] = true
fmt.Println(visited[Point{3, 4}]) // true  ← a NEW Point, same fields: equal

pairs := map[[2]string]int{}      // an array of 2 strings as the key
pairs[[2]string{"ana", "ben"}]++
pairs[[2]string{"ana", "ben"}]++
fmt.Println(pairs)                // map[[ana ben]:2]

Slices, maps and functions have no ==, so they can't be keys. The compiler catches it:

m := map[[]int]string{} // compile error: invalid map key type []int

With any (interface) keys, the check moves to run time: m[[]int{1}] = 3 on a map[any]int compiles, then panics with runtime error: hash of unhashable type []int.

JavaScript: objects are compared by identity

A JS Map accepts any value as a key, including objects. But two objects are the same key only if they are the same object, not if they look the same. This is one of the most common Map bugs:

const m = new Map();
m.set({ x: 1 }, "A");
console.log(m.get({ x: 1 })); // undefined  ← a different object

const k = { x: 1 };
m.set(k, "B");
console.log(m.get(k));        // "B"  ← the same object

The usual fix is to turn composite keys into a string (or number) with a fixed format:

const grid = new Map();
grid.set(`${3},${4}`, "tree");   // key "3,4"
console.log(grid.get("3,4"));    // "tree"

A plain object does something worse with object keys: it silently converts them to the string "[object Object]", so every object key collides with every other.

const o = {};
o[{ x: 1 }] = "A";
console.log(Object.keys(o), o[{ y: 2 }]); // [ '[object Object]' ] A   ← oops

Never change a key after inserting it

The hash is computed once, at insert time. If the key's contents change afterwards, its new hash points to a different bucket, and the entry is stranded in the old one. Go prevents this for you: keys are copied into the map, and you can't modify them in place. In languages where keys can be mutable objects compared by contents (Java's HashMap with a mutable key, for example), this is a classic bug. JS Map avoids it differently: object keys compare by identity, so changing an object's fields doesn't change which key it is.

The NaN trap

NaNNaN“Not a Number”: the floating-point value you get from 0/0 or the square root of −1. It's defined to be unequal to everything, including itself, so NaN == NaN is false. ("not a number", e.g. the result of 0.0/0.0) has a famous property: NaN == NaN is false. That breaks the promise above:

m := map[float64]string{}
nan := math.NaN()
m[nan] = "first"
m[nan] = "second"   // doesn't overwrite: NaN != NaN, so it's a new key
v, ok := m[nan]
fmt.Println(len(m), v == "", ok) // 2 true false

Each insert adds a new, unfindable entry. Only range (which prints both, in some order) or clear(m) can reach them. If float keys might be NaN, check with math.IsNaN first, or avoid float keys altogether (they also have rounding surprises: with a, b := 0.1, 0.2, the key a + b is not the same key as 0.3).

JavaScript chose differently. Map and Set compare keys with SameValueZeroSameValueZeroThe equality rule JavaScript's Map and Set use for keys. It's like === except that NaN equals NaN. (+0 and −0 count as the same key, just as with ===.), which treats NaN as equal to itself:

const nm = new Map([[NaN, "nan"]]);
console.log(nm.get(NaN));                  // "nan"  ← found
console.log(new Set([1, "1", NaN, NaN]).size); // 3: 1 and "1" differ, the NaNs merge

JavaScript: Map, plain objects, Set and WeakMap

Map in 30 seconds

const ages = new Map();
ages.set("ana", 31).set("ben", 25);  // set returns the map, so calls chain
ages.get("ana");                     // 31
ages.has("zoe");                     // false
ages.delete("ben");                  // true
ages.size;                           // 1
for (const [name, age] of ages) {    // insertion order, always
  console.log(name, age);
}

Why plain objects make awkward maps

1. They come with keys you didn't add. Every {} inherits from Object.prototype through its prototypePrototype (JS)The object a JavaScript object falls back to when a property isn't found on it. Every plain {} inherits from Object.prototype, which is why {} already “has” keys like toString and constructor., so it already "has" toString, constructor, hasOwnProperty and more. A word counter built on {} breaks on real text:

const counts = {};
for (const w of ["toString", "constructor", "hello"]) {
  counts[w] = (counts[w] || 0) + 1;
}
console.log(counts);

{
  toString: 'function toString() { [native code] }1',
  constructor: 'function Object() { [native code] }1',
  hello: 1
}

counts["toString"] wasn't missing: it found the inherited function, and function + 1 made a string. Likewise "constructor" in {} is true. And the key "__proto__" is special: o["__proto__"] = "hi" on a plain object doesn't create a key at all.

2. Keys are always strings (or symbols). o[1] and o["1"] are the same key, and object keys become "[object Object]" (§07). Map keeps 1 and "1" apart and accepts any value as a key.

3. The order has a twist. Objects list integer-like keys first, in ascending order, then other keys in insertion order. Map always uses insertion order:

Object.keys({ b: 1, 2: "two", a: 2, 1: "one" });  // [ '1', '2', 'b', 'a' ]
[...new Map([["b", 1], [2, "two"], ["a", 2], [1, "one"]]).keys()]; // [ 'b', 2, 'a', 1 ]

4. No cheap size. map.size is instant; for an object you build an array with Object.keys(o).length.

If you must use an object as a dictionary (say, for JSONJSONJavaScript Object Notation: a text format for data — {"id": 7, "tags": ["a"]}. Readable by humans and every language; the default body format for web APIs. you're about to send), create it without a prototype and check keys with Object.hasOwn:

const dict = Object.create(null); // no prototype: no inherited keys at all
dict["constructor"] = 1;          // just an ordinary key now
dict["__proto__"] = "hi";         // also an ordinary key
console.log(Object.keys(dict));   // [ 'constructor', '__proto__' ]
Object.hasOwn({}, "constructor"); // false: ignores inherited keys

What the engine does with each (V8, simplified)

V8 (the engine in Chrome and Node) treats objects as records first. Objects created with the same properties in the same order share a Hidden classHidden class (V8 “map”)V8's internal description of an object's shape: which properties it has, in what order, and where each one is stored. Objects built the same way share one hidden class, which lets V8 store them compactly and read properties fast., which lets V8 store fields at fixed positions and read them very fast, like a Go struct.

When an object is used as a dictionary instead, with many keys added and deleted at run time, V8 gives up on that layout and switches it to dictionary modeDictionary mode (V8)V8's slow-but-flexible fallback for objects whose shape keeps changing (many added or deleted keys): it stores the properties in an internal hash table instead of using a fixed hidden-class layout.: the properties move into an internal hash table. It still works, but you lose the record fast path, and the switch itself costs time. Map is a hash table from the start, designed for frequent adds and deletes. (These are engine internals: they explain the advice, but they change between versions, so measure rather than relying on them; §10 has numbers.)

Set: a hash map with only keys

A Set stores unique values with fast has checks, using the same key rules as Map (§07):

const seen = new Set();
for (const id of [3, 1, 3, 2, 1]) seen.add(id);
console.log(seen.size, [...seen]); // 3 [ 3, 1, 2 ]
console.log(seen.has(2));          // true

Go has no built-in set; use map[T]struct{} (or map[T]bool for readability).

WeakMap: data attached to objects you don't own

A WeakMap only accepts objects (and non-registered symbols) as keys, and holds them weakly: it's a Weak referenceWeak referenceA reference that lets you reach an object without keeping it alive. If only weak references remain, the GC may collect the object and the weak reference then gives you nothing. map. If nothing else references a key object, the garbage collector may delete it, and its entry disappears with it.

const metadata = new WeakMap();
function track(el) {
  metadata.set(el, { clicks: 0 }); // no leak: dies with el
}
new WeakMap().set("str", 1);
// TypeError: Invalid value used as weak map key

That makes it perfect for caches and extra data hung on objects (DOM nodes, request objects) without keeping them alive forever. The price: you can't iterate a WeakMap or ask its size, because its contents depend on when the GC runs. See Garbage Collection for why.

Inside Go's map: Swiss tables (Go 1.24+)

Everything below comes from the Go 1.24 source in internal/runtime/maps (its design comment is well worth reading), with later changes noted where we checked the Go 1.25 and 1.26 sources. It's an implementation detail: the language only promises how maps behave, and the internals may change again.

The layout: groups and control bytes

A table is an array of groups. Each group holds 8 key/value slots plus an 8-byte control word: one control byteControl byteIn a Swiss table, one byte of metadata per slot: “empty”, “deleted”, or “full, and here are 7 bits of the key's hash”. Checking control bytes first avoids most full key comparisons. per slot.

• Empty slot: control byte 1000 0000.
• Deleted slot (tombstoneTombstoneA marker meaning “this key was deleted”, left in place of actually erasing it. An LSM tree writes one because it can't edit its immutable files (compaction removes both later); an open-addressing hash table leaves one in the slot so lookups for later keys keep probing past it.): 1111 1110. A delete only leaves one when the group is full. If the group still has an empty slot, no probe can have continued past this group, so the slot is simply marked empty (the §05 problem can't arise).
• Full slot: 0 followed by 7 bits of the key's hash.

The 64-bit hash is split in two (H1 and H2H1 / H2The two pieces Go's Swiss table splits a 64-bit hash into. H1 (the upper 57 bits) picks where to start looking; H2 (the low 7 bits) is a tiny fingerprint stored in the slot's control byte.): H1, the upper 57 bits, picks which group to start at; H2, the low 7 bits, is the fingerprint stored in the control byte.

A lookup, step by step

1. Hash the key; split into H1 and H2.
2. Go to group H1 & (number of groups − 1).
3. Compare H2 against all 8 control bytes at once. Each match is a candidate.
4. Compare the full key only in candidate slots. Since H2 has 7 bits, an unrelated full slot matches by accident only 1 time in 128, so most lookups do zero or one real key comparison.
5. If the group has an empty slot and no match, the key isn't in the map. Otherwise, move to the next group and repeat.

Try it on a small table. pumpkin's home group is full, so it was pushed into group 1; lychee shares its 7-bit fingerprint with two keys there (a false alarm the key comparison catches); kale is rejected without comparing a single key:

"8 comparisons at once"

Step 3 is the trick that gives Swiss tables their speed. On x86-64 CPUs (Go calls them amd64), Go compiles it to SIMDSIMDSingle Instruction, Multiple Data: CPU instructions that do the same operation on several values packed side by side, e.g. compare 8 or 16 bytes against one value at once. instructions that compare 8 bytes to one value in parallel. On other CPUs it uses plain 64-bit arithmetic on the whole control word (a technique called SWAR, "SIMD within a register"); here's the portable version from the Go source:

// bitsetLSB = 0x0101010101010101, bitsetMSB = 0x8080808080808080
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset {
    v := uint64(g) ^ (bitsetLSB * uint64(h)) // bytes equal to h become 0x00
    return bitset(((v - bitsetLSB) &^ v) & bitsetMSB) // flag each 0x00 byte
}

Probing between groups

When a group is full, the lookup moves on with quadratic probingQuadratic probingAn open-addressing order where each jump is one longer than the previous: from the home position h, try h+1, h+3, h+6, h+10… (gaps of 1, 2, 3, 4). It escapes crowded areas faster than linear probing and breaks up its long runs. over groups: each jump is one group longer than the previous one, so it visits start, start+1, start+3, start+6, start+10… (the gaps are 1, 2, 3, 4; the offsets are the "triangular" numbers, as Go's source calls them). With a power-of-two number of groups, this visits every group exactly once, wrapping around the end. Compare it with linear probing:

Linear probing crawls through a crowded neighbourhood one step at a time; the growing jumps leave it quickly, which breaks up the long runs from §04. Because each probe already covers 8 slots, Go lets a table fill up to a load factor of 7/8 before growing (§04).

Small maps are a special case: a map that has only ever held 8 or fewer entries is just one group, with no table around it. Lookups scan it directly.

Growing without a huge pause

A full table's group count must double, and since every key's probe sequence depends on that count, all of its keys must be reinserted at once (§04). To keep that bounded, a Go map is really a directory of tables, each capped at 1,024 slots:

• The top bits of the hash pick a table from the directory (extendible hashingExtendible hashingSplitting one big hash table into many smaller ones and using the top bits of the hash to pick which small table a key belongs to. Each small table grows on its own, so no single grow has to move everything.). With a directory of 4 entries, the top 2 bits decide.
• A table below the cap grows by doubling, as you'd expect.
• A table at the cap splits into two tables, each taking half of the hash space, and the directory doubles if needed.

So no single insert ever rehashes more than about a thousand entries, however big the map is. That's how Go kept the "no big pause" property of its old incremental resizing (§04) while switching designs.

What Go had before (≤ 1.23)

Go 1.24 and 1.25 can still build the old map with GOEXPERIMENT=noswissmap, which is how we compared them on this machine in §10; Go 1.26 removed the old map entirely. The Go team reported typical map operations getting noticeably faster, and lower memory use for large maps; treat the exact percentages as workload-dependent.

Randomness, built in

Two more details from the same source explain behaviour you saw in §06:

• Each map gets its own random hash seed when it's created, and a new one whenever it's emptied by clear or by deleting its last key. Two maps with the same keys lay them out differently. §11 explains why that matters for security.
• Each range loop starts at a random table in the directory and a random slot offset, which is where the random iteration order comes from. In a small one-group map, that offset only rotates the order (§06's output was rotations of one sequence), but you still can't rely on it.

Performance, measured

All numbers below were measured on this site's build machine: a shared 4-core Intel Xeon VM at 2.3 GHz, Go 1.24.7 and Node 22. Shared VMs are noisy, so each figure is a range over repeated runs. Use them for ratios, not absolute promises, and run a BenchmarkBenchmarkA small program that runs one piece of code many times and measures how long it takes (and, in Go with -benchmem, how many bytes and allocations it makes per run). on your own hardware before acting on them.

Lookup cost depends on size and key type

for b.Loop() {               // Go 1.24's benchmark loop
    sink += m[keys[i]]       // look up a key we know is there
    i = (i + 7919) % n       // jump around so we don't walk memory in order
}

Three lessons:

• Size matters, even though it's O(1). A 1,000-entry map fits in the CPU cacheCPU cacheSmall, very fast memory on the CPU chip (L1, L2, L3) that keeps copies of recently used data. Reading from cache takes ~1–10 ns; reading from RAM takes ~100 ns.; a million entries (about 38 MB, see below) doesn't, so most lookups wait for a cache missCache hit / cache missA hit means the data asked for was already in the cache — fast. A miss means it wasn't, so it must be fetched from the slower source: for a CPU cache the next cache level or RAM, for an app cache the database or another service. from RAM. Same algorithm, ~8× slower. See CPU Caches.
• String keys cost more. The hash has to read every byte of the string, and the slot only stores a pointer to the string's bytes, so a lookup also follows that pointer to compare them: one more potential cache miss (pointer chasing).
• For tiny maps, a slice can tie. Up to about 8 small keys, scanning a slice is as fast as a map. CPU Caches §10 measures that crossover, so we won't repeat it here.

Running the same lookups with the old map (GOEXPERIMENT=noswissmap) gave ~115–140 ns for 1M int keys versus ~65–105 ns with Swiss tables: consistent with the Go team's reports, but this VM is too noisy to put a precise number on it.

Pre-sizing: skip the grows

m := make(map[int]int)    // grows 1 → … as keys arrive
m := make(map[int]int, n) // allocated for n keys up front

At a million keys the gap was smaller in time (~255 ms vs ~180–210 ms) but the same in memory churn: 75 MB allocated growing versus 38 MB pre-sized. The rehashing from §04 is real work, and the discarded tables are garbage the Garbage collectorGarbage collector (GC)Part of the language runtime that automatically frees memory nobody can reach anymore. Anything still referenced — like a stuck goroutine — is never freed. has to clean up.

Memory per entry

A map[int64]int64 stores 16 bytes of actual data per entry. Measured heap growth after inserting 1,000,000 entries:

The map costs about 2.3× the raw data: empty slots kept free to stay under the maximum load factor (§04), plus a control byte per slot. And how full the table happens to be (just after a grow, or just before one) moves this number by up to 2×.

JavaScript: Map vs object

1,000,000 string keys like "user:123" in Node 22 (median of 5 runs, two separate runs shown as a range):

The honest summary: same ballpark, varying from run to run. Map was a little faster to fill, the object a little faster to read in this test, and either can win in your workload. Choose by semantics (§08), not by these numbers.

Staff-level: hash flooding, concurrent maps and cousins

Hash flooding: making every key collide

Suppose a server puts request parameters, JSON keys or HTTP headers into a hash map, and the hash function is public and fixed. An attacker can compute, offline, thousands of keys that all land in the same bucket. Every insert then scans one long list, so n keys cost about n²/2 comparisons instead of n. A single request of a few hundred KB can keep a CPU core busy for seconds. That's hash floodingHash floodingAn attack where someone sends many keys chosen to collide in one bucket, turning each O(1) lookup into an O(n) scan and making a server burn CPU. Defended against with seeded hash functions., a denial-of-serviceDenial of service (DoS)Making a service unusable for its real users — for example by sending requests that tie it up with so much work it can't answer anyone else. Unlike a DDoS, one attacker with one machine can be enough. attack (one attacker with one machine is enough); in 2011 researchers showed it worked against the default hash tables of PHP, Java, Python, Ruby and others.

The defence is a hash seedHash seedA secret random number mixed into a hash function. The same key gives a different hash under a different seed, so outsiders can't predict where keys will land.: a secret random number mixed into the hash, chosen when the process (or, in Go, each map) starts. The attacker no longer knows which keys collide, so precomputed collisions stop working. This is why:

• Go seeds every map separately with a random value, and picks a new one when the map is emptied (§09). Its runtime hash uses the CPU's AES instructions where available, with a fallback based on wyhash otherwise.
• Python, Ruby and Rust default to SipHash variants, keyed hash functions designed specifically to resist this attack (check your version: some have changed algorithms over time).
• V8 seeds its string hashes too, though how strongly has varied between versions.

Seeding doesn't fix everything. Limit request sizes and the number of keys you'll parse (most HTTP and JSON frameworks have such limits), because even perfectly spread keys cost memory.

Concurrent hash maps

One map behind one mutex (§06) is correct, but on a busy 32-core server every goroutine queues on that single lock. The standard fixes, from simplest:

1. sync.RWMutex if reads dominate: many readers can hold it together.
2. A sharded map: 16 or 64 small maps, each with its own lock, picking the shard from the key's hash. Two goroutines only contend if their keys land in the same shard. This is lock stripingSharding (lock striping)Splitting one big structure into N independent pieces, each with its own lock. A key's piece is chosen by turning the key into a number (hashing it) and taking it modulo N., covered with code in Locks §10. Java's ConcurrentHashMap has used variations of this idea.
3. sync.Mapsync.MapA map type in Go's sync package that many goroutines can use at once without your own lock. It's tuned for two cases: keys written once and read many times, or goroutines working on separate keys. for write-once/read-many or disjoint-keys workloads, where it avoids locking on reads. Benchmark before choosing it for anything else.

Hash maps also anchor bigger designs: an LRU cache is a hash map plus a linked list, and a database hash index is a hash map on disk.

Cousins that are easy to confuse

Consistent hashing is not a hash map. Both hash keys, but a hash map maps keys to slots in one process' memory, and rehashes everything when it grows. Consistent hashingConsistent hashingA way to map keys (user IDs, cache keys) to servers so that adding or removing one server moves only about 1/N of the keys, instead of reshuffling almost all of them as hash(key) % N does. maps keys to servers, and is designed so that adding a server moves only a small fraction of keys, because moving data between machines is expensive. See Load Balancing §05 and Sharding.

Perfect hashing. If the key set is fixed and known in advance (a language's keywords, a list of HTTP header names), you can generate a perfect hash functionPerfect hashingA hash function built for one fixed set of keys so that no two of them collide. Useful when the keys never change, e.g. a language's keywords. with no collisions at all for those keys: every lookup is one probe. Compilers and code generators use this; it doesn't work for keys that change.

Bloom filters. A Bloom filterBloom filterA tiny bit array that answers “is this key in the set?” with either “definitely not” or “maybe”. It never misses a key that is there, but sometimes says “maybe” for one that isn't (a false positive). About 10 bits per key gives ~1% false positives. uses several hash functions over a bit array to answer "definitely not here" or "maybe here" in a fraction of a hash map's memory, at the cost of occasional false positives and no stored values. Databases use them to skip disk reads: see LSM Trees: Bloom filters.

Ordered maps. A hash map deliberately scrambles order. If you need "keys between A and F", "the smallest key" or sorted iteration, a balanced tree or B-tree gives O(log n) operations with order. See Trees.

Pitfalls gallery

type Cache struct{ items map[string][]byte }

c := Cache{}
c.items["k"] = data // panic

func NewCache() *Cache {
    return &Cache{items: make(map[string][]byte)}
}

cart.set({ sku: "A1", size: "M" }, 2);
cart.get({ sku: "A1", size: "M" }); // undefined

const key = (item) => `${item.sku}|${item.size}`;
cart.set(key({ sku: "A1", size: "M" }), 2);
cart.get(key({ sku: "A1", size: "M" })); // 2

Check yourself

Predict the answer before you click. Q1, Q4 and Q6 are covered in §06, Q2 and Q5 in §07, Q3 in §05.

var counts map[string]int
counts["go"]++
fmt.Println(counts["go"])

const m = new Map();
m.set({ x: 1, y: 2 }, "treasure");
console.log(m.get({ x: 1, y: 2 }));

m := map[int]int{}
go func() { for i := 0; ; i++ { m[i] = i } }()
go func() { for i := 0; ; i++ { m[i] = i } }()
time.Sleep(time.Second)

m := map[float64]int{}
m[math.NaN()] = 1
m[math.NaN()] = 2
_, ok := m[math.NaN()]
fmt.Println(len(m), ok)

Cheat sheet

Go

JavaScript