21

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?

4 Answers 4

30

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
...
4
  • 2
    Thanks for the insights! It's nice to know that Go 1 will randomize this since it makes it much easier to find cases where you happen to rely on the key order by mistake. Mar 8, 2012 at 16:58
  • Thanks, that's an interesting code. Not the kind of hashmap code I'm used too, this one needs more than a few minutes to analyze : Mar 8, 2012 at 19:03
  • @dystroy Yes, the code is a bit atypical. Another interesting problem would be to verify that the hashmap implementation is safe: Go is a safe language, but it also allows concurrent reads/writes to the same map. Because Go is safe, the programmer shouldn't be able to "invent" an arbitrary pointer because of which the program could crash or be vulnerable from security viewpoint. It would be wrong for the code which does insertion of key-value pairs to use memcpy().
    – user811773
    Mar 9, 2012 at 8:26
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.

1
  • 1
    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. Mar 8, 2012 at 15:15
1

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.

2
  • 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. Mar 8, 2012 at 15:14
  • @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.
    – Marcin
    Mar 8, 2012 at 15:18
0

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
*/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.