This exact issue is why go actively randomises dict iteration too.
Seems really odd that the same team would have used a stable sort and just documented as “not guaranteed to be stable”.
Seems really odd that the same team would have used a stable sort and just documented as “not guaranteed to be stable”.
The reason is that a hash table with a fixed hash function may be used for denial of service attacks. If an attacker knows how a hash map maps keys and can control the keys being inserted, they can insert thousands of keys that all map to the same hash, effectively turning the hash map into a list or vector that has to be searched linearly (on both lookups and insertions)
And that’s a real problem. https://lwn.net/Articles/474912/ says:
“That's where web frameworks come into play. Those frameworks helpfully collect up all of the POST form data that gets sent to a particular web page into a dictionary that gets handed off to the application for processing. The amount of data that the frameworks will allow is typically rather large (e.g. 1MB), so an attacker can create tens of thousands of form entries in a single HTTP request. Because they all collide, those entries can take tens of seconds to a few minutes to process on an i7 core according to the advisory [PDF] released by Wälde and Klink.”
If you manage to insert 10,000 keys with identical hashes, that’s about 10,000²/2 key comparisons.
They absolutely are.
> The reason is that a hash table with a fixed hash function may be used for denial of service attacks. If an attacker knows how a hash map maps keys and can control the keys being inserted, they can insert thousands of keys that all map to the same hash, effectively turning the hash map into a list or vector that has to be searched linearly (on both lookups and insertions)
That has nothing to do with what I'm talking about.
Independent from hash randomisation, Go will randomise the iteration of hashmaps, such that iterating the same hashmap twice, within the same process, without having modified it in any way, will yield different results. Currently this is done by offsetting the starting point of the iteration by a random amount.
For some reason they dropped this explicit mention when https://go.dev/blog/go-maps-in-action was moved over to https://go.dev/blog/maps, but it used to be there:
> Since the release of Go 1.0, the runtime has randomized map iteration order. Programmers had begun to rely on the stable iteration order of early versions of Go, which varied between implementations, leading to portability bugs.
You can trivially observe this behaviour by just iterating the same map multiple times. With mere hash randomisation, even if hash randomisation was done on a per-map basis by iterating the same map you'd observe the same order, but in Go you don't: https://go.dev/play/p/3HZBv2WHKcT
As you can see the items are always in the same relative order, but the starting point of the iteration varies.
You can also see this in the initialisation of the map iterator, it's even labelled with a nice little comment: https://github.com/golang/go/blob/master/src/runtime/map.go#...