Go's Maps Are Swiss Tables: Groups of 8 Slots, Match Bytes and a Tombstone

TL;DR: Go’s map is a Swiss table. Slots live in groups of eight, and each group carries one 64-bit control word whose bytes are either “empty”, “deleted”, or the low seven bits of the key’s hash. A lookup compares all eight control bytes in one operation, so eight probe steps happen at once, and the table refuses to fill past 7/8 so there is always an empty slot to stop the probe sequence.

Every language needs a hash map, and every hash map is a compromise between three things: how fast a lookup is, how fast an insert is, and how much memory the table burns while sitting there doing nothing.

Go’s built-in map used to be a plain open-addressed table with buckets of eight slots and a tophash byte per slot. Then, in Go 1.24, it was rewritten around Abseil’s “Swiss Table” design, and the rewrite moved a lot of code out of the runtime and into a standalone package. This is a walk through that implementation, based on reading the Go 1.28 development tree (src/internal/runtime/maps).

The vocabulary

The package documents its own terms up front, and the terminology is worth internalising because every other file uses it:

go
// src/internal/runtime/maps/map.go:23
// - Slot: A storage location of a single key/element pair.
// - Group: A group of abi.MapGroupSlots (8) slots, plus a control word.
// - Control word: An 8-byte word which denotes whether each slot is empty,
//   deleted, or used. If a slot is used, its control byte also contains the
//   lower 7 bits of the hash (H2).
// - H1: Upper 57 bits of a hash.
// - H2: Lower 7 bits of a hash.
// - Table: A complete "Swiss Table" hash table. A table consists of one or
//   more groups for storage plus metadata to handle operation and determining
//   when to grow.
// - Map: The top-level Map type consists of zero or more tables for storage.
//   The upper bits of the hash select which table a key belongs to.
// - Directory: Array of the tables used by the map.
//
// At its core, the table design is similar to a traditional open-addressed
// hash table. Storage consists of an array of groups, which effectively means
// an array of key/elem slots with some control words interspersed. Lookup uses
// the hash to determine an initial group to check. If, due to collisions, this
// group contains no match, the probe sequence selects the next group to check
// (see below for more detail about the probe sequence).
//
// The key difference occurs within a group. In a standard open-addressed
// linear probed hash table, we would check each slot one at a time to find a
// match. A swiss table utilizes the extra control word to check all 8 slots in
// parallel.
//
// Each byte in the control word corresponds to one of the slots in the group.
// In each byte, 1 bit is used to indicate whether the slot is in use, or if it
// is empty/deleted. The other 7 bits contain the lower 7 bits of the hash for
// the key in that slot. See [ctrl] for the exact encoding.
//
// During lookup, we can use some clever bitwise manipulation to compare all 8
// 7-bit hashes against the input hash in parallel (see [ctrlGroup.matchH2]).
// That is, we effectively perform 8 steps of probing in a single operation.
// With SIMD instructions, this could be extended to 16 slots with a 16-byte
// control word.
//
// Since we only use 7 bits of the 64 bit hash, there is a 1 in 128 (~0.7%)
// probability of false positive on each slot, but that's fine: we always need
// double check each match with a standard key comparison regardless.

That last paragraph is the whole trick in one sentence. The control byte is a filter, not a proof. A group of eight slots holds eight hashes; if you could compare all eight against your hash in one CPU operation, then in the common case a lookup becomes “one comparison, and then at most a couple of real key comparisons to confirm”.

The control byte

The encoding is three states, and the constants say so:

go
// src/internal/runtime/maps/group.go:14
const (
	// Maximum load factor prior to growing.
	//
	// 7/8 is the same load factor used by Abseil, but Abseil defaults to
	// 16 slots per group, so they get two empty slots vs our one empty
	// slot. We may want to reevaluate if this is best for us.
	maxAvgGroupLoad = 7

	ctrlEmpty   ctrl = 0b10000000
	ctrlDeleted ctrl = 0b11111110

	bitsetLSB   = 0x0101010101010101
	bitsetMSB   = 0x8080808080808080
	bitsetL7B   = 0x7f7f7f7f7f7f7f7f
	bitsetEmpty = bitsetLSB * uint64(ctrlEmpty)
)

