How Go’s Built-in Map Works with Swiss Tables

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.What is a map at runtime?#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.Copying a map variable makes m and m2 point to the same runtime Map.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 same entries are arranged differently when maps use different seeds.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.Group#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.A group pairs each control byte with the key-value slot below it.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.Control bytes and the control word#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:A 64-bit hash contains H1 and a 7-bit H2.Go uses a 32-bit hash layout on 32-bit targets (and Wasm). We will follow the 64-bit layout in the rest of this article.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:A control byte represents a live, empty, or deleted slot.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.