vault

Map Iteration Order Randomization

14 min read

Map Iteration Order Randomization

Ranging over a Go map yields its keys in an order that is deliberately randomized — not merely “unspecified,” but actively scrambled by the runtime on every range so that no two iterations of the same map are likely to match. This is not a side effect of the hash table’s layout; it is a feature, implemented by seeding each iterator with a random starting offset. The spec states the order “is not specified” (go.dev/ref/spec); the maps blog states it “is not guaranteed to be the same from one iteration to the next” (go.dev/blog/maps); and the runtime source shows the mechanism — two rand() calls in the iterator’s Init (table.go). The gotcha is code that accidentally depends on a stable order: a test that passes locally, a hash computed over map entries, a serialized output that differs between runs.

This is a focused gotcha note. The bucket/group structure, the Swiss-table redesign of Go 1.24, and the load-factor mechanics are Map Internals and Swiss Table Maps; here we assume that structure and trace why iteration order is randomized and how.

Mental Model

Think of a Go map’s storage as a ring of slots. A naive iterator would always start at slot 0 and walk forward — which would produce a stable order, an order determined entirely by the keys’ hash values and the table’s size. Go does the opposite on purpose: every time you start a range over a map, the runtime picks a random slot to start from and a random offset within the starting group, then walks the ring from there, wrapping around. The set of keys is the same; the starting point is different each time, so the sequence is different each time.

The reason is a contract-enforcement trick. The Go authors decided early that map iteration order is not part of the language contract. But “unspecified” is weak — if the order happened to be stable in practice, programmers would unknowingly depend on it, and a future runtime change (a different hash, a different table size, the Swiss-table rewrite) would silently break their code. By actively randomizing, the runtime makes any accidental dependence fail immediately and loudly during development, not later in production. Randomization is a forcing function that turns a latent bug into a visible one.

flowchart LR
    M["map m with keys A B C D E<br/>stored in a ring of slots"]
    M --> I1["range #1: Init() -> rand offset = 3<br/>start at slot 3, wrap<br/>=> D E A B C"]
    M --> I2["range #2: Init() -> rand offset = 1<br/>start at slot 1, wrap<br/>=> B C D E A"]
    M --> I3["range #3: Init() -> rand offset = 4<br/>=> E A B C D"]
    style I1 fill:#1e3a5f,color:#fff
    style I2 fill:#1e3a5f,color:#fff
    style I3 fill:#1e3a5f,color:#fff

Diagram: one map, three range loops, three different orders — because each iterator’s Init draws a fresh random starting offset. The keys are identical every time; only the entry point into the ring changes. The insight: the disorder is injected at iterator-creation time, per-loop, not baked into the table’s layout.

Mechanical Walk-through

What the spec promises (and does not)

The spec’s “For statements with range clause” section states the iteration order over a map is not specified. That is the contract: a program may not rely on any particular order. The blog goes one step further and describes the observable behavior — order “is not guaranteed to be the same from one iteration to the next” (go.dev/blog/maps) — i.e. it is not merely arbitrary-but-fixed; it varies run to run and loop to loop.

It is worth being precise about what is and is not randomized. The order of keys within a single range is randomized. A range is also permitted to skip keys added during the iteration or to visit them, and visiting a key that has been deleted during iteration is not guaranteed — but those are separate hazards. This note is about the starting-offset randomization.

The mechanism in the runtime source

Go 1.24 replaced the old bucket-chain map with a Swiss-table design (go.dev/doc/go1.24); the iterator now lives in internal/runtime/maps. The Iter struct in table.go carries two offset fields, with this exact comment (table.go):

// 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

And the iterator’s Init method sets both from the runtime random source:

func (it *Iter) Init(typ *abi.MapType, m *Map) {
    it.typ = typ
    if m == nil || m.used == 0 {
        return
    }
    // ...
    it.m = m
    it.entryOffset = rand()   // <-- random slot offset within a group
    it.dirOffset = rand()     // <-- random offset into the table directory
    it.globalDepth = m.globalDepth
    // ...
}

So the randomization is two-level, matching the Swiss-table’s two-level structure. dirOffset randomizes which table in the map’s directory the iterator visits first; entryOffset randomizes which slot within a group it visits first. The Next method (also in table.go) computes the actual position as (it.dirIdx + it.dirOffset) % it.m.dirLen and similarly applies entryOffset within a group — wrapping around so every entry is still visited exactly once, just starting from a random point. The comment in Next calls the result a “completely randomized dirIdx that may refer to a middle of a run of tables.”

