Non-deterministic set ordering

[Rob Cliffe]

I was shocked to discover that when repeatedly running the following
program (condensed from a "real" program) under Python 3.8.3

for p in { ('x','y'), ('y','x') }:
    print(p)

the output was sometimes

('y', 'x')
('x', 'y')

and sometimes

('x', 'y')
('y', 'x')

Can anyone explain why running identical code should result in
traversing a set in a different order?
Thanks
Rob Cliffe

[Dan Stromberg]

Sets are defined as unordered so that they can be hashed internally to give
O(1) operations for many tasks.

It wouldn't be unreasonable for sets to use a fixed-by-arbitrary ordering
for a given group of set operations, but being unpredictable deters
developers from mistakenly assuming they are ordered.

If you need order, you should use a tuple, list, or something like
https://grantjenks.com/docs/sortedcontainers/sortedset.html

[Rob Cliffe]

Thanks, I can work round this behaviour.
But I'm curious: where does the variability come from?  Is it deliberate
(as your answer seems to imply)?  AFAIK the same code within the *same
run* of a program does produce identical results.
Best wishes
Rob Cliffe

[Paul Bryan]

This may explain it:
https://stackoverflow.com/questions/27522626/hash-function-in-python-3-3-returns-different-results-between-sessions

[Rob Cliffe]

Thanks, Paul.  Question answered!
Rob Cliffe

[MRAB]

Basically, Python uses hash randomisation in order to protect it against
denial-of-service attacks. (Search for "PYTHONHASHSEED" in the docs.)

It also applied to dicts (the code for sets was based on that for
dicts), but dicts now remember their insertion order.