Hash Ordering and Hyrum's Law

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 necessary.

Rather than either of those choices, I argue that languages really should be "key-first" - rather than having classes implement hashing or comparison themselves, they should return a tuple of the data that will be fed into said hash or comparison. Besides being a nicer API, this also prevents many common bugs.

Obviously, one should not willy-nilly break customers for no reason. The point is not to create a management metric around Number Of Times We've Broken The Customer and reward the team for getting their numbers up, up, up. The point is to retain flexibility and the ability to move forward, and that is done through intelligent design up front to the extent possible, and carefully selecting when to break customers over the course of years. It's always expensive and should definitely be treated as an expense, not a benefit on its own terms. But as the Hyrum's Law "builds up" its expense to the company over all will in not really all that long overwhelm the costs of the occasional breakage to stay up-to-date with the world.

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.

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.

It certainly may be useful to define an specific ordering. Maps ordered by insertion time and maps ordered by key order are fairly common. But maps with these constraints probably won't be as fast as those with arbitrary ordering, so there is a trade-off decision to be made. A map constrained to the arbitrary ordering of the initial implementation is the worst of both worlds: difficult to make faster despite not having a particularly useful ordering.

As a concrete example, I am currently in the middle of rewriting Go's map implementation to use a more efficient design (https://go.dev/issue/54766). If Go hadn't randomized map iteration order this work would likely be impossible. It is unlikely we could completely change the design while keeping iteration order identical to the old implementation (assuming we want the new version to be faster at least).

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.

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.

From the python 3.6 change log:

New dict implementation¶ The dict type now uses a “compact” representation based on a proposal by Raymond Hettinger which was first implemented by PyPy. The memory usage of the new dict() is between 20% and 25% smaller compared to Python 3.5.

The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon (this may change in the future, but it is desired to have this new dict implementation in the language for a few releases before changing the language spec to mandate order-preserving semantics for all current and future Python implementations; this also helps preserve backwards-compatibility with older versions of the language where random iteration order is still in effect, e.g. Python 3.5). (Contributed by INADA Naoki in bpo-27350. Idea originally suggested by Raymond Hettinger.)

https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-imple...

> We didn’t invent this idea. Python and Go were both doing this before us, and we modeled our approach on Python’s.

However, this is referring to the actual hashing. Also, Python was doing it for a fundamentally different reason (to avoid denial-of-service attacks caused by pathological input where every key would map to the same hash bucket).

However, starting with Python 3.6, the dictionary implementation doesn't actually store the key-value pairs directly in the hash buckets. Instead, it stores indices for a separate table. This saves space (because the indices can be much smaller than full entries) and also incidentally makes it easy to iterate over key-value pairs in order of insertion (by iterating over the table).

This proved popular, and in 3.7 it became official that this preservation of insertion order would be guaranteed going forward. Note that this is not a "sorted" dictionary structure; the keys are not compared or ordered by value.

Note that space is not freed up in the table when an element is deleted; this would require either O(N) shifting of the data, or ruining the insertion order. As such, Python developers accidentally cheated themselves out of a further optimization by deciding to offer the guarantee.

I have some notes (and a quick demo program) on GitHub demonstrating the space performance characteristics across Python versions: https://github.com/zahlman/python-dict-stats/ . This includes a link to https://stackoverflow.com/questions/327311 which gives a lot of detail about the implementation.

>Now, reading Python docs on that topic, they briefly[1] mention that dictionaries’ list views yield items in the order they were inserted without any mentions if items are sorted or not.

It seems clear enough to me:

> Performing list(d) on a dictionary returns a list of all the keys used in the dictionary, in insertion order (if you want it sorted, just use sorted(d) instead).

The insertion order guarantee is more formally documented in the What's New in Python 3.7 documentation (https://docs.python.org/3/whatsnew/3.7.html), which cites the original decree on the mailing list (https://mail.python.org/pipermail/python-dev/2017-December/1...).