How Swiss Tables Work in Go’s Built-in Map

We have already written about Go maps and their old runtime implementation in Go Maps Explained: How Key-Value Pairs Are Actually Stored. Go 1.24 replaced that implementation with a design based on Swiss Tables, so it is time for an update.

You do not need to go back and read the old article. We will review how maps behave and the concepts needed here before moving into the new runtime internals.

The Go blog also has an excellent article, Faster Go maps with Swiss Tables. It goes deeper and assumes a little more background knowledge. We take a different approach. We will discuss the same implementation more gradually and in a visual way, so you can relax your brain a little and still understand what Go is doing.

If you are already familiar with maps in Go, feel free to skip the first section.

A map stores key-value pairs, and each key is associated with one value. The key type and value type can be different:

m := map[string]int{
	"dog": 1,
	"cat": 2,
}

Besides using a map literal, we usually create an empty map with make:

m := make(map[string]int, 100)

The optional 100 tells Go that we expect the map to hold around 100 entries. Go uses 100 as a hint when it creates the map’s initial storage, which we will explain in the next section. The map can then hold the requested number of entries before it needs to grow, which is an expensive operation.

Just a spoiler: with a hint of 100, Go creates initial storage with 128 slots. It can hold 112 entries before the next new entry makes it grow.

The spoiler I just revealed is an internal detail because Go does not expose a map’s capacity. len(m) reports the number of stored entries, while the built-in cap does not accept maps. The value passed to make is only a sizing hint to the runtime.

println(len(m)) // 0
println(cap(m)) // compile error: invalid argument: m for built-in cap

Assignment, lookup, and deletion use the same operations in every Go version:

m["dog"] = 1

value := m["dog"]
value, ok := m["dog"]

delete(m, "dog")

The first lookup value := m["dog"] returns the value directly. If "dog" is missing, it returns 0, the zero value of int.

The two-value form value, ok := m["dog"] also returns ok to tell us whether the map contains "dog". This removes the ambiguity between a missing key and a stored key with the value 0.

Both cases return 0 in value, but ok is false for the missing key and true for the stored key.

m := map[string]int{"dog": 0}

println(m["dog"]) // 0: the key exists
println(m["cat"]) // 0: the key does not exist

The zero value of a map is nil, but its behavior is slightly nuanced because not every operation on a nil map causes a panic:

var m map[string]int

value, ok := m["dog"] // safe
println(len(m))       // safe
delete(m, "dog")      // safe
for range m {}        // safe
m["dog"] = 1          // panic: assignment to entry in nil map

Reading, deleting, calling len, and ranging over a nil map are safe. Writing an entry to a nil map panics with assignment to entry in nil map.

Before looking inside a map, let’s look at 2 more rules:

• A range loop does not guarantee any iteration order.
• A built-in map supports concurrent reads as long as no goroutine writes to it. Concurrent reads and writes, or multiple concurrent writes, need synchronization such as a mutex.

A map’s key type must also be comparable because, internally, the map hashes each key to locate candidate slots and then compares candidate keys for equality (==) to confirm that it has found the requested key:

• Strings, integers, pointers, and channels are valid key types.
• Structs are valid if all their fields are comparable.
• Arrays are valid if their element type is comparable.
• Slices, maps, and functions are not.

m := make(map[[2]string]int) // valid: arrays of strings are comparable
m[[2]string{"dog", "cat"}] = 1

_ = make(map[[]string]int) // compile error: invalid map key type []string

Go rejects the invalid map key type during compilation, so this program cannot be built or run.

An interface type such as any is a valid map key type, but every concrete value assigned as a key must also be comparable:

m := make(map[any]string)

m["dog"] = "string key"                    // valid
m[42] = "integer key"                      // valid
m[[2]string{"dog", "cat"}] = "array key"   // valid

m[[]string{"dog", "cat"}] = "slice key"    // panic: runtime error: hash of unhashable type []string

The snippet above passes compilation and stores the first 3 entries. It then panics on the final assignment when the runtime tries to hash the []string value stored inside the interface key.

That’s enough warming up. It’s time to get into the map internals.

Let’s start with what a map actually is.

m := make(map[string]int)

