Hash Ordering and Hyrum's Law
eaftan.github.io
Hash Ordering and Hyrum's Law
1–10 of 42 posts
Re: Hash Ordering and Hyrum's Law
#2Hash iteration order is a great example of Hyrum’s Law
An even better example (requires less words) https://xkcd.com/1172/
Re: Hash Ordering and Hyrum's Law
#3https://www.youtube.com/watch?v=ncHmEUmJZf4
Is a fun presentation by Matthew Kulukundis (designer of Google's Hash Table) with Hyrum Wright offering objections from the crowd (Hyrum's law) about the design and rollout of it at Google
Re: Hash Ordering and Hyrum's Law
#4Interesting note: the JDK deliberately randomizes iteration order of certain immutable sets and maps (https://github.com/openjdk/jdk/blob/jdk-23%2B37/src/java.bas...).
Re: Hash Ordering and Hyrum's Law
#5Alternatively, maintain backward compatibility as much as possible. Function overloading might be too clever. Extra verbosity in exchange for clarity might be a worthwhile tradeoff. WET is acceptable in these scenarios.
Re: Hash Ordering and Hyrum's Law
#6What'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 random hash ordering to implicitly randomize something without needing to call an RNG explicitly.
It seems like the most principled approach might be an re-specification of the data structure: why is "iteration" even possible over a hash table? Shouldn't the keys be specified as a "set" on which only set-appropriate operations like map can be performed?
Re: Hash Ordering and Hyrum's Law
#7What'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…
I think removing methods from the Hashmap was not in scope for their work - they were working on the JDK, and presumably didn't have the bandwidth to patch every single Java library used at Google to use set-based methods instead of iteration-based.
Also, I think in practice you'll find you want to extract items from a set in some order, so you need some kind of transformation from set->list. e.g: you want to print them out.
Edit: Forgot to address your main question. If the specification requires a specific ordering, the implementation is forever bound to do that, even if other implementations would be more efficient/secure/other-desirable-properties. By introducing randomness, you reduce the risk of people accidentally relying on unspecified behavior, and are more able to change your implementation later.
Re: Hash Ordering and Hyrum's Law
#8Relevant XKCD:
Re: Hash Ordering and Hyrum's Law
#9What'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…
One advantage to randomization, and why various languages did it in the first place, is that it prevents miscreants from DoSing your service if they know its implementation.
Say you're operating a service and you share its source on GitHub such that anyone can see it. Your language doesn't randomize hash values. Hashes are O(1), right? Well, not if a clever attacker can send you a set of values where they know each one will hash into the same bucket. The you end up with like 9 empty buckets and 1 with 100,000 items in it. Oops!
Old Python pre-randomization had a dict.items() method that would yield all the keys in order, conceptually kind of like:
for bucket in self._buckets:
for item in bucket:
yield item
Newer Pythons (since 3.6? 3.7?) do something altogether different, and I can't explain exactly how their ordered dicts work, except to say I sat through a presentation on them and thought it was freaking genius even if I could re-implement it myself without sitting down with their docs.
Re: Hash Ordering and Hyrum's Law
#10What'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…
One advantage to randomization, and why various languages did it in the first place, is that it prevents miscreants from DoSing your service if they know its implementation. Say you're operating a service and you share its source on GitHub such that anyone can see it. Your language doesn't randomize hash values. Hashes are O(1), right? Well, not if a clever attacker can send you a set of values where they know each o…
> and I can't explain exactly how their ordered dicts work
Traditionally you simply use a doubly linked list approach on the entries (each entry maintains two additional references to the previous and next entry) for that like LinkedHashMap: https://docs.oracle.com/javase//8/docs/api/java/util/LinkedH...
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...
Which is also what Python seems to be doing: https://stackoverflow.com/a/34496644
It's fairly intuitive.
Do their new default (now also ordered?) dics do this differently?