And the byte layout is documented right above the ctrl type:

go
// src/internal/runtime/maps/group.go:115
// Each slot in the hash table has a control byte which can have one of three
// states: empty, deleted, and full. They have the following bit patterns:
//
//	  empty: 1 0 0 0 0 0 0 0
//	deleted: 1 1 1 1 1 1 1 0
//	   full: 0 h h h h h h h  // h represents the H2 hash bits
//
// TODO(prattmic): Consider inverting the top bit so that the zero value is empty.
type ctrl uint8

So a group looks like this:

text
  control word (one uint64, eight bytes, one per slot)

   byte:  0x05   0x7f   0x80   0x12   0x80   0x33   0x80   0x00
          full   full  empty   full  empty   full  empty   full
          H2=5   H2=127 empty  H2=18 empty  H2=51 empty  H2=0
            |      |            |            |            |
            v      v            v            v            v
  slots:  [k0]   [k1]   [ -- ]   [k3]   [ -- ]   [k5]   [ -- ]   [k7]
          [e0]   [e1]          [e3]          [e5]          [e7]

“Full” is the only state with bit 7 clear. “Empty” is 0b10000000 exactly. “Deleted” is 0b11111110 — nearly all ones, deliberately, so that it can never be confused with a real H2 value.

Finding “all slots whose H2 equals mine” is one expression on a 64-bit word:

go
// src/internal/runtime/maps/group.go:151
// matchH2 returns the set of slots which are full and for which the 7-bit hash
// matches the given value. May return false positives.
func (g ctrlGroup) matchH2(h uintptr) bitset {
	return ctrlGroupMatchH2(g, h)
}

// Portable implementation of matchH2.
//
// Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
// note on bitset about the packed intrinsified return value.
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset {
	v := uint64(g) ^ (bitsetLSB * uint64(h))
	if goarch.IsArm64 == 1 {
		v = ^v
		return bitset((v&bitsetL7B + bitsetLSB) & (v & bitsetMSB))
	}
	// NB: This generic matching routine produces false positive matches when
	// h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For
	// example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we
	// subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be
	// considered matches of h. The false positive matches are not a problem,
	// just a rare inefficiency. Note that they only occur if there is a real
	// match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key
	// comparisons ensure that there is no correctness issue.
	return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)
}

The magic is ((v - bitsetLSB) &^ v) & bitsetMSB. XOR the control word with the broadcast hash byte to make matching bytes zero, then subtract a broadcast 0x01 — a borrow propagates up through a run of zero bytes and the MSB mask picks out the byte where the borrow landed. On AMD64 and ARM64 this whole thing is a single SIMD instruction sequence; on other platforms it is the portable arithmetic above.

The Map struct

The top-level object is small, and the compiler mirrors it exactly, so the runtime and the compiler can never disagree about the layout:

