Go: what determines the iteration order for map keys?

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?

Map is implemented in Go as a hashmap.

The Go run-time uses a common hashmap implementation which is implemented in C. The only implementation differences between map[string]T and map[byte]T are: hash function, equivalence function and copy function.

Unlike (some) C++ maps, Go maps aren't fully specialized for integers and for strings.

In Go release.r60, the iteration order is independent from insertion order as long as there are no key collisions. If there are collisions, iteration order is affected by insertion order. This holds true regardless of key type. There is no difference between keys of type string and keys of type byte in this respect, so it is only a coincidence that your program always printed the string keys in the same order. The iteration order is always the same unless the map is modified.

However, in the newest Go weekly release (and in Go1 which may be expected to be released this month), the iteration order is randomized (it starts at a pseudo-randomly chosen key, and the hashcode computation is seeded with a pseudo-random number). If you compile your program with the weekly release (and with Go1), the iteration order will be different each time you run your program. That said, running your program an infinite number of times probably wouldn't print all possible permutations of the key set. Example outputs:

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

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.

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.

To extend @user811773 answer. A semi-random range clause iteration does not mean that the chance of returning each element in a map is also equal. See https://medium.com/i0exception/map-iteration-in-go-275abb76f721 and https://play.golang.org/p/GpSd8i7XZoG.

package main

import "fmt"

type intSet map[int]struct{}

func (s intSet) put(v int) { s[v] = struct{}{} }
func (s intSet) get() (int, bool) {
	for k := range s {
		return k, true
	}
	return 0, false
}
func main() {
	s := make(intSet)
	for i := 0; i < 4; i++ {
		s.put(i)
	}
	counts := make(map[int]int)
	for i := 0; i < 1024*1024; i++ {
		v, ok := s.get()
		if !ok {return}
		counts[v]++
	}
	for k, v := range counts {
		fmt.Printf("Value: %v, Count: %v\n", k, v)
	}
}
/*
Value: 1, Count: 130752
Value: 2, Count: 130833
Value: 0, Count: 655840
Value: 3, Count: 131151
*/