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?