go
// src/internal/runtime/maps/map.go:213
// Note: changes here must be reflected in cmd/compile/internal/reflectdata/map.go:MapType.
type Map struct {
	// The number of filled slots (i.e. the number of elements in all
	// tables). Excludes deleted slots.
	// Must be first (known by the compiler, for len() builtin).
	used uint64

	// seed is the hash seed, computed as a unique random number per map.
	seed uintptr

	// The directory of tables.
	//
	// Normally dirPtr points to an array of table pointers
	//
	// dirPtr *[dirLen]*table
	//
	// The length (dirLen) of this array is `1 << globalDepth`. Multiple
	// entries may point to the same table. See top-level comment for more
	// details.
	//
	// Small map optimization: if the map always contained
	// abi.MapGroupSlots or fewer entries, it fits entirely in a
	// single group. In that case dirPtr points directly to a single group.
	//
	// dirPtr *group
	//
	// In this case, dirLen is 0. used counts the number of used slots in
	// the group. Note that small maps never have deleted slots (as there
	// is no probe sequence to maintain).
	dirPtr unsafe.Pointer
	dirLen int

	// The number of bits to use in table directory lookups.
	globalDepth uint8

	// The number of bits to shift out of the hash for directory lookups.
	// On 64-bit systems, this is 64 - globalDepth.
	globalShift uint8

	// writing is a flag that is toggled (XOR 1) while the map is being
	// written. Normally it is set to 1 when writing, but if there are
	// multiple concurrent writers, then toggling increases the probability
	// that both sides will detect the race.
	writing uint8

	// tombstonePossible is false if we know that no table in this map
	// contains a tombstone.
	tombstonePossible bool

	// clearSeq is a sequence counter of calls to Clear. It is used to
	// detect map clears during iteration.
	clearSeq uint64
}

dirPtr is doing double duty: it points at a []*table directory for a real map, or straight at a single group for a small map. dirLen == 0 is the sentinel that says “small”.

Small maps: one group, no directory

A map with eight or fewer entries never needs a directory, a table, or a probe sequence. It is a single group, and the whole lookup is one control word match:

go
// src/internal/runtime/maps/map.go:465
func (m *Map) getWithKeySmall(typ *abi.MapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
	g := groupReference{
		data: m.dirPtr,
	}

	match := g.ctrls().matchH2(h2(hash))

	for match != 0 {
		i := match.first()

		slotKey := g.key(typ, i)
		if typ.IndirectKey() {
			slotKey = *((*unsafe.Pointer)(slotKey))
		}

		if typ.Key.Equal(key, slotKey) {
			slotElem := g.elem(typ, i)
			if typ.IndirectElem() {
				slotElem = *((*unsafe.Pointer)(slotElem))
			}
			return slotKey, slotElem, true
		}

		match = match.removeFirst()
	}

	// No match here means key is not in the map.
	// (A single group means no need to probe or check for empty).
	return nil, nil, false
}

Creating one is free, too — no allocation at all until the first assignment:

go
// src/internal/runtime/maps/map.go:350
func NewEmptyMap() *Map {
	m := new(Map)
	m.seed = uintptr(rand())
	// See comment in NewMap. No need to eager allocate a group.
	return m
}

Inserting into a small map is the same idea with a fallback for the full case:

go
// src/internal/runtime/maps/map.go:586
	// There can't be deleted slots, small maps can't have them
	// (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
	// more efficient than matchEmpty.
	match = g.ctrls().matchEmptyOrDeleted()
	if match == 0 {
		// No empty slot found. Need to grow the map.
		return nil
	}

	i := match.first()

	slotKey := g.key(typ, i)
	if typ.IndirectKey() {
		kmem := newobject(typ.Key)
		*(*unsafe.Pointer)(slotKey) = kmem
		slotKey = kmem
	}
	typedmemmove(typ.Key, slotKey, key)

	slotElem := g.elem(typ, i)
	if typ.IndirectElem() {
		emem := newobject(typ.Elem)
		*(*unsafe.Pointer)(slotElem) = emem
		slotElem = emem
	}

	g.ctrls().set(i, ctrl(h2(hash)))
	m.used++

	return slotElem
}

Wait — small maps never have deleted slots, yet the code says “use matchEmptyOrDeleted as it is a bit more efficient than matchEmpty”. Because the deleted marker 0b11111110 has bit 7 set, it is caught by the same mask as empty, and in a small map no slot is ever in that state, so the cheaper bit test is safe.

The 7/8 load factor

The table refuses to be full, because an empty slot is the terminator of every probe sequence:

