As we all know, a map is an unordered collection of key-value pairs. When we iterate over a map using a for range loop, the order of iteration is not guaranteed to be the same each time. This is by design, as we use a random mechanism during the iteration process to ensure that the order is not predictable.

Let’s dive into the implementation details of how Go handles map iteration.

Review underlying structure of map

We already introduced the underlying structure of a map in this post. we should notice the below points:

• There is a bucket array in hmap structure. and each bucket contains up to 8 key-value pairs.
• bmap contains a pointer to the next overflow bucket, which is used when there are more than 8 key-value pairs in a bucket. So it means every bucket has an independent overflow bucket chain.

So based on that, technically, we can iterate over a map in the same order. Just need to traverse the bucket array and for each bucket, traverse its key-value pairs and overflow buckets.

How does Go implement map iteration?

Go map iteration implements a randomized circular traversal algorithm to ensure unpredictable iteration order while guaranteeing complete coverage of all elements.

Go uses a structure called hiter to manage the state of the iteration. It has multiple fields, but here we will focus on the below three fields:

type hiter struct {
    startBucket uintptr      // random starting bucket
    offset      uint8        // random offset within start bucket  
    wrapped     bool         // have we wrapped around the bucket array?
    // ... other fields
}

• StartBucket: This field stores a random starting bucket index. It is generated when the iterator is created.
• Offset: This field stores a random offset within the starting bucket. It is also generated when the iterator is created.
• Wrapped: This boolean field indicates whether the iteration has wrapped around the bucket array.

Initialization Process

// Generate randomness
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
    r += uintptr(fastrand()) << 31
}

// Calculate random starting position
it.startBucket = r & bucketMask(h.B)           // Random bucket
it.offset = uint8(r >> h.B & (bucketCnt - 1))  // Random offset within bucket

so the startBucket and offset can make sure that the iteration starts from a random position.

Iteration Process

The iteration follows these steps:

• Start: Begin at startBucket[offset]
• Forward: Traverse remaining elements in current bucket
• Overflow: Follow overflow chain if exists
• Next: Move to next bucket (circular: (bucket + 1) % numBuckets)
• Wrap: When returning to startBucket, set wrapped = true
• Complete: Process elements [0...offset-1] in start bucket
• End: When wrapped == true and back at start bucket

More thoughts

Predictable Vs Unpredictable

Actually, I think when we say the order is unpredictable, it means that the starting point is unpredictable. Once the starting point is fixed, then the next elements are predictable. But it’s just for the same map, if you add or delete elements, then the order should be changed

func main() {
	m := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6}

	for key, v := range m {
		fmt.Println(key, v)
	}
}

when you run above code multiple times, you may get the below output

c 3 -> d 4 -> e 5 -> f 6 -> a 1 -> b 2
a 1 -> b 2 -> c 3 -> d 4 -> e 5 -> f 6
e 5 -> f 6 -> a 1 -> b 2 -> c 3 -> d 4

you might get multiple different outputs, but if you look closely, you will find that the order is actually predictable once the starting point is fixed. b always follows a, c always follows b, and so on.

Modify map during iteration

What if we add/delete/modify elements during the iteration? Will it be reflected in the iteration? The answer is it might be reflected, but not guaranteed.

If we add/delete/modify elements that have not been iterated yet, it might be reflected in the iteration. But if we add/delete/modify elements that have already been iterated, it will not be reflected in the iteration.