The key takeaways from the source: (1) the randomization happens per Init — i.e. once per range loop, when the compiler-generated range code constructs the iterator; (2) it uses the runtime’s rand(), so it varies every loop and every program run; (3) it is structural — every key is still visited exactly once, only the entry point moves.

What rand() actually is

The rand() called inside maps.Iter.Init is the runtime’s own random source — runtime.rand, declared in src/runtime/rand.go and reached from internal/runtime/maps through the runtime’s internal plumbing (the same rand() the package uses to seed each map’s hash0 in NewMap). Its own comment is “rand returns a random uint64 from the per-m chacha8 state. This is called from compiler-generated code” (runtime/rand.go). Two facts settle the earlier open question. First, the generator is per-M, not per-goroutine: rand() does mp := getg().m and reads mp.chacha8, so the state lives on the OS-thread-bound m, and the comment notes it deliberately avoids acquirem on the fast path so a range costs just a getg, an inlined c.Next, and a return. Second, it is not the old fastrand linear generator — since Go 1.22 the runtime’s per-M state is a ChaCha8 stream cipher (mp.chacha8), seeded at thread creation (mrandinit) from the global bootstrap RNG, which is itself seeded at process startup from operating-system entropy. So map iteration offsets are drawn from a cryptographic-strength per-thread stream, varying every loop and every run.

Why the old bucket map randomized too

Before Go 1.24, the classic bucket map (runtime/map.go) achieved the same effect with two iterator fields, startBucket (“bucket iteration started at”) and offset (“intra-bucket offset to start from”). mapiterinit set both from one rand() draw — r := uintptr(rand()); it.startBucket = r & bucketMask(h.B); it.offset = uint8(r >> h.B & (abi.MapBucketCount - 1)) (runtime/map.go @ go1.23.0) — i.e. it reused the low hash bits of one random word to pick the starting bucket and the high bits to pick the starting slot within it. (Older Go releases drew this from fastrand; by Go 1.22+ it is the same per-M ChaCha8 rand() described above — the cosmetic source changed, the contract did not.) The Swiss-table rewrite changed the data structure but preserved the randomization contract: randomizing iteration order is a deliberate, version-stable property, not an artifact of either implementation. (See Map Internals for the old bucket layout and Swiss Table Maps for the new one.)

The one exception: fmt printing of maps

There is a single, deliberate exception to “maps iterate randomly.” The fmt package, when printing a map (%v), sorts the keys so that output is reproducible — fmt.Println(m) is stable across runs. This is implemented inside fmt using reflection and a sort, not by ranging the map. So fmt map output being ordered is not a counterexample to randomization; it is fmt going out of its way to undo it.

Code Examples with Line-by-Line Commentary

Example 1 — observing the randomization

package main
 
import "fmt"
 
func main() {
    m := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4}
    for i := 0; i < 3; i++ {
        for k := range m {           // each range loop -> fresh Iter.Init -> fresh rand offsets
            fmt.Print(k, " ")
        }
        fmt.Println()
    }
}
// Possible output (varies every run):
//   c a d b
//   b d a c
//   a c d b

Line 8’s for k := range m causes the compiler to emit code that constructs a map iterator and calls its Init — which draws entryOffset and dirOffset from rand(). Because that happens once per loop, the three loops on lines 7–11 get three independent random starting points and print three different orders.

Example 2 — the gotcha: a test that relies on order

func keysOf(m map[string]int) []string {
    var out []string
    for k := range m {               // RANDOM order
        out = append(out, k)
    }
    return out
}
 
// In a test:
func TestKeys(t *testing.T) {
    got := keysOf(map[string]int{"x": 1, "y": 2})
    want := []string{"x", "y"}       // BUG: assumes a fixed order
    if !reflect.DeepEqual(got, want) {
        t.Fatalf("got %v, want %v", got, want)
    }
}

keysOf returns keys in whatever order the range produced. The test on line 12 hard-codes ["x", "y"]. Because range randomizes, the test passes roughly half the time and fails the other half — a flaky test. The randomization is doing its job: it surfaces the latent assumption immediately. The fix is to sort before comparing, or to compare as sets.

Example 3 — the fix: sort the keys for a deterministic order

import "slices"
 
func sortedKeysOf(m map[string]int) []string {
    out := make([]string, 0, len(m))
    for k := range m {               // still random...
        out = append(out, k)
    }
    slices.Sort(out)                 // ...but now imposed into a stable order
    return out
}