go
// src/internal/runtime/maps/table.go:114
// maxGrowthLeft is the number of inserts we can do before
// resizing, starting from an empty table.
func (t *table) maxGrowthLeft() uint16 {
	if t.capacity == 0 {
		// No real reason to support zero capacity table, since an
		// empty Map simply won't have a table.
		panic("table must have positive capacity")
	} else if t.capacity <= abi.MapGroupSlots {
		// If the map fits in a single group then we're able to fill all of
		// the slots except 1 (an empty slot is needed to terminate find
		// operations).
		//
		// TODO(go.dev/issue/54766): With a special case in probing for
		// single-group tables, we could fill all slots.
		return t.capacity - 1
	} else {
		if t.capacity > math.MaxUint16/maxAvgGroupLoad {
			panic("overflow")
		}
		return (t.capacity * maxAvgGroupLoad) / abi.MapGroupSlots
	}

}

Seven usable slots per group of eight. That is the “7/8” in the name of the design, and it is why growthLeft counts down as you insert.

Looking up in a full map

Now the real path. Pick a table with the high bits of the hash, pick a group with the next bits, and walk a quadratic probe sequence:

go
// src/internal/runtime/maps/table.go:193
	seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
	h2Hash := h2(hash)
	for ; ; seq = seq.next() {
		g := t.groups.group(typ, seq.offset)

		match := g.ctrls().matchH2(h2Hash)

		for match != 0 {
			i := match.first()

			slotKey := g.key(typ, i)
			if typ.IndirectKey() {
				slotKey = *((*unsafe.Pointer)(slotKey))
			}
			if typ.Key.Equal(key, slotKey) {
				slotElem := g.elem(typ, i)
				if typ.IndirectElem() {
					slotElem = *((*unsafe.Pointer)(slotElem))
				}
				return slotKey, slotElem, true
			}
			match = match.removeFirst()
		}

		match = g.ctrls().matchEmpty()
		if match != 0 {
			// Finding an empty slot means we've reached the end of
			// the probe sequence.
			return nil, nil, false
		}
	}
}

Three steps: match the control word, confirm with a real key comparison, and if the group has an empty slot, stop — the key is not in the map.

The probe sequence itself is triangular-numbered, which is the classic quadratic probing trick:

go
// src/internal/runtime/maps/table.go:1337
type probeSeq struct {
	mask   uint64
	offset uint64
	index  uint64
}

func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
	return probeSeq{
		mask:   mask,
		offset: uint64(hash) & mask,
		index:  0,
	}
}

func (s probeSeq) next() probeSeq {
	s.index++
	s.offset = (s.offset + s.index) & s.mask
	return s
}

The comment above the type explains why this visits every group exactly once: the triangular numbers (i^2 + i)/2 are a bijection modulo any power of two, which is why the number of groups must be a power of two.

Putting, and why tombstones exist

Insertion is the same walk with one extra rule: if the group is full but the table has room, remember the first tombstone you passed and reuse it instead of consuming new capacity:

go
// src/internal/runtime/maps/table.go:304
		// No existing slot for this key in this group. Is this the end
		// of the probe sequence?
		match = g.ctrls().matchEmptyOrDeleted()
		if match == 0 {
			continue // nothing but filled slots. Keep probing.
		}
		i := match.first()
		if g.ctrls().get(i) == ctrlDeleted {
			// There are some deleted slots. Remember
			// the first one, and keep probing.
			if firstDeletedGroup.data == nil {
				firstDeletedGroup = g
				firstDeletedSlot = i
			}
			continue
		}
		// We've found an empty slot, which means we've reached the end of
		// the probe sequence.

		// If we found a deleted slot along the way, we can
		// replace it without consuming growthLeft.
		if firstDeletedGroup.data != nil {
			g = firstDeletedGroup
			i = firstDeletedSlot
			t.growthLeft++ // will be decremented below to become a no-op.
		}

		// If we have no space left, first try to remove some tombstones.
		if t.growthLeft == 0 {
			t.pruneTombstones(typ, m)
		}

		// If there is room left to grow, just insert the new entry.
		if t.growthLeft > 0 {
			slotKey := g.key(typ, i)
			if typ.IndirectKey() {
				kmem := newobject(typ.Key)
				*(*unsafe.Pointer)(slotKey) = kmem
				slotKey = kmem
			}
			typedmemmove(typ.Key, slotKey, key)

			slotElem := g.elem(typ, i)
			if typ.IndirectElem() {
				emem := newobject(typ.Elem)
				*(*unsafe.Pointer)(slotElem) = emem
				slotElem = emem
			}

			g.ctrls().set(i, ctrl(h2Hash))
			t.growthLeft--
			t.used++
			m.used++

			t.checkInvariants(typ, m)
			return slotElem, true
		}

		t.rehash(typ, m)
		return nil, false
	}
}

