DEV Community

Waldemar Quevedo
Waldemar Quevedo

Posted on

Go’s map iteration order is not that random?

I have been using Go for around 5 years already so by now had already internalized the behavior for range on maps to be random. This observable behavior of how Go's for range works on maps, naturally lead to code as follows to look correct to me:

package main

import (
    "fmt"
)

func pickRandom(entries map[string]int) string {
    var key string
    for k, _ := range entries {
        // Chose the random key
        key = k

        // Mark that it has been used
        entries[k]++
        break
    }
    return key
}

func main() {
    entries := make(map[string]int)
    entries["A"] = 0
    entries["B"] = 0
    entries["C"] = 0

    for i := 0; i < 10000; i++ {
        pickRandom(entries)
    }

    for k, v := range entries {
        fmt.Printf("key=%s hit=%v\n", k, v)
    }
}
Enter fullscreen mode Exit fullscreen mode

So I was very surprised once I saw that the following results being repeated constantly:

key=A hit=7511
key=B hit=1279
key=C hit=1210
Enter fullscreen mode Exit fullscreen mode

Looks like it doesn't matter how many times this is run, the first entry of the map will always get at least 7000 of the hits 😱

One way to fix this would be to instead create an extra array with they keys then use rand to get a random one, for example using math/rand:

package main

import (
    "fmt"
    "math/rand"
)

func pickRandom(entries map[string]int) string {
    var key string
    choices := []string{}
    for k, _ := range entries {
        choices = append(choices, k)
    }

    // Choose random one and mark that it was hit
    key = choices[rand.Intn(len(choices))]
    entries[key]++

    return key
}

func main() {
    entries := make(map[string]int)
    entries["A"] = 0
    entries["B"] = 0
    entries["C"] = 0

    for i := 0; i < 10000; i++ {
        pickRandom(entries)
    }

    for k, v := range entries {
        fmt.Printf("key=%s hit=%v\n", k, v)
    }
}
Enter fullscreen mode Exit fullscreen mode

Now the results look much better!

key=A hit=3254
key=B hit=3387
key=C hit=3359
Enter fullscreen mode Exit fullscreen mode

I was pointed that this could be a good example of the Hyrum's Law:

With a sufficient number of users of an API,
it does not matter what you promise in the contract:
all observable behaviors of your system
will be depended on by somebody.
Enter fullscreen mode Exit fullscreen mode

We ended up accidentally depending on the for range behavior in the Go NATS client, where it was causing an imbalance with one server often having more connections than others in the server pool (issue has since then been fixed).

Top comments (0)