make initializes the map. map[string]int is the language-level type, which tells us that the map uses strings as keys and integers as values. Underneath that type, the runtime representation of m is a pointer to internal/runtime/maps.Map.

type Map struct {
	used uint64
	seed uintptr

	dirPtr unsafe.Pointer
	dirLen int
	...
}

We can easily inspect this with println, which prints that pointer:

m := make(map[string]int)
m2 := m

println(m)  // 0x14000122000
println(m2) // 0x14000122000

Copying m to another map variable copies this pointer, so both variables refer to the same runtime Map and the same entries.

The 2 fields at the top describe the map itself, not the storage for its entries.

type Map struct {
	used uint64
	seed uintptr
	...
}

used counts how many entries are currently stored. Since Go knows exactly where to find the number of entries, when you write len(m), Go replaces this call with an access to the first field of Map and converts it to an int. That is why len(m) is O(1) instead of scanning the entire map.

seed is an interesting field because it causes different maps to distribute the same keys differently. Go initializes this field with a random number for every map.

The array above is only a simplified representation used for this explanation. The actual data structure is more complicated.

Whenever Go needs to locate a key in the map’s storage, it hashes that key using the map’s seed. Since each map receives its own seed, hashing the same key in 2 maps can produce different hash values and therefore different storage locations.

A map lays out its storage differently depending on the number of key-value pairs it holds.

In its smallest form, a map stores up to 8 key-value pairs in a structure called a group. This is the smallest unit of storage that Go’s Swiss Table implementation examines at one time. Each group contains:

• 8 slots for key-value entries.
• 8 control bytes, one for each slot. Go stores these 8 bytes together in one uint64.

The group’s concrete type depends on the map’s key and value types, so the compiler generates an internal anonymous struct for each map type. Conceptually, map[string]int has this layout:

type group struct {
	ctrl uint64

	slots [8]struct {
		key  Key
		elem Elem
	}
}

Go is also testing a new group layout with separate key and value arrays to improve key lookup locality and remove repeated alignment padding, as explained in the split group layout section.

Let’s first look at the top row of the group. These are the 8 control bytes. Together, they form the 8-byte control word.

Each control byte describes the slot directly below it, so control byte 0 belongs to slot 0, control byte 1 belongs to slot 1, and the same relationship continues through slot 7.

But where do those bytes come from?

Go hashes the key using the seed from Map, then divides that hash into 2 parts. On most 64-bit targets, the upper 57 bits are called H1, and the lower 7 bits are called H2. Suppose we have another key, "cow", which produces H2 42 in our illustration:

H1 is the first part of the hash that Go uses to choose where a search starts in the map’s storage. A small map has only 1 group, so there is nothing to choose. Let’s leave it aside until the map grows.

H2 is the part stored in the control byte above a live slot.

But a control byte has 8 bits, while H2 uses only 7, so we still have 1 bit left. Go uses this highest bit to tell whether the slot contains a live entry or a special state. If this bit is 0, the lower 7 bits contain H2. If this bit is 1, the complete control byte represents empty or deleted:

When its slot contains a key-value entry, the highest bit is 0, while the lower 7 bits contain H2. H2 42 is 0101010 in binary, so the complete control byte for "cow" is 00101010.

When the highest bit is 1, the control byte stores a special value instead of H2. An empty slot uses 10000000. A deleted slot uses 11111110 and is also called a tombstone. Both states contain no live key-value entry, but a lookup can stop at empty while it must continue past deleted. We will return to this distinction in the deletion section.

With this layout, a control byte lets Go answer 2 questions before it reads the complete key from a slot:

• Does this slot contain a live entry, or is it empty or deleted?
• If the slot contains a live entry, could its key be the one we are looking for?

Now return to the original group above:

Next, assign a value to the "cow" key that produced H2 42:

m["cow"] = 4

Before storing "cow", Go must know whether this assignment updates an existing key or adds a new one. It uses H2 to find slots that may already store the key, then confirms each candidate with a complete key equality check.

• H2 for "cow" is 42, which is also the value stored in the control byte of "dog".
• Go then compares the complete keys with an equality check (==), but "dog" is not equal to "cow".
• No other control byte contains H2 42, so Go knows that this assignment is adding a new key.

