4

There does seem to be some consistency in that calling set() on a string always seems to resolve to the same (non-alabetical) order, and both

set([1,2,3]) & set([1,2,3,4])

and its jumbled up cousin

set([2,3,1]) & set([4,3,1,2])

will result in orderly-looking set([1,2,3]).

On the other hand, something like a bit more racy, such as

from random import randint
set([randint(0,9) for x in range(3)])

will sometimes give something like set([9, 6, 7]) ...

... what is going on here?

user
  • 5,370
  • 8
  • 47
  • 75
ben
  • 1,583
  • 2
  • 11
  • 12
  • http://en.wikipedia.org/wiki/Hash_table – SLaks Feb 13 '13 at 22:09
  • You may find this thread interesting: http://stackoverflow.com/questions/3949310/how-is-cpythons-set-implemented – ben_frankly Feb 13 '13 at 22:12
  • I did some minor experimenting a while back and I think I found it to be somehow binary, like a binary search tree (but I have a feeling I'm horribly wrong here, as it's expected to behave as a hash-table). You may be interested in [this](http://stackoverflow.com/q/13001913/198633) and [this](http://stackoverflow.com/q/14493204/198633) – inspectorG4dget Feb 13 '13 at 22:13

1 Answers1

5

You should consider sets as unordered collections

They are stored in a hash table.

Additionally, as you continue to add elements, the hash will be shifted into a larger table, so that order may change dramatically.

There is no guarantee that the order will be the same across different Python versions/implementations.

John La Rooy
  • 295,403
  • 53
  • 369
  • 502
  • I just came to leave http://bugs.python.org/issue13703 here. The order being deterministic is an implementation detail that is irrelevant, all that matters is that `set` is unordered. – mmgp Feb 13 '13 at 22:20
  • @mmgp, I meant to say that first, but forgot :) – John La Rooy Feb 13 '13 at 22:21
  • I also implicitly asked to not mention the order is deterministic (see the report). For instance, start Python 3.3 and do `hash('x')`, exit the interpreter and start again, try `hash('x')` again. – mmgp Feb 13 '13 at 22:29