8

Running this code multiple times 

t = {'a', 'b', 'c', 'd'}
print(t)

could print something like: 

{'c', 'b', 'a', 'd'} 
{'d', 'b', 'c', 'a'} # different
{'d', 'b', 'c', 'a'} # same
{'a', 'd', 'b', 'c'} # different
{'a', 'b', 'c', 'd'} # different
# etc

(If you are using the console to replicate it, make sure you click Rerun every time before you re-paste the code and execute it. If you still can't replicate, perhaps you have hash randomization not equal to random. On Python 3.3 and greater, hash randomization is turned on by default.)

On the other hand, the code below always prints the same set, and it's actually sorted:

s = {1, 6, 3.3, 4}
print(s) 

# prints: 
# {1, 3.3, 4, 6}
# {1, 3.3, 4, 6}
# {1, 3.3, 4, 6}
# {1, 3.3, 4, 6}

Question:
Why do sets of numbers appear to be always sorted and are they really always sorted?

user
  • 5,370
  • 8
  • 47
  • 75
  • Note that a `set` is basically just a `dict` with no values. – jonrsharpe Sep 09 '15 at 16:41
  • It only seems to be sorted in the iPython console, not in the normal python console, when iterating through it or calling `str(s)` or `repr(s)`. – jojonas Sep 09 '15 at 16:44
  • 1
    Another possible duplicate: http://stackoverflow.com/questions/12165200/order-of-unordered-python-sets – mgilson Sep 09 '15 at 16:52

1 Answers1

6

Note, I don't have python3.4 handy, but on python2.7 this isn't always the case (and I'd expect that to be true of python3.4 too).

I can even change the order of the elements based on how I put them into the set:

>>> print({1, 9})
set([9, 1])
>>> print({9, 1})
set([1, 9])
>>> set([9, 1])
set([9, 1])
>>> set([1, 9])
set([1, 9])

The order is determined by the hash of the element and by when it was inserted (in the case of hash collisions). In CPython, integers hash to themselves and a dict/set has 8 slots free to start with. Since there are 8 spots available, we can hash numbers 0 -> 7 (inclusive) without a hash collision. However, if we try to hash 8 and 0 (or 9 and 1) in the same set, we'll get a collision. if 9 is already in the set and then we try to put 1 in, python looks and says "Oh snap, that slot's taken -- Now I need to put it in the next most favorable slot". The details of collision resolution are beyond what I've looked into, so I can't offer insight into what slot that is ...

Note if we had more than ~5 elements in the set, then it would be resized (IIRC, to 16, then 32, then 64, ...) which changes which elements would collide (naturally).

mgilson
  • 300,191
  • 65
  • 633
  • 696
  • Not printing will give you a different ordering – Padraic Cunningham Sep 09 '15 at 16:48
  • @PadraicCunningham -- Not sure what you mean? if I do `a = {1, 9}; a` I still get the same thing as `print({1, 9})` on python2.7 – mgilson Sep 09 '15 at 16:51
  • http://pastebin.com/yaaS9UbE, that is running from ipython which seems to be different to the python repl – Padraic Cunningham Sep 09 '15 at 16:53
  • 1
    @PadraicCunningham -- You're using IPython which appears to try to be helpful and sort the elements for you. What happens if you just print `repr(s)` (which is what the normal python REPL will do)? – mgilson Sep 09 '15 at 16:55
  • funnily just using print or print repr both show the repr output i.e `set([3.3, 1, 6, 9])`, just doing `s` actually shows the nicely sorted order. – Padraic Cunningham Sep 09 '15 at 16:57
  • @PadraicCunningham -- Yep, that's what I'd expect. `IPython` can intercept the `s` and see that it's a set and print it in sorted order wheras if there's a function call or statement in the middle, it can't. – mgilson Sep 09 '15 at 16:59
  • 1
    @PadraicCunningham -- The really surprising thing for me is that `{1, 9}` and `set([1, 9])` give different results... For some reason it seems that python sets that involve only literals are read backwards? – mgilson Sep 09 '15 at 17:05
  • `s = set([1, 9]) s -> {1, 9}, print s -> set([1, 9])` and `s = {1, 9} s -> {1, 9}, print s -> set([9, 1])` – Padraic Cunningham Sep 09 '15 at 17:11
  • To see all the examples where the set order is not the same as the sorted order: https://tio.run/##K6gsycjPM9ZNBtP//6flFylkKmTmKRQl5qWnahgaaFpxcYIEs9AFOTPTFIrzi0pSUzSqM3UUsmo1FRRtFXIyi0tgfJAizoKizLwSDZCA5v//AA – Zachary Blackwood May 12 '21 at 19:28