The map selects the first empty slot in the group, which is slot 2, writes "cow" and 4 into that slot, then writes H2 42 into control byte 2 directly above it:

The insertion increases used from 3 to 4, which also changes the value returned by len(m) to 4. Since this small map still needs only one group, dirPtr points directly to that group and dirLen is 0:

In this small-map form, dirPtr points directly to the group that stores the map’s key-value entries.

Now the group contains 2 control bytes with the same H2 value, 42: one above "dog" and one above "cow". Suppose we later assign another value to "cow":

m["cow"] = 5

Before Go can update the value, it must find the existing key. It takes H2 42 from the hash and compares it with all 8 control bytes in the group at once:

Go does not visit the 8 slots one by one and compare H2 with each control byte separately. On AMD64, Go uses SIMD instructions to compare H2 42 with those 8 control bytes at the same time.

SIMD lets the CPU apply the same comparison to several byte values in parallel. On AMD64, the result is a packed bitmap with one bit for each slot:

In our group, the bits for slots 0 and 2 are set because both control bytes contain 42. The other bits are clear, which masks out the other 6 slots without reading their complete keys.

Other architectures produce the same candidate mask with arithmetic and bitwise operations on the 64-bit control word, but they use one byte per slot instead of packing the result into 8 bits.

Go then reads the complete keys from slots 0 and 2 and compares them with "cow". "dog" fails the equality check (==), while "cow" matches, so the assignment updates the value stored for "cow".

A group has only 8 slots, so if we keep adding key-value pairs beyond its capacity, Go needs another storage structure to store them.

Go doubles the number of groups from 1 to 2 and introduces a new structure called a table to manage them. It moves the 8 existing entries from the small group into that table, redistributes them between the 2 groups, and then stores the new entry.

A table is a complete Swiss Table that owns one or more groups together:

type table struct {
	used       uint16
	capacity   uint16
	growthLeft uint16
	...

	groups groupsReference
}

Our first table has capacity = 16, used = 9, and 2 groups:

• groups points to the contiguous allocation that contains the groups.
• capacity counts all slots across those groups.
• used counts the live entries in this table.

Now, why do the existing key-value pairs in the first group need to be redistributed, and how does Go know which of the 2 groups each pair should go to?

Let me introduce H1, which is used for this exact purpose. Go uses H1 to calculate the starting group for each key:

starting group = H1 % number of groups

Since this table has 2 groups, % 2 only needs the lowest bit of H1. When we write H1 with its highest bit on the left, the lowest bit is the rightmost bit, directly beside H2 in the original hash.

For example, suppose H1 for "cow" ends in 0, while H1 for "dog" ends in 1:

Because the number of groups changed, Go runs this calculation again for each existing key. Some key-value pairs are inserted into the new group 0, while others are inserted into the new group 1.

This result is only the starting group. For example, a 16-slot table with 10 live entries can distribute them unevenly, leaving one group full while the other still has empty slots:

In this case, another key may also select the full group 0 above as its starting group. Go cannot store the key there, so it checks group 1 next. The list of groups Go checks, together with the order used to check them, is called the triangular probe sequence.

The storage pointer in Map also changes when the small map becomes a table-backed map. dirPtr no longer points directly to a group. It points to a one-entry array, and that entry points to the table.

The runtime calls this pointer array the directory:

The table above starts with 2 groups. Since each group contains 8 slots, this table currently has 16 slots.

If we keep adding keys, Go can replace it with a larger table containing 4 groups, then 8 groups, then 16 groups, and continue doubling the number of groups when more storage is needed. One table can grow up to 128 groups, giving it a maximum capacity of 1024 slots:

128 groups * 8 slots = 1024 slots

If another insertion requires more storage, Go splits the table into 2 tables instead. We will follow that split shortly.

But after the small map with 1 group becomes a table with 2 groups, Go uses a different growth threshold:

• The map does not wait for all groups in the table to become full before doubling the group count from 2 to 4, from 4 to 8, and so on.
• Once a table has grown to 1024 slots, it also does not wait for every slot to contain an entry before splitting it into 2 tables.

