Go: what determines the iteration order for map keys?

Question

The Go Programming Language Specification says:

3. The iteration order over maps is not specified. [...]

That's to be expected since a map type can be implemented as a hash table, or as a search tree, or as some other data structure. But how is map actually implemented in Go?

Put differently, what determines the iteration order of the keys in

for k, _ := range m { fmt.Println(k) }

I started wondering about this after I saw that a map with string keys apparently do have a certain iteration order. A program like

package main
import ("fmt"; "time"; "rand")

func main() {
    rand.Seed(time.Seconds())
    words := [...]string{"foo", "bar", "a", "b", "c", "hello", "world",
        "0", "1", "10", "100", "123"}
    stringMap := make(map[string]byte)
    for i := range rand.Perm(len(words)) {
        stringMap[words[i]] = byte(rand.Int())
    }
    fmt.Print("stringMap keys:")
    for k, _ := range stringMap { fmt.Print(" ", k) }
    fmt.Println()
}

prints the following on my machine:

stringMap keys: a c b 100 hello foo bar 10 world 123 1 0

regardless of the insertion order.

The equivalent program with a map[byte]byte map also prints the keys in a shuffled order, but here the key order depends on the insertion order.

How is all this implemented? Is the map specialized for integers and for strings?

Solution 1

If the specs say the iteration order is not specified then a specific order in specific cases is not ruled out.

The point is one cannot rely on that order in any case, not even in some special case. The implementation is free to change this behavior at any given moment, run time included.

Solution 2

Note that it is not that odd for order to be stable regardless of insertion order if there is a total order over the keys (as there frequently may be if they are of a homogenous type); if nothing else, it can allow efficient searching over keys which generate the same hash.

This may well also reflect a different underlying implementation - in particular, this is something people might want for strings, but for integers you could use a sparse array instead.

Comments

[Martin Geisler]

Yeah, I'm not really surprised that there is a stable ordering. I'm more surprised that there is an insertion-independent ordering for strings and not for integers.

[Martin Geisler]

I know that the order cannot be relied upon and that it's okay that there is an order even though the spec doesn't define it.

[Marcin]

@MartinGeisler This may well reflect a different underlying implementation; in particular, this is something people might want for strings, but for integers you could use a sparse array instead.