Now the reason tombstones exist. Suppose you delete a key from a group that has no empty slot. If you marked that slot empty, then a later lookup for some other key whose probe sequence passes through this group would stop there and conclude “not found” — even though the key it wants is further along the sequence. So you must not create an empty slot in the middle of a probe sequence. You write a tombstone instead:

go
// src/internal/runtime/maps/table.go:520
				// Only a full group can appear in the middle
				// of a probe sequence (a group with at least
				// one empty slot terminates probing). Once a
				// group becomes full, it stays full until
				// rehashing/resizing. So if the group isn't
				// full now, we can simply remove the element.
				// Otherwise, we create a tombstone to mark the
				// slot as deleted.
				var tombstone bool
				if g.ctrls().matchEmpty() != 0 {
					g.ctrls().set(i, ctrlEmpty)
					t.growthLeft++
				} else {
					g.ctrls().set(i, ctrlDeleted)
					tombstone = true
				}

A tombstone is a slot that is occupied (so probing walks past it) but never matches any hash (so nothing is ever found in it). Tombstones do count against the load factor, which is why the table eventually has to be cleaned up — pruneTombstones walks the probe sequence of every live key to find the tombstones that are genuinely unreachable and reclaim them.

Growing

Growth is not a simple “make it bigger” because the probe sequence depends on the number of groups: reordering slots to match a new probe sequence would break iteration. So the whole table is replaced.

go
// src/internal/runtime/maps/table.go:1205
// Replaces the table with one larger table or two split tables to fit more
// entries. Since the table is replaced, t is now stale and should not be
// modified.
func (t *table) rehash(typ *abi.MapType, m *Map) {
	// TODO(prattmic): SwissTables typically perform a "rehash in place"
	// operation which recovers capacity consumed by tombstones without growing
	// the table by reordering slots as necessary to maintain the probe
	// invariant while eliminating all tombstones.
	//
	// However, it is unclear how to make rehash in place work with
	// iteration. Since iteration simply walks through all slots in order
	// (with random start offset), reordering the slots would break
	// iteration.
	//
	// As an alternative, we could do a "resize" to new groups allocation
	// of the same size. This would eliminate the tombstones, but using a
	// new allocation, so the existing grow support in iteration would
	// continue to work.

	newCapacity := 2 * t.capacity
	if newCapacity <= maxTableCapacity {
		t.grow(typ, m, newCapacity)
		return
	}

	t.split(typ, m)
}

Doubling stops at maxTableCapacity (1024 slots). Past that, the table is split in two and the map grows a directory level instead. That is extendible hashing: the high bits of the hash select a directory entry, and the directory points at a table.

text
  directory (globalDepth = 2)

   +----+
   | 00 | --\
   +----+    +--> table (localDepth = 1)
   | 01 | --/
   +----+
   | 10 | ------> table (localDepth = 2)
   +----+
   | 11 | ------> table (localDepth = 2)
   +----+

Multiple directory entries may point at the same table, which is why a directory of size four can hold three tables. This is what makes growth incremental: instead of rehash-ing the entire map, one table grows at a time, and the work per insert is bounded.