A regular table reaches its insertion limit before every slot is used, and that limit is controlled by the load factor. It tells Go how full the table is. Go includes both live entries and deleted slots in this calculation:

load = (live entries + deleted slots) / table slots

Our table has no deleted slots, so with 16 slots and 10 live entries, its load factor is 10 / 16, or 62.5%.

Go does not let a regular table reach 100%. Its maximum load factor is 7 / 8, or 87.5%, which means that live entries and deleted slots together may account for 7 out of every 8 slots on average. The limit applies across the whole table.

The table field growthLeft tracks how many additional empty slots new keys may consume before the table reaches that limit.

type table struct {
	used       uint16
	capacity   uint16
	growthLeft uint16
	...

	groups groupsReference
}

A 16-slot table containing only live entries and empty slots has an insertion limit of 14 entries because 16 * 7 / 8 = 14. After the 10 entries above are stored, growthLeft is 4.

growthLeft reaches 0 after the table stores 14 live entries. If another new key needs an empty slot, Go doubles the table’s number of groups if the table has fewer than 1024 slots.

Each time the table doubles its number of groups, Go hashes every live key in that table again and redistributes all its entries across the new groups.

A table with 1024 slots already contains the maximum of 128 groups. In this case, Go splits the selected table into 2 new tables instead, each with 128 groups and 1024 slots.

This split uses a different end of H1 than the calculation that chooses a group. When the number of groups doubles, Go uses one more bit from the right side of H1, where the low bits are, to calculate the starting group inside the same table.

So when a table splits, Go uses the next unused bit from the left side of H1, where the high bits are, to choose between the 2 new tables.

Suppose H1 for "dog" begins with 0, while H1 for "cat" begins with 1. The 0 sends "dog" to table 0, and the 1 sends "cat" to table 1:

So the map hashes the key again with its seed, reads the same leftmost H1 bit, and inserts the key-value pair into the selected new table. After all live entries have moved, Go retries the insertion that triggered the split, just as it does when doubling the number of groups.

Before getting into the directory, let’s understand what problem it solves.

If Go redistributed every key-value pair in the map whenever one table needed more storage, each growth operation would become more and more expensive as the map became larger. Instead, Go only rebuilds the table that needs more storage.

When the number of groups in a table doubles, Go redistributes only the live key-value pairs from that table across the new groups.

The leftmost H1 bits select a table, while the rightmost H1 bits select a starting group inside that table.

When the number of groups changes, Go only changes how many rightmost H1 bits that table uses for its group selection.

It does not change the leftmost H1 prefix that selected the table. A key stored in another table has a different leftmost H1 prefix, so it continues to select that table and does not take part in this redistribution.

When a table splits into 2 tables, Go redistributes only the live key-value pairs from the original table between the 2 new tables.

When the map has 2 tables, the directory uses the leftmost H1 bit to select between them: 0 points to table 0 and 1 points to table 1. If table 1 splits, the directory increases the number of leftmost H1 bits it reads from 1 to 2:

H1 prefixes 00 and 01 select directory entries 0 and 1, which both point to table 0 because table 0 has not split. Prefix 10 selects entry 2, which points to new table 1, while prefix 11 selects entry 3, which points to new table 2.

You can see that the map now contains 3 tables, but 2 leftmost H1 bits produce 4 possible combinations, right?

This is where the directory becomes useful. It has 4 entries, one for each bit combination, but those entries do not need to point to 4 different tables.

During a lookup, Go uses the 2 leftmost H1 bits to select a directory entry, and that entry tells Go which table to search. This allows one table to split without requiring every other table in the map to split with it.

In other words, the leftmost H1 bits select a directory entry, not a table directly, and that directory entry tells Go which table may contain the key.

Let’s say table 0 has reached its insertion limit and needs to split. However, we cannot simply split it as we did with table 1, because 2 directory entries point to table 0.

Table 0 therefore needs a way to know:

• How many directory entries point to it?
• Does the directory already have enough entries for the 2 new child tables?

This is what global depth and local depth tell us.

type Map struct {
	dirPtr unsafe.Pointer
	dirLen int

	globalDepth uint8
	...
}

type table struct {
	localDepth uint8
	...
}

