2

I just found out that python set order is arbitrary today and I am surprised by that fact. I have always thought the underlying implementation of set and dict were very similar, both as hash table. The major difference I thought was that dict has a value for each key while set doesn't. So the order would be different from how elements are inserted but deterministic.

Until I found it's not true for set. 

$ cat ht_order.py 
colors = ['blue', 'red', 'green', 'yellow']

print(set(colors))
print(dict((c, c) for c in colors))

Run it in the terminal:

$ python3 ht_order.py 
{'red', 'yellow', 'blue', 'green'}
{'blue': 'blue', 'red': 'red', 'green': 'green', 'yellow': 'yellow'}

$ python3 ht_order.py 
{'yellow', 'blue', 'green', 'red'}
{'blue': 'blue', 'red': 'red', 'green': 'green', 'yellow': 'yellow'}

$ python3 ht_order.py 
{'green', 'yellow', 'red', 'blue'}
{'blue': 'blue', 'red': 'red', 'green': 'green', 'yellow': 'yellow'}

Why does set order keep changing?

EDIT:

Tried running in python2 and I got the same result every time.

$ python2 ht_order.py 
set(['blue', 'green', 'yellow', 'red'])
{'blue': 'blue', 'green': 'green', 'yellow': 'yellow', 'red': 'red'}
dhu
  • 718
  • 6
  • 19
  • 4
    Does this answer your question? [Are sets ordered like dicts in python3.6](https://stackoverflow.com/questions/45581901/are-sets-ordered-like-dicts-in-python3-6) and [Are dictionaries ordered in Python 3.6+?](https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6) – Kevin Ji Mar 31 '20 at 02:27
  • 1
    Hashing algorithms are generally seeded in a randomized way to help defend against collision-based attacks. In any case, `set` objects are indeed unordered in the Python standard. And they do not maintain order in the current CPython implementation, they are optimized for different use-cases anyway. There's *a lot* going on in the internals of `dict` that don't occur in `set` (e.g. shared keys for namespace dicts). – juanpa.arrivillaga Mar 31 '20 at 02:42
  • @kevinji thanks for the links. I wasn't aware that dictionaries are now ordered in 3.6. However my question was not about if set is ordered or not. I was curious about why set demonstrates a 'random/arbitrary' order every time you run it make it non-deterministic. – dhu Mar 31 '20 at 03:18
  • @juanpa.arrivillaga thank you for the explanation. Do you mind elaborate on that? Why can't set behavior in a similar way? – dhu Mar 31 '20 at 03:22
  • @dhu it *could*. The developers have decided to do it differently, though. – juanpa.arrivillaga Mar 31 '20 at 03:27
  • A much deeper explanation of why sets and dicts are different is provided in [Why don't Python sets preserve insertion order?](https://stackoverflow.com/questions/61414947). The reason why the set order is consistent in Python 2 but not Python 3 is that set ordering is based on `hash()` and [Python 3.3 added hash randomization](https://docs.python.org/3.3/reference/datamodel.html#object.__hash__) for security reasons. – ws_e_c421 May 19 '20 at 20:18

0 Answers0