The doubling itself copies every live entry into a fresh table:

go
// src/internal/runtime/maps/table.go:1286
// grow the capacity of the table by allocating a new table with a bigger array
// and uncheckedPutting each element of the table into the new table (we know
// that no insertion here will Put an already-present value), and discard the
// old table.
func (t *table) grow(typ *abi.MapType, m *Map, newCapacity uint16) {
	newTable := newTable(typ, uint64(newCapacity), t.index, t.localDepth)

	if t.capacity > 0 {
		for i := uint64(0); i <= t.groups.lengthMask; i++ {
			g := t.groups.group(typ, i)
			for j := uintptr(0); j < abi.MapGroupSlots; j++ {
				if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
					// Empty or deleted
					continue
				}

				key := g.key(typ, j)
				if typ.IndirectKey() {
					key = *((*unsafe.Pointer)(key))
				}

				elem := g.elem(typ, j)
				if typ.IndirectElem() {
					elem = *((*unsafe.Pointer)(elem))
				}

				hash := typ.Hasher(key, m.seed)

				newTable.uncheckedPutSlot(typ, hash, key, elem)
			}
		}
	}

	newTable.checkInvariants(typ, m)
	m.replaceTable(newTable)
	t.index = -1
}

Note that every key is rehashed during a grow. That is not an oversight: the hash is seeded per map, and the seed can change (see below), so the old hash values are not reusable.

Clearing

Clear is not free — it walks the tables and zeroes the groups that have anything in them:

go
// src/internal/runtime/maps/map.go:755
// Clear deletes all entries from the map resulting in an empty map.
func (m *Map) Clear(typ *abi.MapType) {
	if m == nil || m.Used() == 0 && !m.tombstonePossible {
		return
	}

	if m.writing != 0 {
		fatal("concurrent map writes")
	}
	m.writing ^= 1 // toggle, see comment on writing

	if m.dirLen == 0 {
		m.clearSmall(typ)
	} else {
		var lastTab *table
		for i := range m.dirLen {
			t := m.directoryAt(uintptr(i))
			if t == lastTab {
				continue
			}
			t.Clear(typ)
			lastTab = t
		}
		m.used = 0
		m.tombstonePossible = false
		// TODO: shrink directory?
	}
	m.clearSeq++

	// Reset the hash seed to make it more difficult for attackers to
	// repeatedly trigger hash collisions. See https://go.dev/issue/25237.
	m.seed = uintptr(rand())

	if m.writing == 0 {
		fatal("concurrent map writes")
	}
	m.writing ^= 1
}

Two things worth noting. The directory is not shrunk, only cleared — a Clear on a map with a big directory leaves the directory allocated. And the seed is replaced, so the same keys will hash differently after a clear.

Iteration starts at a random slot

Go randomises map iteration order on purpose, so that code cannot accidentally depend on it. The iterator picks a random offset within the table and a random offset within the directory:

go
// src/internal/runtime/maps/table.go:704
type Iter struct {
	key  unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
	elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
	typ  *abi.MapType
	m    *Map

	// Randomize iteration order by starting iteration at a random slot
	// offset. The offset into the directory uses a separate offset, as it
	// must adjust when the directory grows.
	entryOffset uint64
	dirOffset   uint64

	// Snapshot of Map.clearSeq at iteration initialization time. Used to
	// detect clear during iteration.
	clearSeq uint64

	// Value of Map.globalDepth during the last call to Next. Used to
	// detect directory grow during iteration.
	globalDepth uint8

	// dirIdx is the current directory index, prior to adjustment by
	// dirOffset.
	dirIdx int

	// tab is the table at dirIdx during the previous call to Next.
	tab *table

	// group is the group at entryIdx during the previous call to Next.
	group groupReference

	// entryIdx is the current entry index, prior to adjustment by entryOffset.
	// The lower 3 bits of the index are the slot index, and the upper bits
	// are the group index.
	entryIdx uint64
}