Global depth belongs to the whole directory. It is the number of high hash bits used to select one directory entry. In this case, we have 4 directory entries selected by the 2 leftmost bits of H1 (00, 01, 10, and 11), so globalDepth = 2.

Local depth belongs to each table. It is the number of high hash bits needed to identify that table. In this case:

• Every key with an H1 prefix of 0 chooses table 0. Table 0 is identified by the leftmost bit (0), so its localDepth = 1.
• Every key with an H1 prefix of 10 chooses table 1, while every key with an H1 prefix of 11 chooses table 2. Tables 1 and 2 need the 2 leftmost bits, so each has localDepth = 2.

Table 0 knows that its local depth (1) is less than the global depth (2), which means the directory already has enough entries for the split. Go can make entry 0 point to one child and entry 1 point to the other without growing the directory.

What if table 1 reaches its insertion limit and needs to split instead of table 0? In this case, its localDepth (2) is equal to the map’s globalDepth (2). The map first doubles the directory from 4 entries to 8 and increases globalDepth to 3. It then splits table 1 into tables 1 and 2:

So far, so good. Let’s recap what we have discussed so far using only a key’s hash.

The highest bits of H1 select a directory entry and therefore a table. The lower bits of H1 select a starting group inside that table. H2 filters the 8 slots in the group. Any H1 bits between the directory selection and the group selection may be unused for the current map shape:

After following the new implementation from a group to a directory, let’s compare it with the implementation that Go used before version 1.24.

The old implementation stored up to 8 key-value pairs in one bucket. If that bucket could not hold another entry, the runtime could connect an overflow bucket that provided 8 more slots.

If the overflow bucket also became full, another overflow bucket could follow it:

An overflow bucket allowed 1 full bucket to receive more space without redistributing the other buckets. But an overflow chain also introduced several costs:

• A lookup had to load the overflow pointer before it could find and check the next 8 slots.
• A longer chain repeated that pointer load and bucket scan for every additional overflow bucket.
• Extending the chain could require another allocation.

Go cannot read the overflow bucket until it has loaded the pointer from the current bucket. Every additional overflow bucket adds another dependent pointer load:

bucket
  -> load pointer
overflow 1
  -> load pointer
overflow 2

The new implementation allocates a table’s groups together in one array. It already knows exactly where each group is and uses the triangular probe sequence to find another group inside that table when the starting group has no empty slot:

Growth is the 2nd major change.

The old implementation had one primary bucket array for the map. When the bucket array doubled, Go created a new array with twice as many buckets. The key-value pairs from each old bucket were then distributed between 2 buckets in the new array.

Go repeated this process gradually for every old bucket as we assigned or deleted entries, so both arrays stayed alive until every key-value pair had moved.

In contrast, Go’s Swiss Table growth does not move one group at a time, as we discussed. The new implementation divides a large map into tables with at most 1024 slots.

One assignment may rebuild one complete table, but the advantage is that it does not rebuild the entry storage of the other tables.

In the Go team’s microbenchmarks, map operations ran up to 60% faster than in Go 1.23, although some edge cases became slower. Full application benchmarks showed a geometric mean CPU time improvement of around 1.5%.

Let’s return to the 3 control states we introduced earlier, this time focusing on deleted:

An empty slot and a deleted slot both contain no live key-value entry, but they have different meanings during lookup.

During a lookup:

1. Go first checks whether any candidate slot in the current group contains the requested key.
2. If Go does not find the key in those candidate slots and the group contains an empty control byte, Go can stop early.
3. A deleted control byte cannot provide the same guarantee because another key may have been inserted into a later group before this slot was deleted, so Go must continue checking other groups in the probe sequence.

The empty state does not mean no keys exist after the empty slot or in later groups. Other keys may still be stored there. It only means the requested key cannot sit in a later group along the same probe sequence.

But deleting a key does not always produce a deleted slot. In a small map with only 1 group, the removed slot always becomes empty because lookup has no later group to continue to.

In a larger table-backed map, the removed slot also becomes empty if its group already contains at least 1 other empty slot. If the group has no empty slot, Go marks the removed slot as deleted so lookup can continue to later groups.

Earlier, we said Go lets live entries and deleted slots account for up to 7 / 8 of a table before the next new key needs table maintenance. This ratio is the table’s load factor:

