Why are iterations over maps random?

Question

From the Golang source code, they seem to follow a pretty standard implementation of hash tables (ie array of buckets). Based on this it seems that iteration should be deterministic for an unchanged map (ie iterate the array in order, then iterate within the buckets in order). Why do they make the iteration random?

Answer 1

TL;DR; They intentionally made it random starting with Go 1 to make developers not rely on it (to not rely on a specific iteration order which order may change from release-to-relase, from platform-to-platform, or may even change during a single runtime of an app when map internals change due to accommodating more elements).

The Go Blog: Go maps in action: Iteration order:

When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Since the release of Go 1.0, the runtime has randomized map iteration order. Programmers had begun to rely on the stable iteration order of early versions of Go, which varied between implementations, leading to portability bugs. If you require a stable iteration order you must maintain a separate data structure that specifies that order.

Also Go 1 Release Notes: Iterating in maps:

The old language specification did not define the order of iteration for maps, and in practice it differed across hardware platforms. This caused tests that iterated over maps to be fragile and non-portable, with the unpleasant property that a test might always pass on one machine but break on another.

In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order.

This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem. Just as important, it allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a map.

Notable exceptions

Please note that the "random" order applies when ranging over the map using for range.

For reproducible outputs (for easy testing and other conveniences it brings) the standard lib sorts map keys in numerous places:

1. encoding/json

The json package marshals maps using sorted keys. Quoting from json.Marshal():

Map values encode as JSON objects. The map's key type must either be a string, an integer type, or implement encoding.TextMarshaler. The map keys are sorted and used as JSON object keys by applying the following rules, subject to the UTF-8 coercion described for string values above:

• keys of any string type are used directly
• encoding.TextMarshalers are marshaled
• integer keys are converted to strings

2. fmt package

Starting with Go 1.12 the fmt package prints maps using sorted keys. Quoting from the release notes:

Maps are now printed in key-sorted order to ease testing. The ordering rules are:

• When applicable, nil compares low
• ints, floats, and strings order by <
• NaN compares less than non-NaN floats
• bool compares false before true
• Complex compares real, then imaginary
• Pointers compare by machine address
• Channel values compare by machine address
• Structs compare each field in turn
• Arrays compare each element in turn
• Interface values compare first by reflect.Type describing the concrete > - type and then by concrete value as described in the previous rules.

3. Go templates

The {{range}} action of text/template and html/template packages also visit elements in sorted keys order. Quoting from package doc of text/template:

{{range pipeline}} T1 {{end}}
  The value of the pipeline must be an array, slice, map, or channel.
  If the value of the pipeline has length zero, nothing is output;
  otherwise, dot is set to the successive elements of the array,
  slice, or map and T1 is executed. If the value is a map and the
  keys are of basic type with a defined order, the elements will be
  visited in sorted key order.

Answer 2

This is important for security, among other things.

There are lots of resources talking about this online -- see this post for example