The range on line 5 is still random; line 8’s slices.Sort (standard library slices package, Go 1.21+) imposes a deterministic order after collection. This is the canonical pattern the maps blog itself prescribes — collect keys, sort, then iterate the sorted slice. The pre-1.21 form used sort.Strings.

Example 4 — a subtler bug: order-dependent serialization

func fingerprint(m map[string]string) string {
    h := sha256.New()
    for k, v := range m {            // RANDOM order
        h.Write([]byte(k))
        h.Write([]byte(v))
    }
    return hex.EncodeToString(h.Sum(nil))
}

This computes a SHA-256 over the map’s entries. Because range order is random, the same map hashes to a different value on every call. Any code comparing fingerprints — cache keys, change detection, deduplication — breaks silently. The fix: collect entries, sort by key, then hash in sorted order. Note that encoding/json already does this internally — it sorts map keys when marshaling — so json.Marshal of a map is deterministic, by the same deliberate effort fmt makes.

Failure Modes and How to Diagnose Them

Symptom: a flaky test that passes ~50% of the time. Almost always an assertion comparing a slice built from a map range against a hard-coded order. Diagnose by running the test 20 times (go test -count=20); intermittent failure with order-shuffled output confirms it. Fix: sort, or compare as a set/map.

Symptom: non-reproducible output between runs. A program prints, hashes, or serializes the result of ranging a map without sorting. Diagnose by running twice and diffing. Fix: collect-and-sort.

Symptom: golden-file tests diff spuriously. A golden file captured one random order; later runs produce another. Fix: make the producer emit sorted output, then regenerate the golden file.

Symptom: a hash/checksum over map data is unstable. As in Example 4. Fix: canonicalize (sort) before hashing.

Non-symptom: fmt.Println(m) looks ordered. That is fmt sorting keys deliberately; it is not evidence that range is ordered. Do not generalize from fmt’s behavior.

Common Misunderstandings

“Map order is undefined, so it’s arbitrary-but-fixed.” No — it is actively varied, per loop and per run. “Undefined” in Go’s case means “deliberately scrambled,” which is strictly stronger and is what makes accidental dependence fail fast.

“The randomization comes from the hash function.” No. The hash determines which slot a key lands in; that is stable for a given map state. The iteration randomization is a separate, explicit rand()-seeded starting offset chosen anew per iterator (entryOffset/dirOffset).

“Small maps iterate in insertion order.” No — there is no insertion-order guarantee at any size. A tiny map may appear stable across a few runs by chance, but the rand() offsets still apply (the Init code draws them whenever m.used > 0). Never rely on observed stability of small maps.

“fmt proves maps are ordered.” Covered above — fmt sorts; range does not.

“Randomization makes maps slower.” The cost is two rand() calls and a modulo per range — negligible. It is a correctness device, not a performance trade.

Alternatives and When to Choose Them

Collect keys into a slice and slices.Sort them — the standard answer when you need a deterministic traversal. Two extra lines; choose this for tests, serialization, hashing, and any reproducible output.

Maintain an explicit ordered structure alongside the map — when you need insertion order (not sorted order) or frequent ordered traversal, keep a []K of keys in insertion order next to the map[K]V. The blog shows the sorted-slice variant; the insertion-order variant is the same idea with the sort omitted and an append on every new key.

An ordered-map data structure — a container/list + map combination, or a third-party ordered map, when ordered iteration is a core requirement and you do not want to re-sort on every traversal. Heavier; choose only when traversal frequency justifies it.

encoding/json / fmt for reproducible output — if all you need is deterministic printed output, both already sort map keys for you. No code needed.

Do not “stabilize” by relying on observed order, or by disabling randomization — there is no supported knob to turn map randomization off, and that is intentional.

Production Notes

The maps blog is unambiguous: “if you need a stable iteration order you must maintain a separate data structure that specifies that order” (go.dev/blog/maps). The randomization was introduced precisely because, in Go’s early days, map iteration happened to be stable enough that programs accidentally depended on it, and the team wanted to break that dependence permanently before the contract calcified. The Swiss-table rewrite in Go 1.24 vindicates that decision — it changed the entire map data structure, and code that had (wrongly) relied on the old order would have broken; code written against the randomized contract did not.

In real systems the bug is overwhelmingly a test problem — flaky CI from order-sensitive assertions — and a serialization problem — non-reproducible builds, unstable cache keys, golden-file churn. The discipline is simple and absolute: whenever the order of a map traversal can be observed by anything outside the loop, sort first. When it cannot — you are just summing values, counting, or mutating — the randomization is invisible and free.

See Also

Graph View

Backlinks