load factor = (live entries + deleted slots) / table slots

Our current table has 16 slots and no deleted slots. A load factor of 7 / 8 gives it space for 14 live entries:

14 / 16 = 7 / 8 = 87.5%

Why does Go stop here instead of filling all 16 slots?

The triangular probe sequence chooses the group indexes, and Go scans the selected groups one at a time. This work is a linear scan across the probed groups, so checking 4 groups requires 4 separate group checks.

Now extend the same load factor to a 32-slot table. It can store 28 live entries and still keep 4 empty slots. All 4 empty slots may sit in one group, while the other 3 groups are full:

Suppose a missing lookup starts at group 0. With 4 groups, the triangular probe sequence is 0 -> 1 -> 3 -> 2. Go checks group 0, then group 1. The empty control bytes in group 1 stop the lookup, so Go never checks groups 3 and 2 even though both contain entries.

As the table fills, empty slots become harder to find. A missing lookup may scan more groups before it reaches an empty control byte. If every slot were full, no empty control byte could stop the scan, so Go would need to check every group before reporting a missing key.

The 7 / 8 limit keeps some empty slots in the table before this scanning cost becomes too high.

Could Go choose another limit? Yes.

• A lower limit would use more memory but usually shorten the probe sequence.
• A higher limit would leave less unused memory but usually lengthen the probe sequence.

Go currently uses the same 7 / 8 limit as Abseil’s Swiss Table.

There is one more map change worth discussing. Go 1.27 includes an experimental group layout named mapsplitgroup, which we can enable with GOEXPERIMENT=mapsplitgroup.

Despite the name, this experiment does not change the map algorithm, the hash split, or the probe sequence. It only changes how one group arranges its 8 keys and values in memory.

By default, Go 1.27 stores each key beside its value:

control:  42     17     -      -
slots:    dog:1  cat:2  empty  empty

The internal layout is approximately:

slots [8]struct {
	key   string
	value int
}

The experimental layout separates the keys from the values:

control:  42     17     -      -
keys:     dog    cat    empty  empty
values:   1      2

Its internal layout is approximately:

keys   [8]string
values [8]int

The 2 arrays still describe the same entries. At index 1, keys[1] stores "cat", and values[1] stores 2.

Let’s look up "cat". Its control byte identifies index 1 as a candidate, so Go reads keys[1] and compares it with "cat". But do we need values[1] at this point? No:

Go reads values[1] only after the key matches. This is why the new layout keeps the keys together. During the search, Go reads candidate keys, while the values become useful only after one key matches. The values no longer sit between those key reads.

The split layout can also use less memory. Consider map[int64]struct{}, a map often used as a set. Each key needs 8 bytes, and the empty value stores no data. But the old layout still uses 16 bytes for every {key, value} slot because the empty value at the end adds 8 bytes of padding.

The control word is unchanged, so we only need to compare the storage below it:

The old slot layout uses 128 bytes across 8 slots. The 8 keys use 64 bytes, but each slot also contains 8 bytes of padding, adding another 64 bytes.

The split layout keeps all 8 keys together instead:

The 8 keys still use 64 bytes. The empty value array adds no element data, but Go adds one 8-byte trailing padding area after it. The storage below the control word therefore uses 72 bytes in total, saving 56 bytes in one group.

Go introduced this layout behind GOEXPERIMENT=mapsplitgroup in CL 711560, then enabled it by default on the development branch in CL 820500.

• The Go specification: Map types
• Go 1.24 release notes: Runtime
• Faster Go maps with Swiss Tables
• Go 1.27 runtime source: map.go, table.go, group.go, and runtime.go
• Go 1.27 map ABI and group layout
• Go 1.23.12 map implementation
• Abseil Swiss Tables Design Notes
• Split group layout: CL 711560 and CL 820500
• Go Maps Explained: How Key-Value Pairs Are Actually Stored

We’re VictoriaMetrics, a team providing open-source, highly scalable, and cost-efficient solutions for monitoring, logging, and tracing, trusted by users worldwide to reduce their observability costs. Check out our VictoriaMetrics, VictoriaLogs, and VictoriaTraces for more details.