[porridgeraisin]

> mix randomisation into hash tables.

I believe you don't understand.

In go, they literally randomly permute the iteration order of the map each time you iterate over it.

e.g

  for x in map {
  
  }

  for x in map {
   // different order
  }

Now, the fact that they randomize means people use it as a cheap "select random item from map" function :D, which is hyrums law all over again.

  var randomUser User
  for userId, user in usersMap {
    randomUser = user
    break
  }

Funny isn't it.

[deathanatos]

Well … it seems like you're right. (A playground — https://go.dev/play/p/OHQTIuDWicd — if anyone is curious.)

That's … pretty surprising, since that would seem to imply that iteration would require a O(n) sized chunk of memory somewhere to reify the order into. (And probably O(n) time to do the shuffle, or at least, a copy of the ordering; we should shuffle as we go, I suppose, but we'd need to track what we've emitted & what we've not, hence O(n) time & space to populate that scratch…) That seems undesirable.

[porridgeraisin]

They actually do it without needing a O(n) memory chunk, aiui.

1. choose starting bucket randomly

2. From there iterate through buckets in usual order (wrapping around)

3. Within each bucket, generate permutation of 0..7, and stream it in that order.

See func mapiterinit() in runtime/map.go

This is just me musing, but you can probably precompute all permutations of 0..7 and store it for ~20KB once for the whole runtime, and just index that each time. Can avoid the fischer yates each time.

[bboreham]

Do note your last example makes a biased, or poorly random, selection.