Is map iteration sufficiently random for randomly selecting keys?

Question

Can I rely on the random iteration order of maps to implement a random "pairing" of clients in a web application? I've tried looking around but can't seem to find a breakdown of how random this randomness is.

The algorithm would look something like:

var clients map[Client]struct{}

func PairClient(c Client) (Client, error) {
    for m := range clients {
        if m != c {
            return m, nil
        }
    }
    return nil, fmt.Errorf("lobby: insufficient number of clients")
}

Would this be sufficient when there are >1000 connected clients, or should I maintain a separate slice of clients and randomly select from that?

dictionary iteration order is usually a function of insertion and hash collision order, so if you need random, you probably need to introduce some randomness yourself. one way would be to pull the keys of the map, shuffle them randomly and then iterate over the map using your shuffled keys. — matias elgart, Dec 07 '16 at 14:18
It's not guaranteed to be in any specific order, which includes random. While the implementation currently shuffles the output, it's definitely not over a normal distribution. — JimB, Dec 07 '16 at 14:22
Thanks @JimB, I'll keep a slice of Clients and use that instead, or figure out a more efficient solution than that. — Brett Lempereur, Dec 07 '16 at 14:26
@matiaselgart The current implementation actually explicitly randomises iteration. But this is not guaranteed by the standard. — Art, Dec 07 '16 at 14:27
@BrettLempereur: is random access if more important that insertion and deletion, perhaps use a different data structure. A simple sorted slice is `O(1)` random access, `O(log n)` lookup, and `O(n)` insertion, which is often just fine. — JimB, Dec 07 '16 at 14:32
@JimB: Insertion and deletion each happen once per-session, pairing can happen multiple times. I'll need to get some real world data to see which happens more frequently in practice, for now I'll see which comes out cleaner. — Brett Lempereur, Dec 07 '16 at 14:36
@Art wow, unexpected. thank you for the info, very much appreciated. i was curious why golang did this and found (from https://blog.golang.org/go-maps-in-action) : `Since Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation.` — matias elgart, Dec 07 '16 at 14:38

score 8 · Accepted Answer · edited May 23 '17 at 12:13

Even though it said to be random (randomized) (spec, blog, hashmap source, another blog, SO), the distribution is far from being perfect.

Why? Because we like maps being fast, and better random distribution tends to require more computation and/or bigger delays. A compromise had to be made. And because the intention is not to provide a quality "shuffle" functionality by for range, but only to prevent developers relying on stable iteration order (because it could change even without explicit randomization).

But "how good" may this distribution be? Easy to get a "taste". Let's create a map of 10 pairs, and start iterating over it lot of times. And let's count the distribution of the very first index (key):

m := map[int]int{}
for i := 0; i < 10; i++ {
    m[i] = i
}

dist := make([]int, 10)
for i := 0; i < 100000; i++ {
    for idx := range m {
        dist[idx]++
        break
    }
}

fmt.Println("Distribution:", dist)

Output (try it on the Go Playground):

Distribution: [25194 24904 6196 6134 6313 6274 6297 6189 6189 6310]

The first 2 keys (0 and 1) were roughly encountered 4 times more than the rest which had roughly the same probability.

You can tell it's pretty bad for being true (or even good) random, but that's not the point. It's good enough to provide varying iteration order (and importantly: it's fast).

Yup, and the distribution gets even worse depending on the distribution of keys: https://play.golang.org/p/2MMS3pPCMO `[15597 9339 3211 3076 3153 3170 21979 3201 3119 3081 3082 3137 3114 2943 3099 3101 3151 0 0 3101 3150 3196 0]` — JimB, Dec 07 '16 at 14:57

score 5 · Answer 2 · answered Dec 07 '16 at 14:46

From the spec:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. (...)

Which essentially means that the order in which maps are iterated is undefined. Even if it's random right now with the default Go compiler, other compilers or other versions might differ.

Is map iteration sufficiently random for randomly selecting keys?

2 Answers2

Linked