Just don't make it uniformly distributed random, otherwise people will depend on it as a random number generator, what you don't want either.
Hash Ordering and Hyrum's Law
21–30 of 42 posts
Re: Hash Ordering and Hyrum's Law
#22(from Feb 2021) Some of the JDK's unmodifiable collections, such as those from `Set.of()` and `Map.of()`, also randomize iteration order. At the time they were added, Go and Python also randomized iteration order. However, more recently, Python moved away from randomization. Early in the Python 3.x releases, dict iteration order was randomized. In 3.6, iteration order was insertion order, but only as an implementatio…
IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. And since hash-first languages provide a broken API, there's no way to provide it for arbitrary types. Compare-first languages (like C++) generally provide it, but paying the price of tree-based structures (assuming a B-tree can't negate it) isn't actually n…
> IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it.
This would be a lot more convincing if you had an actual concrete example where this was true, rather than just insisting that "sometimes" it's true.
Re: Hash Ordering and Hyrum's Law
#23Earlier quoted context omitted.
IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. And since hash-first languages provide a broken API, there's no way to provide it for arbitrary types. Compare-first languages (like C++) generally provide it, but paying the price of tree-based structures (assuming a B-tree can't negate it) isn't actually n…
> IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. This would be a lot more convincing if you had an actual concrete example where this was true, rather than just insisting that "sometimes" it's true.
Few examples I’ve come across: hashing, float summation, reproducible serialisation
Re: Hash Ordering and Hyrum's Law
#24What's the advantage of specifying it as random over specifying it as sequential in some way? Aren't both just specifying a behavior, where one behavior is potentially more useful than the other? I guess I understand the principled point that a set of hash keys is not an array. But it seems like more complexity than is necessary, and even possible to fall victim to Hyrum's law besides… you can imagine someone using r…
Unfortunately, map can (and does) have external effects in most languages, so your code could still be effected by the external order.
I’ve actually worked on some maths code where we wanted to prove algorithms worked correctly in exactly this type of situation, so we wanted to prove our code iterating over a hashed container was order-invariant. You can do it, but involves pulling in theorem provers, and is beyond what most people would probably tolerate.
Re: Hash Ordering and Hyrum's Law
#25Earlier quoted context omitted.
> IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. This would be a lot more convincing if you had an actual concrete example where this was true, rather than just insisting that "sometimes" it's true.
Few examples I’ve come across: hashing, float summation, reproducible serialisation
Huh. I guess somebody could build a specialised container for this purpose, which deliberately has some arbitrary but unchanging ordering. Certainly that looks practical in Rust (indeed it may already exist, I haven't looked).
Re: Hash Ordering and Hyrum's Law
#26I wanna say that Abseil's hash function does something like this? It was a couple of years ago, but I remember tearing my hair out figuring out why hash tables passed from a C++ api to my tests were failing. Turns out, the tests and the API was compiled by my build system as separate libraries and dynamically linked, and that abseil seeded their hash function with the address of a dummy global variable (which had a different location in the main program and the tests).
Presumably because they didn't want people to depend on the value of the hash function because of Hyrum's Law, but that meant the hash tables couldn't be passed across a DLL boundary, which seemed like an insane tradeoff to me. But hey, I'm not google, I get why they would do it.
Re: Hash Ordering and Hyrum's Law
#27Just don't make it uniformly distributed random, otherwise people will depend on it as a random number generator, what you don't want either.
They might depend on it even if it's not uniformly distributed :)
Re: Hash Ordering and Hyrum's Law
#28Earlier quoted context omitted.
> IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. This would be a lot more convincing if you had an actual concrete example where this was true, rather than just insisting that "sometimes" it's true.
Few examples I’ve come across: hashing, float summation, reproducible serialisation
I get two of those, can you tell me more about float summation?
Re: Hash Ordering and Hyrum's Law
#29(from Feb 2021) Some of the JDK's unmodifiable collections, such as those from `Set.of()` and `Map.of()`, also randomize iteration order. At the time they were added, Go and Python also randomized iteration order. However, more recently, Python moved away from randomization. Early in the Python 3.x releases, dict iteration order was randomized. In 3.6, iteration order was insertion order, but only as an implementatio…
IMO the real problem is that sometimes you really do want a deterministic order (not caring which one), but the container doesn't offer any API that provides it. And since hash-first languages provide a broken API, there's no way to provide it for arbitrary types. Compare-first languages (like C++) generally provide it, but paying the price of tree-based structures (assuming a B-tree can't negate it) isn't actually n…
C++ gives both ‘map’ and ‘unordered_map’, and in my experience idiomatic C++ uses unordered_map unless you actually need a tree.
Re: Hash Ordering and Hyrum's Law
#30What's the advantage of specifying it as random over specifying it as sequential in some way? Aren't both just specifying a behavior, where one behavior is potentially more useful than the other? I guess I understand the principled point that a set of hash keys is not an array. But it seems like more complexity than is necessary, and even possible to fall victim to Hyrum's law besides… you can imagine someone using r…
> why is "iteration" even possible over a hash table?
Going through all items in a container seems like a logical thing to want to do.
> Shouldn't the keys be specified as a "set" on which only set-appropriate operations like map can be performed?
Efficient implementation (in space and time) of these set operations would limit the possible efficient implementations of a hash table (i.e. to using the hash value as a key in an ordered map).
Going one step further, this guarantee would freeze behaviour of the hash function (and how they are combined) for all time; optimisations for different architectures would not be possible, nor would avoiding hash collision attacks by changing seeds.
Sometimes hash value stability is what you want (e.g. when transmitting data in space and time), so "frozen" hash functions give these guarantees e.g. https://github.com/google/highwayhash#versioning-and-stabili... .
Yes it can be annoying when tests are flaky, but the unit testing/matcher library should have some reasonably efficient way of matching unordered containers.