Hacker News Reader

Comment by drngdds | Hacker News Reader

I haven't done a ton of Python, but I can't really think of a situation where relying on a dict to be ordered is an easy mistake to make. Do you have an example?

View on HN

I saw this in Perl a long time ago but it could just as easily have happened in Python. The dict (Perl hash) was a set of mappings for template replacement of "from" strings to "to" strings.

    "FOO" => "bar" # Replace FOO with bar

The author had considered the case where one key (FOO) might be a left-substring of another (FOOBAR), and so reversed the output from keys() before iterating over the hash. This ensured that FOOBAR, which sorts later, would be substituted before FOO (else FOOBAR -> barBAR, oops).

Unfortunately, despite empirical evidence to the contrary at the time, keys() does not guarantee sort-order results https://perldoc.perl.org/functions/keys.html

This worked for a while (appeared to work?) and but was subsequently caught by another developer, who added a sort().

(Get a templating library alreay yeesh).

Incidentally Ruby made the transition to sorted Hash some years ago (1.9 maybe?) and I don't remember any great fall-out.

I definitely recall there being no fall out or or problems when ruby did it in I think 1.9. Semantically, I can't think of how there would be. Since previously order was unpredictable and not guaranteed, it could be anything at all; always using insertion order is, after all, one possible value of "anything at all".

Only possible downside might be performance (or memory). I recall the ruby maintainers ensuring they had an implementation with very little if any performance/memory implication.

The Perl example sounds like someone incorrectly assuming that the output from `keys` be ordered, when it's explicitely not:

> Hash entries are returned in an apparently random order. The actual random order is specific to a given hash; the exact same series of operations on two hashes may result in a different order for each hash.

Applying a `sort` to the output of `keys` is second nature to me - I'm always aware that hash entries are unordered in Perl.

The most common situation I saw was where the entries from the dictionary were being iterated over and used to perform edits on a structure whose edits were nearly commutative.

For example, suppose you have a dictionary containing PriorityItem values. PriorityItems are sorted by priority, while the value only matters for equality (affects __eq__ but not __lt__). If you have a dictionary whose values are PriorityItems and you say `sorted(dictionary.values())` the order of the output could vary w.r.t. equal priority items. So if you wrote a test asserting a process hiding a dictionary had a stable ordering of the items, it might consistently pass by accident on your machine and then fail elsewhere.

Reply on news.ycombinator.com