go
// src/internal/runtime/maps/table.go:740
// Init initializes Iter for iteration.
func (it *Iter) Init(typ *abi.MapType, m *Map) {
	it.typ = typ

	if m == nil || m.used == 0 {
		return
	}

	dirIdx := 0
	var groupSmall groupReference
	if m.dirLen <= 0 {
		// Use dirIdx == -1 as sentinel for small maps.
		dirIdx = -1
		groupSmall.data = m.dirPtr
	}

	it.m = m
	it.entryOffset = rand()
	it.dirOffset = rand()
	it.globalDepth = m.globalDepth
	it.dirIdx = dirIdx
	it.group = groupSmall
	it.clearSeq = m.clearSeq
}

Two random numbers: one picks where in the slot space to start, one picks where in the directory to start. The iterator also holds on to the old table when the map grows underneath it, so it can re-look-up each key in the new table to return the latest value — that is the “entries modified during iteration must return their latest value” rule from the spec, and it is why iteration has to re-hash keys.

Trade-offs

What the Swiss table buys over a plain open-addressed map:

One control-word comparison covers eight slots. A lookup does one 64-bit (or SIMD) comparison instead of eight byte comparisons.
Fewer false key comparisons. The H2 filter means the expensive Equal call happens rarely — the code comments estimate fewer than 1/8 false positives per find.
Cheap small maps. Up to eight entries live in one group with no directory, no table, and (for an empty map) no allocation at all.
Incremental growth. A map that outgrows one table splits it and grows the directory instead of rehashing everything, so an insert never pays for a whole-map resize.

What it costs:

Tombstones. Deleting from a full group leaves a slot that is neither empty nor reusable, and it counts against the load factor.
Rehashing on grow. Every key is hashed again when a table is rebuilt.
A more complex invariant. “Empty terminates the probe sequence” means delete, insert, and prune all have to agree with each other.
A bigger control word per group. One extra byte per slot (8 bytes per 8 slots) on top of the key and element data.

Caveats

The load factor is a hard 7/8. A table can never be completely full. That is not a tuning knob you can change; it is a correctness requirement of the probe algorithm.

A nil map read is fine, a nil map write panics. The runtime’s mapassign path checks for a nil map explicitly and panics with “assignment to entry in nil map”. A make(map[K]V) is not the same thing as a nil map.

Maps are not safe for concurrent use. The writing flag is a cheap sanity check that detects the most obvious races, not a lock. Two goroutines writing to the same map is a data race and the runtime will eventually crash with “concurrent map writes”.

Iteration order is random and can change between runs. Worse, the Go spec explicitly allows entries added during iteration to be returned, and entries deleted during iteration to be skipped. If you need a stable order, sort the keys.

Clear keeps the directory. The tables are emptied but the directory is not shrunk, so a map that was once huge stays shaped like it.

The seed is regenerated when the map empties out. After a delete that takes the map to zero entries, the seed is replaced. That means the hash of a given key changes over the life of the map, which is exactly why growing a table has to rehash every key.

Wrapping up

The one thing to remember: a Go map is a table of groups of eight slots, each group carrying a control word where every byte is either empty, deleted, or seven bits of the key’s hash. Lookups compare that word against the hash of the key in one shot, and only the survivors get a real key comparison.

The part people get wrong: the “deleted” state. Deleting a key from a full group cannot write an empty marker, because an empty marker would cut the probe sequence short and make later lookups fail. It writes a tombstone instead, and tombstones are why the table has to be pruned or grown eventually.

What to go do about it: if you are building a map-heavy workload, stop thinking about “the map” as one object and start thinking about the table that holds your keys. Pre-sizing with make(map[K]V, n) avoids repeated doubling; keeping keys small keeps them stored inline instead of indirectly; and if you are iterating, remember you are getting a snapshot of a moving target.